CS PAPERS DEEP-READ · PAPER 44
Leslie Lamport · Microsoft Research · ACM SIGACT News · 2001
In 2001, Leslie Lamport re-told, in plain English, the Paxos algorithm he had invented — a way for a group of machines scattered across a network they can't trust to reach a single, never-reversed agreement on some one thing. Almost every large online service you use has it hiding underneath: how a database picks its primary node, whether a piece of data really got written, who's in charge of a cluster — these "every machine must agree on the same answer" problems are solved by consensus algorithms like Paxos.
Picture a group of friends trying, by phone, to settle on one restaurant — but calls drop at random, people suddenly fall asleep and wake up a while later (machines crashing and rebooting), and messages arrive late or twice. The requirement is brutal: everyone must end up at the same place, and once it's settled, no one may ever believe it was somewhere else. The difficulty: there's no "center everyone trusts," the messages are unreliable — so how do you rule out "half the group thinks it's A, half thinks it's B"? (One assumption: nobody lies here; machines only crash, they don't deliberately send false messages — lying is a different, harder problem.)
Paxos's answer is two rounds of talking + a queue ticket. Anyone who wants to propose first draws an ever-larger ticket number (a later ticket is always bigger than an earlier one). In the first round they take that ticket to a majority of people and ask, "will you promise to me?"; only in the second round do they formally push their chosen restaurant and ask that majority to "accept" it. A restaurant accepted by a majority counts as "settled."
Two rules hold everything together. First: everyone honors only the bigger ticket — once you've promised to ticket 5, you ignore anyone with a smaller number. Second, and the clever one: before a proposer pushes their own restaurant in round two, they must ask around first; if anyone says "I've already accepted some place," the proposer must switch to championing that place and drop their own.
Add the magic of "majority": any two groups that each form a majority must share at least one person. So once a restaurant has been settled, anyone asking around later is guaranteed to run into that "overlapping person," hear from them that it's already settled, and dutifully carry it forward. The decision is therefore forever unique and never overturned.
This "ask around first, then push, honor the bigger ticket, reuse the old value" discipline became the bedrock of nearly every strongly-consistent distributed system: Google's Chubby lock service, the Spanner global database, and the primary-election logic in all sorts of databases are Paxos at heart. The later, easier-to-follow Raft is a repackaging of the same ideas.
To make a set of unreliable machines agree on one thing: draw an ever-increasing ticket, ask a majority around first, honor whoever's ticket is bigger — and before pushing your own value, reuse any value others have already accepted. Because "any two majorities must overlap," a value once settled can never be overturned. Honest caveat: it's famously hard to understand, it survives crashes but not lies, and plain Paxos can stall when two proposers keep grabbing bigger tickets from each other (fixed by electing a single "leader").
Want the two-phase flow diagram, why majorities must overlap, and how it becomes a real system? → switch to the deep read
Paxos is a consensus algorithm that lets multiple processes agree on a single value in an asynchronous distributed system where "messages can be lost, duplicated, or delayed, and machines can crash and restart, but nobody lies." Using two mechanisms — proposal numbers and majorities (quorums) — it guarantees that safety always holds (at most one value is ever chosen, and once chosen it never changes), while handing the liveness it can't co-guarantee (some value is eventually chosen) to "elect a single leading proposer." This 2001 "Paxos Made Simple" is Lamport's plain-English rewrite of his own opaque 1998 "The Part-Time Parliament," and it is the consensus core of nearly every strongly-consistent distributed system (Chubby, Spanner…).
The author is Leslie Lamport (Microsoft Research). "Paxos Made Simple" appeared in ACM SIGACT News in 2001, a minimal restatement of his 1998 "The Part-Time Parliament" — told as an allegory about a Greek island parliament that almost nobody understood (the algorithm actually took shape around 1990). It builds on Lamport's own logical clocks (1978) and the consensus problem, and works around the FLP impossibility (1985); downstream it was deployed heavily in industry (Chubby, ZooKeeper's Zab, Spanner) and directly prompted the 2014 Raft, which sold itself on "understandability." Lamport won the 2013 Turing Award for this line of distributed-systems work.
One of the most basic problems in distributed systems: how does a group of machines agree on one value — say, who the primary is, or what the next log entry should be. It sounds simple; the trouble is a brutally unfriendly environment: the network drops, reorders, and duplicates messages; machines crash and restart (and after restarting must still remember the promises they made before crashing). We want three ironclad rules: only a proposed value can be chosen; in the end only one value is chosen; and if nothing was chosen, no one may believe otherwise.
Worse is the theoretical ceiling — FLP impossibility proves that in a purely asynchronous model where even one process may crash, no deterministic algorithm can guarantee both "always chooses a result" and "never chooses wrongly." So the practical trade-off is: safety (never choose wrongly) must never break; liveness (eventually choose) may be redeemed later, once the network behaves. Paxos is the classic answer to that trade-off. Earlier schemes like two-phase commit either couldn't tolerate a crashed coordinator or would block; Paxos was the first to give a minimal protocol that tolerates a minority of crashes and is rigorously proven safe.
Paxos splits processes into three roles (one process can play several): proposers put forward candidate values; acceptors vote; learners find out the result. The core rule is minimal: a value accepted by a majority of acceptors is "chosen."
Using a majority rather than everyone is the paper's key design: any two majorities must share at least one common member. That overlapping member acts like a "witness" — once it has taken part in a decision, it can leak that decision into any later inquiry, making it impossible for two different values to each gather a majority in mutual ignorance.
Each proposal carries a unique, increasing number n. The protocol runs in two rounds (see Fig 2):
prepare(n) to a majority of acceptors. An acceptor that hasn't promised to any larger number makes a promise: it will no longer accept any proposal numbered below n; and it reports back the highest-numbered proposal value it has already accepted (if any).accept(n, v). And there's an ironclad rule for v: if any promise reported an "already-accepted value," v must be the highest-numbered one among them; only if nobody reported any value may the proposer fill in the value it wants. An acceptor receiving accept(n,v) accepts it, as long as it hasn't promised to a larger number in the meantime.Put the two rules together and Phase 2's value rule is really: v = highest-numbered accepted value reported by the majority (if any), else free choice. It is exactly this "before pushing your own value, ask around first and reuse any already-accepted value" rule, combined with "majorities must overlap," that guarantees — once some value v is chosen (accepted by a majority), every higher-numbered proposal thereafter also carries v. Hence "the chosen value is unique and never changes." (The paper derives this rigorously through a chain of invariants P1 / P2a / P2b / P2c; but the intuition is just the sentence above.)
Each acceptor need only persist two things to stable storage: the largest prepare number it has promised to, and the highest-numbered proposal it has accepted, plus that value. After a crash-restart, those two numbers are enough to restore its earlier promises and never renege — which is the key to fault tolerance.
Safety aside, Paxos can stall on liveness: two proposers may keep grabbing bigger numbers — p gets promises with n1, q preempts with n2>n1 (voiding p's Phase 2), p reclaims with n3>n2… back and forth, and nothing ever gets chosen (precisely the scenario FLP says you can't escape). The fix is to elect a single "leading proposer" (leader) and let only it issue proposals. Leader election need not be perfect — a wrong choice only hurts efficiency, not safety; as long as there's eventually a stretch of time with one stable leader, a value gets chosen.
The above only settles "one value." Real systems need to settle a whole sequence of commands (a log): just run a separate Paxos instance for each slot of the log. The optimization: a stable leader can do Phase 1 once for a whole range of future slots, after which each new command needs only a single Phase-2 round-trip — this is Multi-Paxos. Wrap it around a "deterministic state machine" (each replica runs the same command sequence in the same order) and you get state machine replication: a service that tolerates a minority of crashes yet, from the outside, is as strongly consistent as a single machine. This is how Paxos is actually used in industry.
This is a theory paper — no datasets, no benchmarks. Its "result" is a rigorously proven correctness guarantee and the way it's derived. Starting from "what does safety actually require," the paper reasons step by step to show the two phases (prepare / accept) are the necessary and sufficient minimal mechanism, proving: under any message loss / duplication / delay and any minority of acceptor crashes, safety always holds (at most one value chosen, chosen values immutable); while liveness is achieved given "a single stable leader + messages eventually delivered." It candidly acknowledges the FLP boundary — under pure asynchrony you can't guarantee termination, which is not a flaw but a theoretical necessity. This "derive the algorithm from the requirements" style is itself part of why it's so heavily cited and became a textbook model.
Paxos is the foundational distributed-consensus algorithm, all but defining "how to do strong consistency on machines that crash." Google's Chubby lock service, the Spanner global database, Megastore, and other core systems all have Paxos as their consensus core; ZooKeeper's Zab and the Raft used by etcd / Consul are near relatives or repackagings of it. It's fair to say nearly every "strongly consistent + highly available" distributed store today traces its fault-tolerance skeleton back here. It's also one of the works behind Lamport's 2013 Turing Award.
① Problem: make a set of machines that crash, can only talk over an unreliable network, but never lie, agree on a single value — uniquely and irreversibly.
② Trade-off: FLP rules out having both — Paxos keeps safety always true and redeems liveness once the network recovers.
③ Definition of "chosen": a value accepted by a majority of acceptors.
④ Key design one: the majority — any two majorities overlap, and that overlap is the "witness" preventing two coexisting values.
⑤ Key design two: two phases (prepare/promise → accept/accepted) + increasing proposal numbers; acceptors honor only the bigger number.
⑥ The heart of safety: before pushing its own value a proposer must ask around and reuse the highest-numbered already-accepted value — so a chosen value never changes.
⑦ Fault-tolerance detail: an acceptor need only persist "largest promised number" and "highest accepted proposal"; it never reneges after a restart.
⑧ Liveness via a leader: elect one leading proposer to break the "duel"; election need not be perfect and never affects safety.
⑨ Practical form: Multi-Paxos (one instance per slot, a stable leader skipping Phase 1) + state machine replication — the real industrial use.
⑩ Impact and limits: bedrock of Chubby / Spanner and forerunner of Raft; but hard to grasp, far from a running system, and survives crashes not lies.