Paxos Made Simple (Lamport, 2001)

Leslie Lamport, dated 01 Nov 2001, 14 pages (ACM SIGACT News 32(4)). The abstract is one sentence:

“The Paxos algorithm, when presented in plain English, is very simple.”

The author rewriting his own paper because the first version did not land. The introduction says so: Paxos “has been regarded as difficult to understand, perhaps because the original presentation was Greek to many readers.” Same algorithm as part-time-parliament, no island, no archaeology. This is the version the field actually learned from, and the source of the vocabulary everyone now uses.

Both papers are held. See paxos for the algorithm itself.

The contribution is the derivation, not the algorithm

part-time-parliament states conditions B1–B3 and proves they work. This paper derives them, and claims the derivation is forced: the consensus algorithm “follows almost unavoidably from the properties we want it to satisfy.”

The chain is short enough to follow in one sitting, and each step exists because the previous one broke:

Majority quorums, in one line — “any two majorities have at least one acceptor in common.”
P1: an acceptor must accept the first proposal it receives. Needed or nothing is ever chosen when only one proposal exists.
P1 then forces acceptors to accept multiple proposals (numbered), because otherwise two simultaneous proposals can split the acceptors with neither reaching a majority.
P2 → P2a → P2b → P2c. Each is a strengthening of the last, adopted because a counterexample killed the weaker form. P2 constrains what gets chosen; P2a constrains what any acceptor accepts; P2b constrains what any proposer issues; P2c states the checkable version — before issuing proposal n with value v, some majority must have either accepted nothing below n, or v must be the value of the highest-numbered proposal accepted among them.

Forbidding what you cannot observe

P2c requires a proposer to know about accepts that have not happened yet. The paper’s move:

“Since it’s not possible to predict the future, the proposer controls it by extracting a promise that there won’t be any such acceptances.”

That is Phase 1 in a sentence, and it generalises well past Paxos: when you cannot observe the future, forbid it. Chubby’s master lease (chubby-lock-service) is the same trick with a clock attached.

The two phases, which is what the world actually uses

Phase 1 — a proposer sends prepare with number n; an acceptor that has seen nothing higher replies with a promise not to accept anything below n, plus the highest-numbered proposal it has already accepted. Phase 2 — the proposer sends accept for n with either its own value or, if any promise carried one, the value from the highest-numbered accepted proposal; acceptors accept unless they have since promised higher.

Three roles are named here for the first time in plain terms: proposers, acceptors, learners. The prepare/promise/accept/accepted vocabulary in every later implementation comes from this paper, not from the 1998 one.

Progress, stated as an actual livelock

The 1998 paper says progress needs timing. This one shows exactly how it fails: proposer p finishes phase 1 at n₁, q finishes phase 1 at n₂ > n₁ so p’s accepts are ignored, p retries at n₃ > n₂ so q’s accepts are ignored, “and so on.” Two live, correct, non-faulty proposers can starve each other forever.

The fix is to elect one distinguished proposer. And the consequence is stated without hedging:

“The famous result of Fischer, Lynch, and Patterson implies that a reliable algorithm for electing a proposer must use either randomness or real time—for example, by using timeouts. However, safety is ensured regardless of the success or failure of the election.”

That last clause is the design principle behind every leader-based replicated system in this spoke. A bad election costs availability and never correctness — which is why leader election can be best-effort, and why two nodes briefly believing they are leader is survivable.

Provenance

T1, primary, read locally from the PDF. The arriving link carried a Facebook fbclid parameter, stripped here. freshness: stable.

Not a duplicate of part-time-parliament, and not a replacement: the 1998 paper carries the multi-decree construction, the quorum generalisation and the state-machine framing at length; this one carries the derivation, the two-phase vocabulary and the livelock. Both are held, and paxos is the page that reconciles them.

paxos · part-time-parliament · consensus · chubby-lock-service · leslie-lamport · podc-lecture-notes · operational-databases

Cross-spoke. That an author had to rewrite his own paper in plain English before the field could use it is a data point for ../research-wiki’s diffusion-and-adoption cluster: the idea did not spread until its presentation changed, with the content held constant. Noted there rather than argued here.