The Part-Time Parliament — Papers Distilled

In one breath — the whole paper, compressed

The Paxon Parliament had to keep every legislator's ledger consistent even though legislators wandered out of the Chamber at will and messengers could delay, lose, or duplicate messages. Lamport's answer is a protocol built on three conditions over numbered ballots: every ballot has a unique number, any two ballots' quorums intersect, and a new ballot must adopt the decree of the highest-numbered earlier vote cast by any member of its quorum. Those three conditions alone prove that any two successful ballots choose the same decree, so consistency never depends on timing, on message delivery, or on there being exactly one leader. Progress is added afterwards, by electing a president and using timers, which quarantines the impossibility of asynchronous consensus into the liveness half of the design. Running one instance of the protocol per decree number, with phase one executed just once for all instances, yields a replicated state machine that passes each decree in three message delays and about 3N messages.

Before this paper — the world it landed in

By 1990 the state-machine approach was already more than a decade old: Lamport's 1978 clocks paper gave the first algorithm for implementing an arbitrary state machine, and 1984 work tolerated up to any fixed number f of arbitrary failures. Those algorithms bought bounded-time response and Byzantine tolerance at a steep price — a large f means large costs in redundant hardware, communication bandwidth, and response time, and since two servers unable to communicate is equivalent to one of them failing, exceeding f leaves servers with inconsistent copies of the state. The database community had three-phase commit, which exchanges five messages between a coordinator and the participants but chooses only between commit and abort. Fischer, Lynch, and Paterson had proved in 1985 that no asynchronous protocol can guarantee agreement at all, so any claim of progress had to be conditioned on timing assumptions. This paper was written in 1990 and only published in 1998, framed by an editorial note claiming the submission had been discovered behind a filing cabinet in the TOCS office.

The problem — what was actually breaking

Ledgers must be consistent: if one legislator has an entry for decree 132, no other legislator's ledger may hold a different entry for 132, though a legislator who has not yet learned of the decree may have no entry at all.
Consistency alone is trivially satisfied by leaving every ledger blank, so the protocol also needs a progress condition that forces decrees to actually be passed and recorded.
Legislators leave the Chamber at any time and may forget everything that is not written in their ledger, which is exactly a process crash where only durable state survives.
Messengers never garble a message but may deliver it twice, may leave on a six-month voyage before delivering it, or may leave forever, so the channel is asynchronous, lossy, and duplicating.
Because legislators refuse to curtail their outside activities, it is impossible to guarantee that any decree is ever passed, so progress can only be promised under the condition that a majority stays in the Chamber long enough.
Different legislators may each believe themselves president and run ballots concurrently, and a higher-numbered ballot may in fact have been conducted before a lower-numbered one.

Core ideas — the contributions, and why they work

Three conditions that imply consistency

Instead of designing a protocol and then proving it, the Paxons first defined three conditions on the set B of all ballots ever conducted: B1 says every ballot has a unique number, B2 says the quorums of any two ballots share at least one priest, and B3 says a ballot's decree must equal the decree of the latest earlier ballot in which any of its quorum members voted. The Lemma shows that if a ballot is successful then every later ballot carries the same decree, and Theorem 1 concludes that any two successful ballots choose the same decree. The protocol is then derived as whatever actions preserve B1 to B3, which is why every rule about promises and vote reporting has an obvious justification. This ordering matters: the mathematics really did precede the algorithm, discovered while mathematicians were attempting to prove no satisfactory protocol existed.

Intersecting quorums, not unanimity

The old Synod procedure required all priests to be present and finally failed outright when priests started wandering. Paxos replaces unanimity with a quorum that need only be a majority set, and the sole property actually required is that any two majority sets have at least one priest in common. That intersection is what makes B2 hold, and it is the reason any new ballot is forced to see the vote of at least one member of any previously successful ballot. The paper notes the definition was generalized over time — from a simple majority to sets whose total weight exceeds half the total weight, and then to symbolic weights based on attendance records — showing that the algorithm depends on intersection alone, not on counting.

The promise, and choosing the decree late

When priest q answers a NextBallot(b) message with LastVote(b, v), he reports his highest-numbered vote below b and simultaneously promises to cast no new vote in any ballot numbered less than b. The promise is what freezes MaxVote for that priest, so the value the president computes in phase one is still valid when he fixes the decree in phase two. Crucially the decree is not sent in the first round at all; the president discovers, from a majority of LastVote replies, whether some decree may already have been chosen, and only then picks one. Choosing late is what separates Paxos from a converted commit protocol and is what makes phase one reusable across decrees.

Safety without liveness, by construction

