Papers
Time, Clocks, and the Ordering of Events in a Distributed System
Leslie Lamport · Communications of the ACM, 1978
The problem: in a distributed system, 'before' and 'after' are not obvious
In a distributed system, processes run on separate machines and communicate only through messages that take an unpredictable time to arrive. In this scenario, asking whether one event happened before another is treacherous: there is no single, perfect clock that everyone consults, and each machine's physical clocks diverge. Lamport starts from this observation and argues that the intuitive notion of 'before' needs to be carefully redefined. The paper examines the concept of one event occurring before another and shows that it defines only a partial ordering of events: some pairs of events have a well-defined order, and others simply do not. Next, the author proposes an algorithm for synchronizing a system of logical clocks, so that events can be placed in a total order. The underlying idea is that, for many coordination problems, what matters is not the wall-clock time, but the order in which things may have influenced one another. The paper fixes this distinction, which became basic vocabulary for those who design distributed systems.
The happened-before relation and concurrency
The paper's central concept is the 'happened-before' relation. It is built from two simple rules. First, if two events occur in the same process, the one that comes earlier in that process's execution happens before the other. Second, sending a message happens before receiving that same message. In addition, the relation is transitive: if A precedes B and B precedes C, then A precedes C. The result is a strict partial order, in which no event happens before itself. When two events cannot be linked by any path of sequential events and messages, the paper calls them concurrent: neither can have caused or influenced the other, and saying which came first has no physical meaning at all. This definition is purely causal and does not depend on any wall-clock time. It gives an objective criterion for knowing when the order of two events is real information and when it is just a coincidence of observation, which underpins the rest of the paper.
Logical clocks and total order
To make the happened-before relation usable, Lamport assigns each event a number, its logical timestamp, such that if A happens before B, A's number is smaller than B's (the so-called clock condition). The algorithm, as described in technical summaries of the mechanism, has few rules. Each process keeps a counter and increments it before each local event, including sending a message. The message goes out carrying the value of the sender's counter. On receipt, the recipient sets its own counter to the larger of its own value and the message's, and then increments it. Because equal timestamps can appear in different processes, the paper proposes breaking ties with an arbitrary ordering of the processes, such as each one's identifier, which produces a total order consistent with causality. There is an important limitation: the condition holds in only one direction. If A happened before B, then A's timestamp is smaller, but a smaller timestamp does not prove that A happened before B, since the events may be concurrent. In addition, the resulting total order is partly artificial: the tie-breaking does not reflect real causality.
Application: distributed mutual exclusion and replicated state machines
Lamport uses total ordering to solve a concrete synchronization problem: granting exclusive access to a shared resource among several processes, without a central coordinator. In the formulation of the algorithm described in summaries of the paper, a process that wants the resource puts its request, with a timestamp, in a local ordered queue and sends it to all the others. Whoever receives it enqueues the request and answers with a reply message, also timestamped. The process only enters the critical section when its request is first in the queue and it has received replies from all the others; when done, it removes the request and notifies everyone with a release message. Later analyses count 3(N-1) messages per use of the resource, for N processes, and summaries of the paper note that the scheme assumes messages are delivered reliably and in order, and that the failure of a single process can block progress. Lamport himself says the example illustrates something more general: totally ordering the requests makes it possible to implement an arbitrary distributed state machine. Each replica is a deterministic state machine: given the same initial state and the same sequence of inputs, it always produces the same results. So, if all replicas process the same inputs in the same total order, they reach the same decisions. He notes that many people think the paper is only about causal ordering or only about mutual exclusion, and miss this point.
Anomalous behavior, physical clocks, and legacy
The paper also discusses what happens when the system interacts with the world outside it. If causality passes through an external channel, which the logical clock cannot see, the total order may contradict the order in which users perceive the events, which the paper treats as anomalous behavior. To avoid it, Lamport introduces physical clocks that obey bounds on drift and on the difference between each other, kept synchronized by the messages exchanged; in summaries, the achievable precision depends on clock drift and message delays. The exact values of the paper's inequalities were not verified here and are not asserted in this summary. Lamport says the work originated from a note by Paul Johnson and Bob Thomas based on message timestamps, and that he saw in it a total order of events consistent with causality. The paper received the PODC Influential Paper Award in 2000 (later renamed the Dijkstra Prize) and the SIGOPS Hall of Fame Award in 2007, and Lamport calls it his most cited paper. As a technical legacy, Lamport timestamps are the conceptual starting point of vector clocks, which generalize the idea and recover the reverse direction of the condition: comparing two vector clocks allows concluding causality.
See the ideas at work
Practice the designs that use this paper in the System Design school.