[erlang-questions] Question about message passing paradigm
Richard A. O'Keefe
Tue Jul 1 05:33:27 CEST 2008
The problem we are discussing is
processes B, C, D hold information X, Y, Z respectively;
process A wants a coherent snapshot of X, Y,Z.
There are actually two slightly different cases depending on
A needs "X Y Z as of *now*" (A, B, C, and D must all
synchronise), or A needs "X Y Z as of *some* time in the
recent past" (B, C, and D must all synchronise but can then
send the information to A without waiting for A to receive it).
I like this problem because it is simple yet subtle.
One way that it is subtle is that in "multithread" programming
most people STILL think in terms of a single absolute time
shared by all threads. (After all, there _is_ such a thing,
the system clock. And yes, it's not exactly true, but it's
close enough to make people _think_ it's true.) But when you
start thinking about Erlang and especially *distributed*
Erlang, you start realising that "now" is a pretty fuzzy
To me, the easiest approach to *think* was
A sends "tell me X" to B, "tell me Y" to C,
and "tell me Z" to D in any order,
then does three receives in any order to
collect the results, then
sends "thanks" to B, C, and D in any order.
B receives "tell me X" from A, computes X,
sends "here is X" to A, then waits for
"thanks" from A.
C and D are just like B.
This has 9 messages compared, but it is symmetric, and it is
actually pretty close to the locking technique (to "lock" a
process, send it a message asking it to wait, receive its
acceptance, and then send it a message telling it to proceed).
This extends to any number of processes E, F, G, ... and none
of the processes except A has to know about any of the others.
On 30 Jun 2008, at 6:45 pm, Erik Reitsma proposed a scheme
that doesn't actually need any functions to be sent around
(which is nice if you are doing distribution):
A sends "I need X Y and Z, ask C and D for Y and Z"
to B then waits.
B sends "A needs Y and Z, ask D for Z, here is X"
to C. B then waits for the go-ahead.
C sends "A needs Z, here are X and Y" to D,
D sends "here are X Y and Z" to A.
If a four-way synchronisation is wanted, D waits.
If a three-way is wanted, it doesn't.
A receives X, Y, and Z. It sends "go ahead" to B
and C (and to D if four-way is wanted).
This is 7 messages if the "NOW" reading with four-way
synchronisation is wanted, or 6 if the "some time in the
recent past" reading with three-way synchronisation is
wanted. Since B, C, and D have to be told that their
information is needed and A has to receive the results,
four messages are needed.
Can it be done in fewer than 7 (or 6) messages?
Are there other readings of the requirements that I've missed?
How do/should we think about these problems?
Pace Dijkstra, I'm afraid that I came up with the schemes
above in a very anthropomorphic CRC-card-ish way:
who knows what?
who needs to know what?
can the message count be reduced if I ask
someone to do something for me?
plus a sort of intuitive idea that
to get N processes to synchronise, get all
but 1 of them waiting for something
There has to be a tutorial, perhaps even a textbook, waiting
to be written about "how to think about messages".
More information about the erlang-questions