In the basic protocol every step is optional: a priest may ignore a NextBallot message, may decline to vote even when permitted, and may lose the slip of paper holding his in-flight ballot state. Failing to act, or failing to receive a message, can only prevent an action from happening, and no absent action can falsify B1 to B3, so consistency survives arbitrary crashes, message loss, and duplication. This is why the paper can add progress as a strictly separate layer of timers and leader election, and why having several priests simultaneously believe they are president can impede progress but can never make two ledgers disagree. All the murky parts of consensus are thereby pushed into the liveness half, where the FLP impossibility result lives.

One phase one for infinitely many decrees

The parliamentary protocol is logically a separate instance of the Synod protocol for every decree number, but a single elected president performs steps 1 and 2 exactly once for all of them. One NextBallot(b, n) message serves as phase one for every decree numbered above n, and a legislator's single reply carries the finite set of votes he has actually cast, since he can have voted in only finitely many instances. Afterwards each new request costs only steps 3 to 5 — BeginBallot, Voted, Success — so a decree passes in three message delays and about 3N messages, or 2N when the president piggybacks a BeginBallot on the previous decree's Success. This is the amortization that turns a five-message agreement protocol into a practical replicated log.

No-op decrees to fill gaps

A newly elected president may learn that decree 126 passed while knowing nothing about 125, because everyone who voted for 125 is out of the Chamber. Assigning a new proposal the number 125 would place it earlier in the law than a decree already passed, which can violate a citizen's expectations. The president therefore fills every gap with the traditional olive-day decree, which changes nothing, and this preserves the decree-ordering property: if decrees A and B are important and A was passed before B was proposed, then A has the lower number. The same trick converts an abort in commit-protocol terms into a harmless entry in the log.

The state-machine reading

Section 4 supplies the translation: legislator maps to server, citizen to client program, current law to database state, and passing a decree to executing a state-machine command. Because all servers obtain the same sequence of commands, they produce the same sequence of responses and states, so the only thing a designer must invent for a new system is the state machine itself — a function from command and state to response and new state. Fault tolerance and synchronization come from a standard algorithm already proved correct. As the paper puts it, functions are much easier to design, and to get right, than distributed algorithms.

How it works — the mechanism, concretely

Ballots, votes, and MaxVote

A ballot B is a four-tuple: a decree Bdec, a nonempty quorum Bqrm, the set Bvot of priests who actually voted, and a ballot number Bbal drawn from an unbounded ordered set. A ballot is successful exactly when Bqrm is a subset of Bvot, and the decree of a successful ballot is the one chosen by the Synod. A vote is a triple of priest, ballot number, and decree, with null votes assigned ballot number minus infinity so that every priest always has a defined maximum. MaxVote(b, p, B) is p's largest vote with ballot number below b, extended to a set Q by taking the maximum over its members, and B3 is exactly the statement that a ballot's decree must equal MaxVote(Bbal, Bqrm, B) whenever that is not null. The set B itself is a history variable the Paxons called a quantity observed only by the gods, since it might never be known to any mortal.

The six-step ballot

Step 1: priest p picks a ballot number b greater than lastTried[p], from the block of numbers reserved for him, and sends NextBallot(b). Step 2: priest q, if b is above nextBal[q], sets nextBal[q] to b and replies LastVote(b, v) with v equal to prevVote[q], thereby promising not to cast any new vote in a ballot numbered below b. Step 3: once p has LastVote replies from a majority set Q, he chooses decree d as required by B3 — the decree of the maximum reported vote, or anything if all reports are null — and sends BeginBallot(b, d) to Q. Step 4: a legislator with nextBal[q] equal to b casts his vote, records it in prevVote[q], and replies Voted(b, q). Steps 5 and 6: when every member of Q has voted, p writes d in his ledger and broadcasts Success(d), and each recipient writes d in his own ledger.

What must be durable, and what may be lost

The basic protocol exists precisely to shrink what a priest must write in the back of his ledger down to three items: lastTried[p], the last ballot number he tried to initiate; prevVote[p], his vote in the highest-numbered ballot in which he voted; and nextBal[p], the largest b for which he has sent a LastVote message. The appendix splits prevVote into prevBal and prevDec and adds outcome[p], the decree written in the ledger. Everything else — status, the accumulated prevVotes set, the quorum, the voters, the current decree — lives on a slip of paper that may be lost, in which case status reverts to idle and the priest simply stops conducting that ballot. Because the basic protocol conducts only one ballot at a time and ignores messages for older ballots of its own, the durable state stays constant-sized no matter how many ballots have been attempted.

President selection and the timing budget

