[erlang-questions] Question about message passing paradigm

[Richard A. O'Keefe]

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
concept.

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,
	  then waits.
	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".