<html>
<head>
<meta content="text/html; charset=ISO-8859-1"
http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000066">
On 6/4/12 6:52 AM, Michael Turner wrote:
<blockquote
cite="mid:CANHeBiiYkktUZ3DW1Th6oUJpM6rJPkz3w8234ka9UBSzOF0JcQ@mail.gmail.com"
type="cite">
<pre wrap="">I started using seq_trace ... an implementation of Lamport clocks. ... Just say it. </pre>
</blockquote>
<br>
I would like to try a brief on what Lamport clocks are, based on [1]
+ [2]. <br>
<br>
I think that it's freakishly exciting because it obviously is an
application of the Special Theory of Relativity, as Lamport
mentions.<br>
<br>
From that, I sense a promise of finally understanding something I
run up against ever since tackling Erlang, how to /think/ parallel.
Special Relativity really might be the answer to that: it cancels
out the physical clock that is unattainable as part of any solution
at any rate. Giving it up, in essence skipping this reaching for an
objective reference for events, may be the liberating move to cut
the knot. In the process I also found a new favored quote: "Systems
in which an event can happen before itself do not seem to be
physically meaningful."<br>
<br>
<br>
Lamport clocks are simple counters, one per process.<br>
<br>
They help to order events occurring in parallel processes, with
'false positives' as price for the ease of the algorithm.<br>
<br>
False positives would be events listed as having happening one after
the other while "really" (causally) having occurred "at the same
time".<br>
<br>
This matters less because an order of events can never express with
certainty what event /did/ affect which other event, but only which
event /did not/ (the later the earlier). And this is not violated
when concurrent events are ordered in sequence.<br>
<br>
What is lost is only the accurate reflection of possibility: ordered
by Lamport clocks, some events that look like they possibly could
have affected some other (later) events, in reality could not.<br>
<br>
Lamport clocks work like this:<br>
<br>
* Every process has a counter. <br>
* Before any 'event' it increments it.<br>
* Also before sending a message, it increments it. <br>
* The process sends its counter value with every message.<br>
* The receiving process sets its counter to the greater of itself or
the received.<br>
* It increments it.<br>
* It assigns it to the event of receiving.<br>
<br>
<br>
I found Lamport's original paper [2] much more accessible than
usually, and the illustrations he gives (Fig. 1 - 3) are easy to
grasp and illuminating. It's really mostly about the 3 1/2 first
pages.<br>
<br>
Writes Lamport: "Acknowledgment. The use of timestamps to order
operations, and the concept of anomalous behavior are due to Paul
Johnson and Robert Thomas."<br>
<br>
Best,<br>
Henning<br>
<br>
[1] <a class="moz-txt-link-freetext" href="http://en.wikipedia.org/wiki/Lamport_timestamps">http://en.wikipedia.org/wiki/Lamport_timestamps</a><br>
[2] <a class="moz-txt-link-freetext" href="http://research.microsoft.com/users/lamport/pubs/time-clocks.pdf">http://research.microsoft.com/users/lamport/pubs/time-clocks.pdf</a><br>
<br>
</body>
</html>