Progress requires that someone be obliged to initiate ballots, but too many initiations also block progress, since a high-numbered NextBallot can elicit promises that kill a ballot already in flight. The Paxons measured their system: a messenger who stays in the Chamber delivers within 4 minutes and a priest who stays acts within 7 minutes, so a request and reply complete within 22 minutes. A president re-initiates a ballot only if he has not reached step 3 or step 5 within the previous 22 minutes, or if he learns of a higher ballot number — legislators bounce back nextBal[q] when they see a stale b. President selection needs only that after T minutes exactly one priest in the Chamber considers himself president; the paper's example elects the alphabetically last name present, with each priest announcing himself at least every T minus 11 minutes.

Multi-decree parliament and catch-up

A newly elected president whose ledger is complete through decree n sends NextBallot(b, n), which serves as phase one for every instance above n. Each legislator replies with all decrees above n that are already in his ledger, plus the ordinary LastVote information for decrees he has not committed, and asks the president to send him anything numbered n or below that he is missing. The president immediately runs step 3 for those instances whose decree is forced by B3, then assigns each new request the lowest decree number he is still free to choose. Gaps left behind by an unfinished predecessor are filled with the olive-day decree so the sequence stays dense and applicable in order.

Law books instead of ever-growing ledgers

As the decree list grew, legislators converted their ledgers into law books that record only the current state of the law plus the number of the last decree reflected in it — a snapshot with a log position. A legislator complete through 1298 who learns that 1299 sets the olive tax to 6 drachmas simply edits the tax entry and advances his marker; if he then hears about 1302 he writes it in the back and waits for 1300 and 1301 before applying it. To let a legislator who was away only briefly catch up without copying the whole book, the past week's decrees are kept as a list in the back. This is exactly log compaction plus a tail of recent entries for delta-based recovery.

Leases, specialists, and reading the law

Two cheese inspectors once operated at once because the replaced inspector had not heard about his replacement, so every appointment decree carries the time it was proposed and a fixed term — Dikstra is cheese inspector for 3 months, beginning at the stated time or when the previous term ends, whichever is later. Since Paxons could tell time only to within 15 minutes, an appointee whose term begins at 8:30 waits until his observations say 8:45, which is a lease with a clock-skew guard. Reads are handled by the monotonicity condition: a slow read passes a decree, a fast read just returns the local copy, and the workable middle ground is to carry decree numbers through business transactions or to route each area of the law to its single designated specialist. Multiple specialists are permitted for an area only while that area cannot change, which is how the tax specialists survive filing season.

What the paper showed — measurements and proofs

Theorem 1 proves that if B1, B2, and B3 hold then any two successful ballots have the same decree; the supporting Lemma proves the stronger statement that every ballot later than a successful ballot carries that ballot's decree, by minimal-counterexample contradiction in eleven numbered steps.
Theorem 2 proves the protocol cannot deadlock: given a ballot number b larger than every existing one and a set Q intersecting every existing quorum, a successful ballot with that number and quorum can always be added while keeping B1, B2, and B3 true.
The appendix restates the basic protocol as atomic actions over the durable and volatile variables and gives an invariant I equal to the conjunction I1 through I7 that is true initially, implies consistency via I1, the first conjunct of I6, and Theorem 1, and is preserved by every allowed action including message loss, duplication, and the Forget action.
With messengers delivering in 4 minutes and priests reacting in 7, a request-reply completes in 22 minutes, and if the doors are locked with a single president and a majority set inside, a decree is passed and recorded in every present ledger within 99 minutes; with a presidential selection requirement of T minutes the bound is T plus 99 minutes.
In steady state with a president already elected, passing a decree costs three message delays and about 3N messages for N legislators and a quorum of about N/2, dropping to about 2N messages per decree when the president combines a BeginBallot with the previous decree's Success message.
The paper positions the result against three-phase commit: both exchange five messages between coordinator and quorum, but because the Synod protocol withholds the decree until the second phase, the parliamentary version runs phase one once per president and needs only three messages per subsequent decree.

Limits and trade-offs — conceded and discovered

Conceded by the paper: the basic protocol guarantees nothing about progress at all — every action is merely allowed, never required — and the paper's own footnote points at Fischer, Lynch, and Paterson for the rigorous statement that any protocol achieving the progress condition must measure the passage of time.
Conceded by the paper: the algorithm does not tolerate arbitrary, malicious failures. A dishonest legislator sending contradictory messages, or an honest lapse of memory, can make ledgers inconsistent, and the described remedy — cycling through all laws with redundant decrees every six months to become self-stabilizing — is admitted to be poorly understood, with the author hoping future excavations turn up the manuscripts.
Conceded by the paper: there is no bounded-time response, so time cannot be made part of the machine state in the natural way that Byzantine real-time algorithms permit; under failures a command can take arbitrarily long, and a command issued later can appear earlier in the sequence of decrees.
Conceded by the paper: reconfiguration is dangerous. Membership for decree n is taken from the law as of decree n minus 3, and the progress condition still only promises progress when a majority set is present, not that one ever will be — the allegory ends with a scribe's error declaring drowned sailors the only members of Parliament, after which no decree could ever pass again and General Lampson staged a coup.
Exposed by later work: the allegorical presentation made the algorithm famously hard to absorb, which is why Lampson's 1996 explanation, De Prisco, Lampson, and Lynch's 1997 formalization, Lamport's own Paxos Made Simple (2001), and eventually Raft (2014) were written; the paper also leaves leader election, log compaction, and membership change deliberately unspecified, and implementers later reported that those unspecified parts are most of the engineering.

