CS PAPERS DEEP-READ · PAPER 31
Leslie Lamport · Massachusetts Computer Associates · CACM 1978
In 1978, Leslie Lamport pinned down an idea that is now everywhere: in a system of independent computers, how do you say "this thing happened before that thing"? Today, when you send a payment or a message, several machines are usually working together behind the scenes; they must agree on "what happened first," or the books won't balance. Lamport gave the first clean answer, and this paper became the intellectual origin of the whole field of distributed systems.
You and a friend are in two cities, each looking at your own wristwatch — but the two watches don't quite agree, and they drift further apart over time. Now decide whether "the letter you mailed this morning" happened before or after "something that happened on your friend's end." Just comparing the two watches is hopeless. Networked computers are exactly like this: each has its own quartz clock, all of them drift, and network messages arrive after unpredictable delays. With no single clock everyone trusts, "before and after" becomes a genuine problem.
Lamport's twist: don't compare clocks — look at who can influence whom. The key handle is messages: a message must always be sent before it can be received. So the moment A sends B a message, you can be sure "A's event came before B received it." Within one machine, whatever ran first is first. Chain these together and you get a web of "who is before whom" (this is the happens-before relation).
The elegant part: some events can't influence each other at all (no message ever passed between them), so we simply call them "simultaneous / concurrent" and refuse to force an order — which is actually more honest.
Give each machine a "ticket counter" (not a clock — just a number that keeps growing). The rules fit in three lines: every local event bumps the counter by 1; when you send a message, stamp your current number on the envelope; when you receive one, jump your number above the number on the envelope.
It's like a post office postmark: mailing a letter stamps a number; the receiver sees "ah, this was mailed as #7" and pushes their own counter to #8 and onward. That way whenever one event can influence another, its number is guaranteed to be smaller — the ticket counter sorts "before and after" for you. Smaller number goes first; if two collide, break the tie by machine ID as a referee. So machines scattered across the world can produce one single ordering that everyone agrees on.
With that shared ordering, you can make several backup machines process the same batch of commands in the same order — same input, same sequence, so each computes the same result and they stay forever consistent. This recipe for "keeping multiple replicas in lockstep" is the common ancestor of today's bank databases, cloud storage, and famous algorithms like Paxos and Raft. A 1978 counter trick holds up half the distributed-systems world.
One honest caveat: the ticket counter only guarantees "if there's influence, the number is smaller"; the reverse doesn't hold — two events with different numbers need not have any real ordering; they may just happen to collide while being completely unrelated. Untangling that layer needs the heavier "vector clocks" that came later.
With no clock everyone trusts, stop comparing clocks — define order by "a message is always sent before it's received," give each machine an ever-increasing ticket number so causally related events get smaller numbers, add a tie-breaking referee, and machines a world apart can produce one agreed-upon ordering — staying independent yet always consistent. This is the intellectual origin of distributed consistency.
Want the space-time diagram, the logical-clock update rules, and that no-coordinator mutual-exclusion algorithm? → switch to the deep read
Lamport argued that a distributed system has no — and should not rely on a — single physical clock; the order of events should be defined by a causal relation, "can one event influence another." He gave the happens-before partial order, a logical clock implementable with nothing but counters (now called Lamport timestamps), and a way to extend that partial order into a total order — letting scattered, independent machines process the same commands in the same order and stay consistent. This state-machine replication idea is the root of Paxos, Raft, and every strongly consistent distributed system since.
Written by Leslie Lamport at Massachusetts Computer Associates, published in Communications of the ACM, July 1978. It carried Einstein's special-relativity insight — that the ordering of events is not absolute — into computing; it launched a whole line of work: vector clocks, the Chandy–Lamport distributed snapshot, Paxos, state-machine replication. It is one of the foundational works behind Lamport's 2013 Turing Award and among the most-cited papers in computer science.
On a single machine, "what happened first" is settled by the CPU's clock — obvious. But wire many machines together over a network and trouble starts: each machine has its own quartz clock, all of which drift (running a touch fast or slow), and message delays swing unpredictably. How do you decide whether "the debit on machine A" or "the balance check on machine B" happened first? By comparing two watches? The watches don't agree, and synchronizing physical time tightly enough is both expensive and unreliable.
And at a deeper level: many events have no objective order at all — they happen independently, in different places, at nearly the same instant, and asking "which first" is meaningless. Yet unless replicas can agree on "in what order to process requests," the data will diverge. What Lamport solved is precisely this first-principles question: how to talk about order in a world with no shared time.
Lamport reframed the question: don't ask "whose watch is earlier," ask "who can influence whom." He defined a "happens-before" relation → using just three rules and no physical time at all: ① within one process, an earlier event → a later one; ② the "send" of a message → its "receive" (information must be sent before it can be received); ③ transitivity: a→b and b→c imply a→c. If a→b, then a could have influenced b.
The crux: this is a partial order, not a total one. Some pairs of events can't reach each other (no message passes), and those are concurrent — with no before or after. This echoes relativity: for "concurrent" events, different observers can legitimately disagree on the order, and forcing one is simply wrong.
How does a machine compute this order on its own? Give process Pi a counter Ci that stamps a number Ci(a) on every event a. The goal is the Clock Condition: whenever a→b, we must have C(a) < C(b). Two implementation rules guarantee it:
Cj := max(Cj, Tm) + 1 (Tm is the sender's timestamp carried by the message) — ensuring a "receive" always outnumbers its "send."Plainly: it's a post-office postmark. Mailing stamps a number; the receiver sees #7 on the envelope and pushes their counter to #8 before continuing. Remember it is not a clock — it's a ticket counter: it only guarantees "causally related events increase in number" and measures no real time.
A logical clock still gives only a partial order — two concurrent events can share a number. To make every machine produce one identical, unique ordering, add a tie-break rule: when numbers are equal, order by process ID (say P1 < P2 < P3). Now any two events have a unique before/after, giving a total order consistent with causality (written ⇒). Plainly: look at the ticket number first; if they collide, look at the ID.
With a total order, Lamport gave a mutual-exclusion algorithm with no central coordinator (deciding who may use a shared resource): to request it, broadcast a timestamped "request" to everyone and record it in your own queue; on receiving a request, enqueue it and reply with a timestamped acknowledgment; when done, broadcast a "release" and everyone removes it. The rule: you get the resource if and only if your request sits at the front of the queue (ordered by the total order ⇒) and you have received a later-timestamped message from every other process.
Because everyone maintains the same queue in the same total order, all processes necessarily agree on "whose turn it is" — no center needed. Abstract this and you get the far-reaching replicated state machine: write the service as a deterministic state machine, and have every replica execute the same commands in the same total order; same input, same order, therefore the same state. That is the universal recipe for fault-tolerant replication.
Honest note: this mutual-exclusion algorithm has premises — messages between two processes are never lost and arrive in the order sent (FIFO reliable channels), and it does not tolerate crashes. Those very premises are the gaps that later fault-tolerant consensus (Paxos and kin) had to fill.
Logical clocks only see messages inside the system. If two events become causally linked through a channel outside it (a person phones someone in another city to act), the system can't see that link, and the total order it computes may contradict reality — this is anomalous behavior. To plug the hole, either feed the external order into the system, or switch to physical clocks synchronized well enough. The paper closes with a theorem on how tightly physical clocks must be synchronized (as a function of the minimum message delay) to rule out anomalies — the derivation is omitted here; the intuition is that a clock's error must not be so large that a message appears to "arrive before it was sent."
This is a theory paper with no benchmarks. Its "results" are constructs that became bedrock: the happens-before partial order, Lamport logical clocks, the recipe for extending a partial order into a total one, and a provably correct distributed mutual-exclusion algorithm (about 3(N−1) messages per request, no central node), which in turn establishes that state-machine replication works; the physical-clock section adds a provable synchronization bound. Its value isn't in a number but in being the first to make "time and order in a distributed system" precise and give an implementable mechanism.
It set the notion of time for distributed systems. Happens-before and logical clocks became textbook standard (the industry simply says "Lamport timestamps"); state-machine replication became the universal fault-tolerance paradigm, leading straight to Paxos (also Lamport's), Raft, ZooKeeper, and every strongly consistent database — Google Spanner's TrueTime is precisely the industrial answer to this paper's closing question of "how tightly can physical clocks actually be synchronized." It also spawned vector clocks, the Chandy–Lamport distributed snapshot, and causal consistency. Cited tens of thousands of times, it is a core contribution behind Lamport's 2013 Turing Award.
a→b implies C(a)<C(b), but not the converse — a smaller number alone can't tell you two events are causally related, nor whether they are concurrent or ordered. Capturing causality exactly needs the later vector clock (Fidge / Mattern, 1988): a→b if and only if V(a)<V(b).① In one line: a distributed system has no shared clock, so define happens-before by "a message is sent before it's received," then extend it into a total order with logical clocks.
② The pain: many machines with drifting quartz clocks and variable delays make "who came first" undecidable, so replicas can't agree on a processing order.
③ happens-before (→): process order + "send→receive" + transitivity; events that can't reach each other are concurrent, left unordered (a partial order, echoing relativity).
④ Logical clocks: one counter per process, +1 per local event (IR1), max(self, incoming)+1 on receive (IR2), so causally related events strictly increase — a ticket counter, not a clock.
⑤ Total order: break ties by process ID, yielding one unique ordering ⇒ everyone agrees on.
⑥ Killer app: no-coordinator distributed mutual exclusion; abstracted, it's the replicated state machine — same order + same commands → same state, the universal recipe for fault-tolerant replication.
⑦ Impact: Lamport timestamps became textbook standard; state-machine replication leads to Paxos, Raft, Spanner; it spawned vector clocks, distributed snapshots, causal consistency.
⑧ Limits: clocks are one-directional (small number ≠ causality; need vector clocks); the mutex algorithm needs FIFO and is not fault-tolerant; the order is arbitrary among concurrent events; the physical-clock part is theoretical.