4 ms·

Actor model is very deterministic, but it can model unbounded non-determinism, i.e. any concurrency problem. Including fine-grained and irregular data paralleli

Actor model is very deterministic, but it can model unbounded non-determinism, i.e. any concurrency problem. Including fine-grained and irregular data parallelism. It's up to the compiler to generate SIMD instructions out of it, if that's what you mean.

chrisseaton 9y ago
How co you argue it’s deterministic? If one actor asks two other actors to do a job and send the result back, those results come in a nondeterimistic order. That’s a race condition. It’s easy to write programs with bugs in them because of this. Something like fork-join is deterministic because results come in a fixed order. And for generating SIMD from actors? Or handling irregularity efficiently? I feel like you’re making the ‘sufficiently clever compiler’ argument. We cannot currently efficiently solve all parallelism problems in practice using actors, and we don’t know how we would be able to.
- zzzcpan 9y ago
  Non-deterministic order is not a race condition. You also need some sort of shared resource and being unaware of said non-deterministic order of incoming messages. With actor model you can't have shared resources and can't be unaware that messages come in no specific order. And I'm not arguing for a sufficiently clever compiler, just that you can express any concurrency with actors. You can definitely create a convention backed by actors that compiles into SIMD if you need it.
  - chrisseaton 9y ago
    > [it is a general race condition if] there is some order among events a and b but the order is not predetermined by the program (Christoph von Praun) If two actors do some work concurrently and when finished send a message to another actor, the order those messages arrive at the other actor, event a and event b, is not predetermined by the program. So it's a race condition. actor a { do some work; send 'a' to x; } actor b { do some work; send 'b' to x; } actor x { receive; <- has this received from 'a' or 'b'? Nobody knows. They've raced. } You can express any concurrency with actors, but we do not know how to do so as efficiently as with other concurrency models for parallelism. Someone might be able to implement it efficiently, but nobody has managed it yet, so we're still reliant on shared memory and other approaches concurrency.
    - zzzcpan 9y ago
      Common, you are literally trying to describe message passing as race conditions.
      - chrisseaton 9y ago
        It's not my definition! And you're right, normal message passing does leave you vulnerable to race conditions and your program can run a different way each time you run it! That's a major problem with it. That's why I think other models of concurrency, such as the fork-join model, where the equivalent of 'messages' have to arrive in a deterministic order and so there are no race conditions, are safer.
        zzzcpan 9y ago
        Message passing forces you to explicitly handle non-deterministic order, how can it leave you vulnerable to race conditions? If you need to receive a specific message first, you wait for that specific message, that's it. Simple and deterministic.
        chrisseaton 9y ago
        This is a real error I've seen someone make using Erlang in making a parallel sort when teaching parallel programming to masters students. actor A { receive half an array sort it send it to C } actor B { receive half an array sort it send it to C } actor C { (a, b) = divide input array into halves send a to A send b to B receive a' receive b' merge a', b' } They send to A, send to B, and then think they're going to receive from A first, because they sent first, but B could finish first instead. Sometimes their program works, sometimes it doesn't. Yeah it's their fault, but the model hasn't helped them not make the bug and worse they may never see the bug until they deploy into production. If we used a fork-join model, they could not have made this mistake, and even if they did make some kind of mistake, at least they'd see it every time they ran their program. (a, b) = divide input array into halves fork { sort a } b' = sort b a' = join return a' + b'

chrisseaton 9y ago

How co you argue it’s deterministic? If one actor asks two other actors to do a job and send the result back, those results come in a nondeterimistic order. That’s a race condition. It’s easy to write programs with bugs in them because of this. Something like fork-join is deterministic because results come in a fixed order. And for generating SIMD from actors? Or handling irregularity efficiently? I feel like you’re making the ‘sufficiently clever compiler’ argument. We cannot currently efficiently solve all parallelism problems in practice using actors, and we don’t know how we would be able to.

zzzcpan 9y ago
Non-deterministic order is not a race condition. You also need some sort of shared resource and being unaware of said non-deterministic order of incoming messages. With actor model you can't have shared resources and can't be unaware that messages come in no specific order. And I'm not arguing for a sufficiently clever compiler, just that you can express any concurrency with actors. You can definitely create a convention backed by actors that compiles into SIMD if you need it.
- chrisseaton 9y ago
  > [it is a general race condition if] there is some order among events a and b but the order is not predetermined by the program (Christoph von Praun) If two actors do some work concurrently and when finished send a message to another actor, the order those messages arrive at the other actor, event a and event b, is not predetermined by the program. So it's a race condition. actor a { do some work; send 'a' to x; } actor b { do some work; send 'b' to x; } actor x { receive; <- has this received from 'a' or 'b'? Nobody knows. They've raced. } You can express any concurrency with actors, but we do not know how to do so as efficiently as with other concurrency models for parallelism. Someone might be able to implement it efficiently, but nobody has managed it yet, so we're still reliant on shared memory and other approaches concurrency.
  - zzzcpan 9y ago
    Common, you are literally trying to describe message passing as race conditions.
    - chrisseaton 9y ago
      It's not my definition! And you're right, normal message passing does leave you vulnerable to race conditions and your program can run a different way each time you run it! That's a major problem with it. That's why I think other models of concurrency, such as the fork-join model, where the equivalent of 'messages' have to arrive in a deterministic order and so there are no race conditions, are safer.
      - zzzcpan 9y ago
        Message passing forces you to explicitly handle non-deterministic order, how can it leave you vulnerable to race conditions? If you need to receive a specific message first, you wait for that specific message, that's it. Simple and deterministic.
        chrisseaton 9y ago
        This is a real error I've seen someone make using Erlang in making a parallel sort when teaching parallel programming to masters students. actor A { receive half an array sort it send it to C } actor B { receive half an array sort it send it to C } actor C { (a, b) = divide input array into halves send a to A send b to B receive a' receive b' merge a', b' } They send to A, send to B, and then think they're going to receive from A first, because they sent first, but B could finish first instead. Sometimes their program works, sometimes it doesn't. Yeah it's their fault, but the model hasn't helped them not make the bug and worse they may never see the bug until they deploy into production. If we used a fork-join model, they could not have made this mistake, and even if they did make some kind of mistake, at least they'd see it every time they ran their program. (a, b) = divide input array into halves fork { sort a } b' = sort b a' = join return a' + b'