5 ms·

The guy you just responded to invented the Actor model. I'd guess he knows... Besides, such a fork join model might be theoretically free of timing and coordi

by j-pb 6y ago

The guy you just responded to invented the Actor model. I'd guess he knows... Besides, such a fork join model might be theoretically free of timing and coordination in a system with infinite resources (bus widths, no cache coherence, an infinitely fast coordinator e.t.c.) but that's not what silicon looks like. The nice thing about the Actor model is exactly that it immediately exposes you to non-determinism, distributed state, and in Erlangs case, failure. It's what allows Erlang systems to "effortlessly" (you had to put the effort upfront) span many node clusters with arbitrary reliability in the face of failures. Somewhere else you write: > The problem is this corner case opens up all the fundamental issues I mention. When we include it we've got a big non-deterministic, racey, stateful, problem. That's not caused by the Actor model, but by the fundamental laws governing distributed systems. Distributed systems are inherently, non-deterministic, racey and statefull. Two generals dictates that you can't solve these issues, unless you're on a single writer system (which your scatter-gather algorithm is an example of, in which you will always be limited by the throughput of the process that organises your scatter-gather operations / your control plane). In which case, you might as well ignore all forms of concurrency and do one thing at a time, which will be faster anyways.

deleted 6y ago
[deleted]
chrisseaton 6y ago
If I ask an undergraduate to implement a simple parallel merge sort using fork-join I know they cannot get it wrong - because they cannot receive results in an order they were not expecting. They cannot possibly introduce a race condition under any circumstances. If they try to implement it using Erlang-style actors and message passing, they can get it wrong and expect the half they sub-sorted first to respond with the result first. I know this because I've seen it in undergraduates for real. Worst of all - it can work every time they test it but then fail in production, so it's extremely hard to explain and teach them to do it correctly.
- j-pb 6y ago
  The kind of parallelism relevant to Merge Sort does not really relate to what message passing and particularly Erlang (the topic of this thread) are about. Erlang is about distributed coordination. It's all about concurrency, and parallelism is a means to the end of increased reliability. Merge Sort is data parallel SIMD with a single coordinator. It's like the difference between multi factory industrial food production (distributed), and you handling multiple pots and pans on the same stove (parallel). You'd never use message passing for that, because it has way too much overhead in and of itself. And if you had more data than could fit a single machine, you'd choose a different algorithm anyways. It's not that hard to find a simpler implementation for a problem that's not really distributed by nature. You're also missing the huge learning opportunity for undergrads here. It's totally possible and actually easy to implement merge sort with message passing (although nobody would do it in the real world), and it provides a good lesson. The first way to implement something is often not the correct one. The naive but wrong implementation is to send messages with each value to be sorted. So the mailboxes act like a list. However since there's no ordering guarantee, the issues you mentioned will crop up. Since messages are our unit of coordination, the naively fixed version simply sends the entire array to its parent node which then merges the arrays it received. However there is also the possibility to send a tuple containing the index in the subarray as well as the value, which allows the parent to buffer the value and wait for the gaps to be filled. Which teaches you something about TCP as well. Seriously. Why only ask your undergrads questions, that they can't get wrong? Seems a waste of everybody's time. You should rather teach them about the tradeoffs between different concurrency and parallelism models. SIMD for data parallel high perf stuff. Actor model, for distributed coordination and reliability. Dataflow for FPGA programming. There's no one fits all model.
  - deleted 6y ago
    [deleted]
- africanboy 6y ago
  it's very easy to order the responses once you received them, it's a different problem from the original one, parallel sorting doesn't depend on the order, every chunk is ordered independently and returned to the caller, unless you mean sorting the list in place (mutating the list) which is not supported in Erlang

by j-pb 6y ago

deleted 6y ago

[deleted]

chrisseaton 6y ago

If I ask an undergraduate to implement a simple parallel merge sort using fork-join I know they cannot get it wrong - because they cannot receive results in an order they were not expecting. They cannot possibly introduce a race condition under any circumstances. If they try to implement it using Erlang-style actors and message passing, they can get it wrong and expect the half they sub-sorted first to respond with the result first. I know this because I've seen it in undergraduates for real. Worst of all - it can work every time they test it but then fail in production, so it's extremely hard to explain and teach them to do it correctly.

j-pb 6y ago
The kind of parallelism relevant to Merge Sort does not really relate to what message passing and particularly Erlang (the topic of this thread) are about. Erlang is about distributed coordination. It's all about concurrency, and parallelism is a means to the end of increased reliability. Merge Sort is data parallel SIMD with a single coordinator. It's like the difference between multi factory industrial food production (distributed), and you handling multiple pots and pans on the same stove (parallel). You'd never use message passing for that, because it has way too much overhead in and of itself. And if you had more data than could fit a single machine, you'd choose a different algorithm anyways. It's not that hard to find a simpler implementation for a problem that's not really distributed by nature. You're also missing the huge learning opportunity for undergrads here. It's totally possible and actually easy to implement merge sort with message passing (although nobody would do it in the real world), and it provides a good lesson. The first way to implement something is often not the correct one. The naive but wrong implementation is to send messages with each value to be sorted. So the mailboxes act like a list. However since there's no ordering guarantee, the issues you mentioned will crop up. Since messages are our unit of coordination, the naively fixed version simply sends the entire array to its parent node which then merges the arrays it received. However there is also the possibility to send a tuple containing the index in the subarray as well as the value, which allows the parent to buffer the value and wait for the gaps to be filled. Which teaches you something about TCP as well. Seriously. Why only ask your undergrads questions, that they can't get wrong? Seems a waste of everybody's time. You should rather teach them about the tradeoffs between different concurrency and parallelism models. SIMD for data parallel high perf stuff. Actor model, for distributed coordination and reliability. Dataflow for FPGA programming. There's no one fits all model.
- deleted 6y ago
  [deleted]
africanboy 6y ago
it's very easy to order the responses once you received them, it's a different problem from the original one, parallel sorting doesn't depend on the order, every chunk is ordered independently and returned to the caller, unless you mean sorting the list in place (mutating the list) which is not supported in Erlang