The Part-Time Parliament (Lamport, 1998) — Paxos

Leslie Lamport, ACM TOCS Vol. 16, No. 2, May 1998, pp. 133–169, written at Digital Equipment Corporation, with minor corrections in August 2000. 33 pages. The paper that introduced Paxos, named for the fictional Greek island whose part-time legislators keep a consistent record while wandering in and out of the chamber.

It is written as archaeology, complete with a fabricated editor’s note claiming the submission “was recently discovered behind a filing cabinet in the TOCS editorial office” and that the author is unreachable, “currently doing field work in the Greek isles.” The device delayed the paper’s reception by years, and the author eventually re-explained the algorithm himself in paxos-made-simple — opening it with the admission that “the original presentation was Greek to many readers.” Section 4 of this paper is its own translation, and the text tells computer scientists to read that section first.

The split happened 2026-08-10, as this page predicted: paxos-made-simple arrived and the algorithm now has its own page at paxos. This page keeps what is specific to the 1998 paper — the derivation from a fictional parliament, the multi-decree construction, and the state-machine framing at length. The plain-English derivation and the prepare/accept vocabulary are on the 2001 paper.

The safety argument is three conditions

The single-decree Synod chooses one value through numbered ballots, each with a quorum of priests, and each priest either votes for the ballot’s decree or does not. All of correctness follows from three conditions on the set of ballots:

B1. Each ballot has a unique ballot number. B2. The quorums of any two ballots have at least one priest in common. B3. For every ballot B, if any priest in B’s quorum voted in an earlier ballot, then B’s decree equals the decree of the latest of those earlier ballots.

B2 is the reason consensus systems count majorities. Not because a majority is democratic, but because any two majorities of the same set must share a member, and that shared member is what carries a decision from the ballot that made it into every ballot that follows. B3 is what that member is for: a new ballot is not free to choose, it must adopt whatever the most recent voter already voted for. Once a ballot succeeds, no later ballot can decide anything else.

That is the whole of safety, and it does not mention time, failure, or messages.

Progress needs time, and the paper knows why

Consistency is guaranteed; termination is not. The Paxons “realized that any protocol to achieve the progress condition must involve measuring the passage of time,” with the footnote — the paper’s best joke — that “many centuries were to pass before a rigorous proof of this result was given,” citing Fischer, Lynch and Paterson (1985).

So consensus‘s framing was right and now has its primary source: Paxos is the branch that buys its way out of FLP by adding timing. Election of a president and initiation of ballots are timer-driven and work with timers of known bounded accuracy. If two nodes both believe they are president, safety still holds — only progress suffers.

Multi-decree: where the leader comes from

Passing a sequence of decrees is logically one Synod instance per decree number. The move that makes it practical is that in the Synod protocol the president does not choose the decree or the quorum until step 3, so a newly elected president can send one message that serves as the first phase for every instance at once, and a legislator can answer with one message covering all of them (finite, since he has voted in finitely many).

This is why a steady-state Paxos commit costs one round trip rather than two, and it is the origin of every “leader” in the replicated systems this spoke documents. The paper is candid that leader selection is unresolved — the section on picking a president ends with the debate’s “outcome is not known; no record exists of the presidential selection protocol that was ultimately used.” The part production systems find hardest is the part the paper declines to specify.

Section 4: the state machine approach

The translation out of the fiction. Servers hold replicas; a client request becomes a state-machine command; a general algorithm ensures every server sees the same command sequence, so all produce the same responses and state changes from the same initial state. The database example distinguishes a slow read (passes a decree) from a fast read (reads the local replica, possibly stale) — the consistency choice from consistency-models, stated in 1998 as an interface decision.

The claim underneath is a design argument rather than a result:

“When designing a new system, only the state machine is new… Functions are much easier to design, and to get right, than distributed algorithms.”

The sentence that pairs it with the Byzantine paper

Comparing Paxos to his own earlier byzantine-tolerant algorithms, Lamport writes that the Paxon protocol

“is less robust and less expensive than the earlier algorithms. It does not tolerate arbitrary, malicious failures, nor does it guarantee bounded-time response. However, consistency is maintained despite the (benign) failure of any number of processes and communication paths.”

byzantine-generals-problem ends by saying the only way to reduce the cost of tolerating arbitrary failure is to assume something about how things fail. This is the same author, sixteen years later, taking exactly that discount and naming both halves of it. The two papers are one argument: 1982 prices the general case, 1998 buys the cheap one and says what it gave up.

Note what survives the discount and what does not. Benign failure of any number of nodes and links still preserves consistency — Paxos does not have a 3f+1 count because it is not defending against lies, only against absence. What it loses is bounded-time response and any defence against a node that is corrupted rather than dead.

Provenance

T1 — the primary paper, from Microsoft Research’s copy of the TOCS article, extracted locally from the PDF. The arriving link carried a Facebook fbclid parameter, stripped here. Results are permanent; freshness: stable.

consensus (Paxos as the add-timing branch out of FLP) · byzantine-generals-problem (the same author pricing the other side of the trade) · consistency-models (slow vs fast reads) · podc-lecture-notes (the secondary account that reached this spoke first) · paxos · paxos-made-simple · chubby-lock-service · leslie-lamport · operational-databases

Cross-spoke: ../research-wiki holds tla-plus, the language Lamport later built for specifying exactly this kind of protocol.