“Time, Clocks, and the Ordering of Events in a Distributed System” – The Breakthrough

[Originally published and copyrighted 24OCT2019 by Dr Kenneth M. Beck. If you are not familiar with Leslie Lamport and his blockchain theory, we provide his publicly available classic paper on the subject. We will proceed with the understanding that the reader has read his paper or understands its propositions.]

“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 before the 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 Distributed 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 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 is crucial to the correct functioning of a distributed system.

In Lamport’s view of a distributed 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, but far different from causality in Einstein’s Special Relativity.

(That last point we will revisit in the next installment in this series.)

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

The Clock Condition

“We are assuming that the events of a process form a sequence, where <a> occurs before <b> in this sequence if <a> happens before <b>. In other words, a single process is defined to be a set of events with an a priori total ordering…” Lamport, pp 559

This “clock condition” has nothing to do with spacetime nor Einstein’s relativity, despite pretty figures and figurines associated by Lamport. It is purely and classically, Newtonian. In its essence: there is an absolute time base. With cause and effect proceeding in an an unchanging progression from <a> to <b> to <c>.

Logical Clocks 

“We now introduce clocks into the system (!)…More precisely, we define a clock Ci for each process Pi to be a function which assigns a number Ci<a> to any event a in that process.  The entire system of clocks is represented by the function C which assigns to any event b the number C<b>, where C<b> = Cj<b> if be is an event in the process Pj….For now, we make no assumption about the reaction of the numbers Ci<a> to physical time(!), so we can think of the clocks Ci as logical rather than physical clocks.(!)…They can be implemented by counters with no actual timing mechanism.” Lamport, pp559-560

“We now consider what it means for such a system of clocks to be correct.  We cannot base our definition of correctness on physical time, since that would require introducing clocks which keep physical time. Our definition must be based on the order in which events occur.”

“The strongest reasonable condition is that if an event <a> occurs before another event <b>, then a should happen at an earlier time than <b>.  We state this condition more formally as follows.” 

“Clock Condition. For any event a, b:  if a-> b then C<a> < C<b>.”

“Note that we cannot expect the converse condition to hold as well, since that would imply that any two concurrent events must occur at the same time (not in spacetime).” Lamport, pp560

“…the Clock Condition implies that if a -> b then a => b. In other words, the relation => is a way of completing the “happened before” partial ordering to a total ordering.

“The ordering => depends on the system of clocks Ci and is not unique.  Different choices of clocks which satisfy he Clock Condition yield different relations =>…” Lamport, pp562

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