[erlang-questions] Trace-Driven Development

[Henning Diedrich]

On 6/4/12 6:52 AM, Michael Turner wrote:
> I started using seq_trace ... an implementation of Lamport clocks. ... Just say it.

I would like to try a brief on what Lamport clocks are, based on [1] + [2].

I think that it's freakishly exciting because it obviously is an 
application of the Special Theory of Relativity, as Lamport mentions.

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


Lamport clocks are simple counters, one per process.

They help to order events occurring in parallel processes, with 'false 
positives' as price for the ease of the algorithm.

False positives would be events listed as having happening one after the 
other while "really" (causally) having occurred "at the same time".

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.

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.

Lamport clocks work like this:

* Every process has a counter.
* Before any 'event' it increments it.
* Also before sending a message, it increments it.
* The process sends its counter value with every message.
* The receiving process sets its counter to the greater of itself or the 
received.
* It increments it.
* It assigns it to the event of receiving.


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.

Writes Lamport: "Acknowledgment. The use of timestamps to order 
operations, and the concept of anomalous behavior are due to Paul 
Johnson and Robert Thomas."

Best,
Henning

[1] http://en.wikipedia.org/wiki/Lamport_timestamps
[2] http://research.microsoft.com/users/lamport/pubs/time-clocks.pdf

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20120606/f5beceda/attachment.htm>