Time, Clocks, the Ordering of Events in Distributed Systems – The Breakthrough

Screen Shot 2019-10-23 at 8.44.59 PM

The concept of time is fundamental to our way of thinking. It is derived from the more basic concept of the order in which events occur. We say that something happened at 3:15 if it occurred after our clock read 3:15 and before it read 3:16. The concept of the temporal ordering of events pervades our thinking about systems. For example, in an airline reservation system we specify that a request for a reservation should be granted if it is made beforethe flight is filled. However, we will see that this concept must be carefully reexamined when considering events in a distributed system….”  – Leslie Lamport,        Time, Clocks, and the Ordering of Events in Distrributed Systems 

In the mid-1970’s, Leslie Lamport was among just a handful of engineers and computer scientists thinking and writing about causality in algorithms and digital data.  At the time, the main concern was concurrence in data segments of distributed systems.  Not one after the other, but  ‘more like’ a measurable simultaneity.  These data streams did not have to exist as single events in spacetime, sª, but in fact were defined as space data streams.  With data stream (1) beginning before the next data stream (2).  And (2) ending before data stream (1) in unit δt .  Both (1) and (2)  had width and breath – spreads of δs or Δs.

Leslie Lamport in the late 70s wrote the seminal work by himself, “Time, Clocks, and the Ordering of Events in a Distributed System”, and showed that two events occurring in δt physical times can be concurrent, so long as they don’t affect one another.  Much of the paper is spent defining causality – what it means for an event to happen before another – in both the logical and physical sense.

This is important, because determining the order of when events take place, such as the measurement of a sensor or detection of error and subsequent error correction – as well as determining which events actually took place in the first place – is crucial to the correct functioning of a distributed system.

In Lamport’s system, time flows upwards unidirectionally, and each message is being sent and received at later and later times. If there exists a path from one event to another, by only traveling upwards in the diagram, “then that means that one event happened before the other.”  If an event doesn’t happen either before or after another event, then it’s said that those events are “concurrent”.   Leslie Lamport realized that the notion of causality was central, and the way he constructed causality in distributed systems was analogous to, but not the same as, that in Einstein’s special relativity.

That last point we will revisit in the next installment in this no-name series.

I wish the careful reader who hasn’t, to thoroughly read Lamport’s breakthrough paper (Time, Clocks, and the Ordering of Events in Distrributed Systems ), where the PDF is free for download under free-use. We will make references to it in the future.


 

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s