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