Time, Clocks, and the Ordering of Events in a Distributed System
1978 · Communications of the ACM · ~12 min read
Read the original paperMachines have no shared clock, so "which happened first" has no obvious answer. This paper defines the only order that matters and shows how to compute it.
The problem: “before” stops meaning anything
On one computer, “which happened first” is a question the hardware answers for you. Two instructions run in order; a timestamp from the system clock settles any dispute. Put the program on two computers connected by a network and that comfort disappears. Each machine has its own clock, the clocks drift apart by milliseconds a day, and a message between them takes an unpredictable amount of time to arrive. Compare timestamps across machines and you get answers that are not merely imprecise but impossible: a reply recorded as arriving before its request was sent.
This matters because almost everything a distributed system must get right is a question of order. Did the withdrawal come before the deposit? Did this replica see the delete before the re-insert? Which of two conflicting updates should win? In 1978, Leslie Lamport asked what “before” could possibly mean when no clock can be trusted, and found that the answer was sitting in the structure of the system itself.
The idea: order comes from causality, not from clocks
Lamport’s move was to stop asking the clocks and ask the messages. Two facts about any system are beyond dispute. First, within a single process, events happen in the order the process performed them. Second, a message is sent before it is received. Chain those facts together (if a happened before b and b before c, then a before c) and you have a relation he called happened-before, written →.
The relation has a hole in it, and the hole is the point. If no chain of messages connects two events on different machines, neither happened before the other. They are concurrent: not simultaneous, just unordered, and no amount of clock accuracy would change that, because nothing either event did could have influenced the other. Lamport’s claim is that this partial order is the only order a distributed program can ever depend on.
How it works: a counter that respects the arrows
Having defined the order, the paper shows how to compute something consistent with it using nothing but a counter in each process, a logical clock. Three rules:
- Before every event, a process increments its counter.
- Every message carries the sender’s counter value.
- On receiving a message, the process sets its counter to one more than the larger of its own value and the value in the message.
That is all. The guarantee is that if a → b then C(a) < C(b): the clock never contradicts causality. The converse is false, and it is the most common misreading of the paper: a smaller Lamport timestamp does not mean the event happened first, only that it did not happen after. To tell concurrency apart from order you need the vector clocks that Fidge and Mattern introduced a decade later, which carry one counter per process. The simulation below computes both, shows you only the Lamport value, and tells you the truth when you ask.
Add local events and messages, then click any two events. The number on each event is its Lamport clock; the verdict below uses the true happens-before relation.
Click two events to compare them. Each is labelled with its Lamport clock: a local step adds one, and a message carries its sender's clock so the receiver jumps past it.
The second half of the paper is easy to skip and should not be. Lamport breaks ties between equal timestamps with the process number, which turns the partial order into a total order that every process computes identically. With a total order on requests, he builds a distributed mutual-exclusion algorithm in which each process keeps a queue of requests and grants the lock to the lowest timestamp. The method generalises: feed every process the same commands in the same order, and they will reach the same state. That is the replicated state machine, and it is the idea under Paxos, Raft, and every strongly consistent database since.
What it changed
The paper gave the field its vocabulary. “Happens-before”, “concurrent”, “logical clock”, “causal consistency” and “state-machine replication” all start here. It also drew the line that later work had to choose a side of: either accept the partial order and build systems that merge concurrent updates, as Dynamo does with version vectors, or manufacture a total order with consensus, as Raft does, or close the clock problem by bounding the uncertainty, as Spanner does with TrueTime. All three are answers to the question this paper posed.
Where you meet it today
- Git. A commit’s ancestry is the happens-before relation; two branches with no common commits after the fork are concurrent, which is exactly why a merge is needed.
- Databases. A log sequence number is a Lamport clock for one node; Cassandra’s “last write wins” compares timestamps across nodes and inherits every pitfall the paper warned about.
- Dynamo-style stores and CRDTs. Version vectors and vector clocks detect concurrent writes so they can be merged instead of silently lost.
- Tracing. A distributed trace is a happens-before graph with spans as events and RPCs as messages.
The original. Read it after this page; the explainer above is a map, not a substitute.
A clear lecture on happens-before, Lamport clocks and vector clocks, with the same examples drawn out step by step.
His publication page has a short note on how the idea came about and why he thinks people cite it for the wrong reason.