Time, Clocks, and the Ordering of Events in a Distributed System
Leslie Lamport1978Communications of the ACM
Read it on doi.org(opens in a new tab)Why this one
Eight pages, written in 1978, and still the cheapest way to fix the single most common bug in a distributed system: assuming that two machines agree on what happened first. Lamport's move is to stop asking for a global clock and define ordering from causality instead - if A could have influenced B, then A came before B, and if neither could have influenced the other they are simply concurrent and no ordering exists. The logical clock that falls out is three lines of code. Read it slowly; the payoff is that 'eventually consistent', vector clocks, happens-before and every conflict-resolution scheme you meet later stop being jargon and become obvious consequences of one definition.
What to take away
- Concurrent is a real answer. Some pairs of events genuinely have no order and no amount of engineering will give them one.
- A logical clock costs a counter and a max(); wall-clock timestamps cost you correctness.
- Read this before Dynamo - vector clocks make no sense without it.
Reads with
- Dynamo: Amazon's Highly Available Key-value Store
vector clocks turn its write conflicts into explicit causal histories
- Spanner: Google's Globally-Distributed Database
it buys a real time ordering service instead of accepting causal partial order
- Paxos Made Simple
consensus is the next step when concurrent events must become one agreed order