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


_______________________________________________
erlang-questions mailing list
erlang-questions@...
http://www.erlang.org/mailman/listinfo/erlang-questions