Richard,<br><br>I'm new to Erlang and FP, and I want to learn from my mistakes or misunderstandings. Please could you critique the suggestion I sent in regarding this problem? The fact that nobody commented means either that it was (a) totally naive and not worthy of comment (or to spare my feelings), or (b) such a good idea that all were rendered speechless with admiration. Somehow the probability of (b) seems rather low. So... where did I go wrong?<br>
<br>Regards,<br>Edwin FIne<br><br><div class="gmail_quote">On Mon, Jun 30, 2008 at 11:33 PM, Richard A. O'Keefe <<a href="mailto:ok@cs.otago.ac.nz">ok@cs.otago.ac.nz</a>> wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
The problem we are discussing is<br>
processes B, C, D hold information X, Y, Z respectively;<br>
process A wants a coherent snapshot of X, Y,Z.<br>
<br>
There are actually two slightly different cases depending on<br>
A needs "X Y Z as of *now*" (A, B, C, and D must all<br>
synchronise), or A needs "X Y Z as of *some* time in the<br>
recent past" (B, C, and D must all synchronise but can then<br>
send the information to A without waiting for A to receive it).<br>
<br>
I like this problem because it is simple yet subtle.<br>
One way that it is subtle is that in "multithread" programming<br>
most people STILL think in terms of a single absolute time<br>
shared by all threads. (After all, there _is_ such a thing,<br>
the system clock. And yes, it's not exactly true, but it's<br>
close enough to make people _think_ it's true.) But when you<br>
start thinking about Erlang and especially *distributed*<br>
Erlang, you start realising that "now" is a pretty fuzzy<br>
concept.<br>
<br>
To me, the easiest approach to *think* was<br>
<br>
A sends "tell me X" to B, "tell me Y" to C,<br>
and "tell me Z" to D in any order,<br>
then does three receives in any order to<br>
collect the results, then<br>
sends "thanks" to B, C, and D in any order.<br>
<br>
B receives "tell me X" from A, computes X,<br>
sends "here is X" to A, then waits for<br>
"thanks" from A.<br>
<br>
C and D are just like B.<br>
<br>
This has 9 messages compared, but it is symmetric, and it is<br>
actually pretty close to the locking technique (to "lock" a<br>
process, send it a message asking it to wait, receive its<br>
acceptance, and then send it a message telling it to proceed).<br>
This extends to any number of processes E, F, G, ... and none<br>
of the processes except A has to know about any of the others.<br>
<br>
On 30 Jun 2008, at 6:45 pm, Erik Reitsma proposed a scheme<br>
that doesn't actually need any functions to be sent around<br>
(which is nice if you are doing distribution):<br>
<br>
A sends "I need X Y and Z, ask C and D for Y and Z"<br>
to B then waits.<br>
B sends "A needs Y and Z, ask D for Z, here is X"<br>
to C. B then waits for the go-ahead.<br>
C sends "A needs Z, here are X and Y" to D,<br>
then waits.<br>
D sends "here are X Y and Z" to A.<br>
If a four-way synchronisation is wanted, D waits.<br>
If a three-way is wanted, it doesn't.<br>
A receives X, Y, and Z. It sends "go ahead" to B<br>
and C (and to D if four-way is wanted).<br>
<br>
This is 7 messages if the "NOW" reading with four-way<br>
synchronisation is wanted, or 6 if the "some time in the<br>
recent past" reading with three-way synchronisation is<br>
wanted. Since B, C, and D have to be told that their<br>
information is needed and A has to receive the results,<br>
four messages are needed.<br>
<br>
Can it be done in fewer than 7 (or 6) messages?<br>
Are there other readings of the requirements that I've missed?<br>
How do/should we think about these problems?<br>
<br>
Pace Dijkstra, I'm afraid that I came up with the schemes<br>
above in a very anthropomorphic CRC-card-ish way:<br>
who knows what?<br>
who needs to know what?<br>
can the message count be reduced if I ask<br>
someone to do something for me?<br>
plus a sort of intuitive idea that<br>
to get N processes to synchronise, get all<br>
but 1 of them waiting for something<br>
<br>
There has to be a tutorial, perhaps even a textbook, waiting<br>
to be written about "how to think about messages".<br>
<br>
<br>
<br>
</blockquote></div><br><br clear="all"><br>-- <br>The great enemy of the truth is very often not the lie -- deliberate, contrived and dishonest, but the myth, persistent, persuasive, and unrealistic. Belief in myths allows the comfort of opinion without the discomfort of thought.<br>
John F. Kennedy 35th president of US 1961-1963 (1917 - 1963)