Time, Clocks, and the Ordering of Events in a Distributed System
"Before" made precise without a clock: a partial order built out of the messages a system already sends.
Read the original ↗This is the paper that made "before" a word you can use precisely about a distributed system. It is also the paper most often cited for a guarantee it explicitly says it cannot provide, and its more influential half is the one almost nobody remembers is in it - a claim Lamport has made himself, in writing, about his own most-cited paper.
Included with a plan
This discussion is included with a plan. The first three lessons of every track are free, with their boards and videos. A plan unlocks every lesson, board, video, lab and paper for one price.
Related on chalk
The same idea as a board, lab, video or lesson.
- BoardThe Hard Part - Timedrifting clocks and a single source of now - the problem the paper answers by not using a clock
- BoardWhen Machines Failpartial failure and unreliable clocks, the demons this paper assumes away
- BoardWho Holds the Penone writer at a time, which is the mutual-exclusion problem the paper's worked example solves
- BoardIdempotency and Fencinga rising token that rejects a zombie's write - a logical clock doing a day's work
- BoardThe Copy Clerksreplicas fed the same changes in the same order, which is the paper's second half
- BoardReplicationstatement-based replication breaking on NOW() and RAND() - the determinism a replicated state machine needs
- BoardPartitionsordering promised inside a partition and nowhere else: a partial order, shipped
- BoardNeither OT nor CRDTconcurrent edits that must converge, answered by putting one server in charge of the order
- LabWho holds the penthe split brain a fence prevents, which is one counter deciding who is stale
- LabThe copy clerksreplicas a beat behind - what a partial order looks like from a reader's chair
- LabThe two ledgers must agreetwo logs that must agree on one order, and the coordinator that makes them
- VideoConsensus: who holds the penone pen, five clerks, a fence - and the fence is a number
- VideoReplication: the copy clerksthe lag between copies, before anyone tries to timestamp it away
- VideoDistributed transactions: the two ledgers must agreethe crash that lands between two writes, which no clock resolves
- VideoThe money-movement state machine: a payment is not a row you updateone object as a chain of legal transitions; the paper's method is running that chain everywhere at once
- LessonScheduler 07: The Hard Part - TimeUses the board The Hard Part - Time
- LessonWhen Machines FailUses the board When Machines Fail
- LessonRaft 01: Leader ElectionUses the board Who Holds the Pen
- LessonRaft Capstone: EverythingUses the board Who Holds the Pen
- LessonWho holds the pen (consensus & Raft)Uses the board Who Holds the Pen
- LessonScheduler 06: Idempotency and FencingUses the board Idempotency and Fencing
- LessonKV: quorumUses the board The Copy Clerks
- LessonThe copy clerks (database replication)Uses the board The Copy Clerks
- LessonReplicationUses the board Replication
- LessonKafka 04: PartitionsUses the board Partitions
- LessonFigma - the case studyUses the board Neither OT nor CRDT
Further reading
Read the original for the full argument and its evidence.
- The paper (PDF) ↗Communications of the ACM, July 1978, eight pages. The first half is the clocks; the section on anomalous behaviour is where it turns honest, and the physical-clock section is the one to read last and slowly.
- Lamport's own note on it ↗His retrospective on his publications page: where the idea came from, why he thinks the interesting part is trivial, and his complaint that nobody notices the state machines.
- Virtual Time and Global States of Distributed Systems (PDF) ↗Later work, 1988: vector clocks, which restore the concurrency information a Lamport timestamp throws away, and the reason every conflict-detecting store carries one.