What it became — the systems that inherited it

Paxos became the default answer for fault-tolerant coordination in large systems. Google's Chubby lock service (Burrows, OSDI 2006) is a Paxos log with a filesystem-like interface, and the Paxos Made Live report (Chandra, Griesemer, Redstone, PODC 2007) documented that the paper's unspecified regions — leader election, log compaction, group membership, disk corruption, testing — dominated the implementation effort. Spanner replicates each shard with its own Paxos group and Megastore ran a Paxos instance per entity group across datacenters, while Bigtable and GFS pushed their metadata consistency onto Chubby. Viewstamped Replication (Oki and Liskov, 1988) is acknowledged in the paper's own postscript as apparently equivalent, and ZooKeeper's Zab is the same shape adapted to primary-order broadcast. Raft (Ongaro and Ousterhout, 2014) was explicitly designed as an understandable substitute but keeps the skeleton intact: monotonic terms in place of ballot numbers, a vote request that doubles as a promise, and a leader required only for liveness — and through Raft the design reached etcd, Consul, CockroachDB, TiKV, and the Kubernetes control plane. The paper's secondary ideas travelled just as far: bureaucrat terms became leases, law books became snapshotting and log compaction, and the decree-number monotonicity trick became the read-index and lease-read techniques in modern consensus stores, while Flexible Paxos (2016) later showed that only phase-one and phase-two quorums need intersect.

In the paper’s words — verbatim

“Recent archaeological discoveries on the island of Paxos reveal that the parliament functioned despite the peripatetic propensity of its part-time legislators.”

Abstract

“However, in the Paxon Synod, having multiple presidents could only impede progress; it could not cause inconsistency.”

§2.4

“Functions are much easier to design, and to get right, than distributed algorithms.”

§4.1

Vocabulary — as this paper uses it

Ledger: A legislator's durable record, written in indelible ink so entries can never be changed; notes in the back may be crossed out, and anything on a mere slip of paper may be lost when he leaves the Chamber. It is the paper's split between stable storage and volatile memory.
Decree: A numbered item of law, the unit that Parliament agrees on; the law of the land is the sequence of decrees passed. In the computing translation a decree is a state-machine command and its number is its position in the replicated log.
Ballot: A numbered referendum on a single decree, consisting of a decree, a quorum, the set of priests who voted, and a ballot number. It succeeds exactly when every priest in its quorum voted, and the decree of a successful ballot is the chosen one.
Ballot number: A value from an unbounded ordered set, partitioned so that each priest has his own infinite supply and no two priests can use the same number. A larger number means later, but says nothing about when the ballot was actually conducted.
Majority set (quorum): The set of priests whose votes make a ballot succeed. The only property actually required is that any two majority sets share at least one priest, which is why simple majorities, weight-based majorities, and attendance-weighted majorities all work.
MaxVote(b, p, B): The vote cast by priest p with the largest ballot number strictly less than b, or p's null vote with ballot number minus infinity if he cast none. Extended to a set of priests by taking the maximum, it is the quantity a president must learn in phase one.
Condition B3: The rule that for every ballot B, if any member of B's quorum voted in an earlier ballot, then B's decree must equal the decree of the latest of those earlier ballots. It is the constraint that prevents a new ballot from overwriting a decree that may already have been chosen.
President: The single priest or legislator responsible for initiating ballots, elected only so that progress is possible. Multiple simultaneous presidents can impede progress but can never cause inconsistency, which is why leader election need not be exact.
Olive-day decree: A traditional decree that makes absolutely no difference to anyone, used by a new president to fill any gap in his ledger. It is the no-op log entry that keeps the decree sequence dense and preserves the decree-ordering property.

On the timeline — where this sits in the story

Year1989–2001

MilestonePaxos consensus algorithm

Problem solvedReplicated distributed systems needed machines to agree on state despite failures and message delays.

How it solved itPaxos formalized fault-tolerant distributed consensus for replicated logs and state machines.

Why it matteredBecame a foundation for metadata services, distributed databases, and coordination systems.

DDIACh. 10: Consistency & Consensus

View on the timeline