[zzzcpan]

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]

> [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]

Common, you are literally trying to describe message passing as race conditions.

[chrisseaton]

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]

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]

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'

[toast0]

As with most things in Erlang; if it's important, you must make it explicit. Implicit ordering works in your fork-join example with only a single fork, but if you require an ordering, you must be explicit about passing information through to enforce the ordering you need.

If you instead did

    fork {
      sort a
    }
    fork {
      sort b
    }
    a' = join
    b' = join

you would have the same problem as in Erlang. or you could have actor C sort B inside the actor between send a to A and receive a' and you would also have an implicit ordering.

In this case, merge sort could work with either order if a stable sort isn't required, or if the sort key is the whole element.

If it matters, this is easy to defend against, you just send a tag (a ref in Erlang would be perfect for this case, if the merge happened in a fourth actor, a numeric indication of ordering would be more useful) in the message to actors A and B, and use that to enforce an ordering when receiving the replies.

[zzzcpan]

Erlang lets you receive first message first even if it arrives last, you just have to specify which message, exactly as in your example. But order doesn't actually matter for sorting, you cannot possible make a mistake wrt to ordering here.