Re: Question about message passing paradigm

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