The encyclopedia · R&D & Science · Technical decision · 1989–2001
Paxos reached consensus in failing networks by intersecting majorities
Lamport's Paxos lets machines agree even when some fail: any two majorities share an acceptor, so only one value can win.
Digital Equipment Corporation
The solution
Leslie Lamport wrote the Paxos algorithm in 1989 as 'The Part-Time Parliament', a parable of a legislature whose members wander in and out while its record stays consistent. He submitted it in 1990, but it appeared in ACM Transactions on Computer Systems only in May 1998.
The core problem is consensus: a group of machines must choose one value even though processes fail, restart and messages get lost or delayed. The naive fix, letting one acceptor decide, dies with that machine; majority voting works only because any two majorities share a member.
Paxos exploits that intersection. Proposals carry ever-higher numbers, acceptors promise to ignore old ones, and a value is chosen when a majority accepts it. The overlap of quorums makes it arithmetically impossible for two values to be chosen, so the system stays safe without any machine being infallible.
Why it worked
- Any two majorities share an acceptor, blocking two winners
- Numbered proposals let acceptors safely change their minds
- Safety needs no clocks, only quorum arithmetic
- The state-machine framing made it usable in real systems
What can be applied
Make any two agreeing groups overlap: intersecting quorums turn an unenforceable guarantee into arithmetic that survives crashes, delays and restarts.
Aftermath
Paxos became the canonical answer to distributed consensus: Lamport's 2001 paper 'Paxos Made Simple' restated the idea in plain English, and the algorithm was adopted in production systems such as Google's Chubby lock service and early Spanner, where its quorum structure keeps replicas consistent under failures.
Sources
spotted an error? The archive wants to know.