# Time, Clocks, and the Ordering of Events in a Distributed System

2018-02-24 · https://fsgeek.ca/log/time-clocks-and-the-ordering-of-events-in-a-distributed-system/

_[Time, Clocks, and the Ordering of Events in a Distributed System](https://amturing.acm.org/p558-lamport.pdf) Leslie Lamport, Communications of the ACM, July 1978, pp. 558-565. _ I had not originally intended to cover this paper, but as I started trying to describe [_Implementing Atomic Actions on Decentralized Data_](https://fsgeek.ca/?p=337&preview=true), I realized that I needed to include it in order to better explain that work. This is one of the papers for which Leslie Lamport was awarded the [Turing Award](https://amturing.acm.org/award_winners/lamport_1205376.cfm). In it, he is wrestling with the effects of relativity in computer systems. What does this mean? In essence, as soon as we have more than two distinct computer systems communicating with one another in a network, we must account for the fact that the order of events may now vary for each individual note. Indeed, as it turns out, this effect is not restricted to distributed systems. It can be seen in single computer systems with multiple processors as well (another area where Lamport was significantly involved) in the study of [ _consistency models_](https://en.wikipedia.org/wiki/Consistency_model). Networks tend to exacerbate these issues because the times involved often make it more apparent that there are issues. This will profoundly impact distributed systems (including distributed file systems, a notable and classic example of distributed systems) and we continue to wrestle with its manifestations 40 years after this paper. [![Figure 1](/media/2018/02/Figure-1-300x280.png)](/media/2018/02/Figure-1.png) The paper describes a system (Figure 1) in which three different components, labeled  _Process P, Process Q,_ and  _Process R,_ are sending messages between them. Individual messages are labeled and numbered in sequence and the time between them is shown. It is worth noting that the times are of both when the message was  _sent_ as well as when it was  _received_. This demonstrates that the **observed** order of events does not necessarily match what an external observer might see as the ordering. Thus, for example,  _Process R_ receives messages in a different order than they were sent by  _Process Q_. This behavior might seem surprising initially, but is in fact a common occurrence. This could be due to queue types, intermediate network components, scheduling delays, etc. Thus, he asks the question: what is the correct ordering of events in this system? How do we capture this and ensure that the system behaves as we expect? [![Figure 2](/media/2018/02/Figure-2-300x268.png)](/media/2018/02/Figure-2.png) He introduces a nomenclature of describing the "happened before" relationship, establishing an ordering of events within the system. He uses the → character to indicate this relationship. Thus, if  _a_ comes before  _b_ he writes "_a_ → _b_ ". Similarly it is [transitive](https://en.wikipedia.org/wiki/Transitive_relation) operation: if  _a → b_ and  _b → c_ then  _a → c_. Finally he defines an operation as  _concurrent_ if there is no ordering between  _a_ and  _b_. This applies to operations within a single process as well as between processes. He notes in this discussion that _sending_ a message must have happened before  _receiving_ a message. While this might sound simple, it helps us begin to reason about these events, since we can pay attention to the events that do have ordering constraints and ignore those that do not. In many cases, we won't care about the order of two operations because the net effect is the same, regardless of the order. What we do want to do, however, is ensure that we understand ordering for those operations where it  _does_ matter. Figure 2 then takes the same chart, but this time he adds the concept of a clock tick. The dashed lines represents the tick of a clock; the ticks occurs  _between_ events. He then defines the time ordering ("clock function") is related to the → relationship. If  _a → b_ then C(_a_) < C(_b_). That is, the clock tick (time) is also well ordered. He observes then that we can extend this definition to cover the prior case, where we look at the ordering of operations within a single process, as well as across processes: recall that _a → b_ is required for messages sent between processes, where _a_ is the send event and  _b_ is the receive event and thus C(_a)_ < C(_b_) in this case as well. He calls this the "Clock Condition". [![Figure 3](/media/2018/02/Figure-3-292x300.png)](/media/2018/02/Figure-3.png) He then goes one step further: he flattens out the clock ticks, yielding Figure 3. Now our clock ticks are uniform time and our events are within one of the clock tick intervals. Since we separate dependent operations, we now have a model we can use to order events globally. _This_ was the point he was trying to make. "_Being able to totally order the events can be very useful in implementing a distributed system._ " This is a classic understatement and is the focus of much of distributed systems research and implementation to this day: how do you ensure that you have a definitive order of events. We will see this when looking at later work. At this point he focuses on more rigorously defining his system. This allows him to note that this becomes a "distributed algorithm". He describes the  _replicated state machine_ that is being executed by all the nodes within the distributed system. There is no central authority in this model forcing the ordering. **This** is an important point not to miss: in Lamport's distributed system there is no requirement for a centralized service. He does not insist on a total ordering of events in the system and settles for a partial ordering - one in which he doesn't worry about the events that aren't sensitive to their ordering. This is a powerful technique because it gives up total determinism; we gain performance through parallelism. From this article we get the [**Lamport Clock**](http://carothersc.github.io/ROSS/model-dev/lamport.html) which is not so much a clock as a monotonically increasing value that represents relative ordering. Note that a hardware clock will satisfy this invariant requirement as well.