Paxos Made Simple — Papers Distilled

In one breath — the whole paper, compressed

Paxos Made Simple restates the consensus algorithm of The Part-Time Parliament without the Greek allegory, deriving it step by step from the safety properties it must satisfy. A set of acceptors accepts numbered proposals, and a value is chosen once a majority of acceptors have accepted a single proposal carrying that value. All of safety reduces to one invariant, P2c: before issuing proposal number n, a proposer must have heard from a majority of acceptors and must reuse the value of the highest-numbered proposal any of them already accepted. That invariant is enforced by a two-phase protocol — a prepare round in which acceptors promise to ignore lower-numbered proposals and report what they have accepted, and an accept round that commits the value phase 1 constrained. Safety holds unconditionally under crash failures and a lossy asynchronous network; liveness requires electing a single distinguished proposer, which by the FLP impossibility result needs randomness or real time.

Before this paper — the world it landed in

By 2001 Paxos was over a decade old, but its canonical presentation, The Part-Time Parliament, dressed the algorithm as an archaeological account of a Greek island parliament and was, in Lamport's own words, Greek to many readers. Practitioners who needed fault-tolerant replication were building around a single central server, which takes the whole service down when it fails, or around two-phase commit, which blocks when the coordinator dies. The state machine approach from Time, Clocks, and the Ordering of Events in a Distributed System was already the most cited idea in distributed systems theory, but it presupposed a way to agree on the command sequence that nobody could explain simply. Fischer, Lynch, and Paterson had proved in 1985 that no deterministic asynchronous algorithm guarantees consensus with even one faulty process, so any usable answer had to cleanly separate what is always safe from what merely usually terminates. This note exists to make that answer readable in ordinary prose.

The problem — what was actually breaking

The easiest way to choose a value is a single acceptor that takes the first proposal it receives, but the failure of that one acceptor makes any further progress impossible.
Requiring an acceptor to accept the first proposal it receives (P1) is needed so a lone proposal can be chosen, yet concurrent proposals can then leave every acceptor holding some value while no value has a majority, and the loss of one acceptor can make the outcome unknowable.
Because P1 forces acceptors to accept more than one proposal over time, the algorithm must separately guarantee that all chosen proposals carry the same value, which is condition P2.
P2a, the natural weakening of P2 onto acceptors, conflicts with P1: an acceptor that never received the winning proposal would still be obliged to accept a later, different value, so the constraint must be pushed back onto proposers as P2b.
To satisfy P2b a proposer must know the highest-numbered proposal that has been or will be accepted by each acceptor in some majority, and while past acceptances are easy to ask about, future acceptances cannot be predicted.
Two proposers can lock each other out indefinitely, each completing phase 1 with a number that invalidates the other's phase 2 accept requests, so the safety argument on its own yields no guarantee that any value is ever chosen.

Core ideas — the contributions, and why they work

Majorities as intersecting quorums

A value is chosen when a majority of acceptors have accepted a single proposal with that value. This works because any two majorities of a fixed acceptor set share at least one member, so no later majority can be assembled without touching an acceptor that already knows about the earlier decision. That one overlapping acceptor is the entire mechanical basis of the safety argument, and it is why an acceptor may accept at most one value per proposal number. Lamport notes the obvious generalization to quorum systems beyond simple majorities, tracing it to his 1978 paper on reliable distributed multiprocess systems.

Deriving the protocol from P2

Instead of presenting a protocol and then proving it correct, the paper starts from the property it wants — P2, that if a proposal with value v is chosen then every higher-numbered chosen proposal has value v — and strengthens it in three forced steps. P2a moves the obligation from chosen proposals to accepted ones, P2b moves it further back to issued ones, and P2c turns it into a local, checkable condition on the act of issuing a proposal. Each step is compelled by a concrete counterexample rather than chosen for convenience. The payoff is that the two-phase protocol reads as the only thing one could have written, which is exactly Lamport's claim that consensus follows almost unavoidably from its requirements.

The P2c invariant

P2c says that when a proposal with number n and value v is issued, there must be a majority S of acceptors such that either no acceptor in S has accepted anything numbered below n, or v is the value of the highest-numbered sub-n proposal accepted by any acceptor in S. This is precisely what makes induction on proposal numbers work: any majority S intersects the majority C that chose the earlier proposal m, so the highest-numbered value visible within S must already be the chosen value. Maintaining P2c is the only safety obligation in the whole algorithm. Everything else in Paxos is machinery for making P2c hold in an asynchronous, crash-prone system.

Extracting a promise instead of predicting the future

P2c requires a proposer to reason about acceptances that have not happened yet, which is impossible. Paxos sidesteps this by having the proposer control the future rather than predict it: the prepare request asks each acceptor for a promise never again to accept a proposal numbered below n. Once a majority has promised, the set of sub-n proposals that majority can ever accept is frozen, so the proposer's snapshot of the highest-numbered one stays accurate forever. This single move converts an unbounded question about the future into a bounded question about the past, and it is the conceptual heart of the algorithm.

Two phases with the value bound late

Phase 1 sends a numbered prepare request and gathers promises together with any previously accepted proposals; phase 2 sends an accept request carrying either the value those responses force on the proposer or, if no acceptor reported anything, any value the proposer likes. The structurally crucial fact is that phase 1 mentions no value at all — the proposer commits to a value only in phase 2. That is what lets a leader run phase 1 once and then reuse it for many subsequent decisions, and it is explicitly named as the key to the efficiency of the state machine implementation.

Safety and liveness split apart

Every rule in the algorithm is one-sided: an acceptor can ignore any request without compromising safety, so the specification only ever says when an agent is allowed to respond. As a result safety survives lost and duplicated messages, arbitrary delays, crashes and restarts, abandoned proposals, and even several servers simultaneously believing they are the leader. Liveness is handled entirely separately, by electing a single distinguished proposer, and the paper is explicit that FLP forces such an election to use randomness or real time such as timeouts. Splitting the two lets the safety argument be unconditional while the liveness argument is allowed to be best effort.

Consensus instances as a replicated log

The complete Paxos algorithm is consensus applied to the state machine approach: run a separate instance of the consensus algorithm for each slot in the command sequence, with the value chosen by instance i being the ith command executed by a deterministic state machine. Because the state machine is deterministic, every server that applies the same command sequence produces the same states and outputs, so a client can use the output produced by any server. Each server plays proposer, acceptor, and learner in every instance, and the consensus algorithm guarantees at most one command can ever be chosen as the 135th. This is the replicated-log shape that essentially every later consensus system inherited.

How it works — the mechanism, concretely

Phase 1: prepare and promise

A proposer selects a proposal number n from its own disjoint number space and sends a prepare request with number n to a majority of acceptors. An acceptor responds only if n is greater than any prepare number it has already responded to, and its response is a promise never again to accept a proposal numbered less than n, together with the highest-numbered proposal it has already accepted, if any. As an optimization the acceptor simply ignores a prepare request numbered below a promise it has already given, since it could never accept the resulting proposal anyway. Ignoring a request is always safe, which is why the acceptor rules are stated purely as permissions rather than obligations.

Phase 2: accept

If responses arrive from a majority of acceptors, the proposer issues an accept request for proposal number n whose value v is the value of the highest-numbered proposal among those responses; if no responder reported an accepted proposal, the proposer is free to pick any value, such as a fresh client command. The accept request need not go to the same set of acceptors that answered phase 1. An acceptor accepts the proposal unless it has already responded to a prepare request with a number greater than n — condition P1a, which subsumes P1. The value is chosen the instant a majority has accepted that numbered proposal, even though no participant necessarily observes that instant.

Acceptor state and stable storage

With the ignore optimization in place an acceptor needs to remember exactly two things: the highest-numbered proposal it has ever accepted, and the number of the highest-numbered prepare request to which it has responded. Because P2c must remain invariant regardless of failures, both must survive a crash and restart, so they live in stable storage and an acceptor records its intended response in stable storage before actually sending it. Proposers need far less durable state: a proposer may abandon a proposal at any point and forget it entirely, provided it never issues another proposal with the same number. Uniqueness of numbers is guaranteed by giving each proposer a disjoint set of numbers and having it remember, also in stable storage, the highest number it has tried to issue.

Learning a chosen value

A learner must discover that some proposal was accepted by a majority of acceptors. The direct scheme has each acceptor send every acceptance to every learner, which learns the fastest but costs a message count equal to the product of the number of acceptors and the number of learners. The alternative routes acceptances to a distinguished learner — in the real implementation, the elected leader — which then informs the rest, costing only the sum of the two counts at the price of an extra round and a single point of failure; a larger set of distinguished learners buys reliability with communication. Because messages can be lost, a value can be chosen with no learner ever finding out, and a failed acceptor can make it impossible to tell whether a majority accepted, so a learner that needs a definite answer must have a proposer run the algorithm again.

Progress and the distinguished proposer

Dueling proposers give a concrete livelock: p completes phase 1 for n1, q completes phase 1 for n2 greater than n1 so p's accept requests are ignored, p then completes phase 1 for n3 greater than n2 so q's accept requests are ignored, and so on forever. The remedy is to elect a distinguished proposer as the only agent that tries to issue proposals; if it can communicate with a majority of acceptors and uses a number higher than any already used, its proposal will be accepted. To reach such a number it abandons and retries whenever it learns of a higher-numbered request, which is why an acceptor that ignores a request should tell the proposer — a performance optimization that does not affect correctness. FLP means the election needs randomness or real time, but a failed election only stalls the system and never breaks it.

A new leader taking over the log

A newly elected leader, being a learner in every instance, already knows most chosen commands — say 1 through 134 plus 138 and 139. It executes phase 1 for instances 135 through 137 and for all instances above 139, using the same proposal number for all of them so that one reasonably short message suffices, and an acceptor replies with more than a simple OK only for those instances where it has already received a phase 2 message. Where phase 1 determines a value the leader runs phase 2 to close that instance; where a gap has no pending command it proposes a special no-op command that leaves the state unchanged, because commands after a hole cannot be executed until the hole is filled. Once 136 and 137 are no-ops, commands 138 through 140 become executable and the leader assigns 141, 142, and onward to incoming client commands.

Pipelining, cost, and reconfiguration

A leader may run up to alpha commands ahead, proposing i+1 through i+alpha before 1 through i are known to be chosen; if it fails mid-flight a gap of up to alpha minus 1 commands can appear, which the next leader repairs with no-ops. Since leader failure and election should be rare, the effective cost of a command in steady state is only phase 2, and the paper cites Keidar and Rajsbaum for the result that phase 2 has the minimum possible cost of any fault-tolerant agreement algorithm, making Paxos essentially optimal. Membership change is folded into the state machine itself: the current set of servers is part of the replicated state and is changed by ordinary commands, with the servers that execute instance i+alpha specified by the state after command i. That single rule allows an arbitrarily sophisticated reconfiguration algorithm to be expressed as ordinary application logic.

What the paper showed — measurements and proofs

The result is a proof, not a measurement: P2c implies P2b, which implies P2a, which implies P2, and because proposal numbers are totally ordered P2 gives the crucial safety property that only a single value is ever chosen.
The induction turns on exactly one quorum fact — that any majority S contains at least one member of the majority C whose acceptors accepted the chosen proposal numbered m — together with unique proposal numbers and an asynchronous, non-Byzantine, crash-restart model whose messages may be delayed, duplicated, or lost but never corrupted.
Condition P1a, that an acceptor can accept a proposal numbered n if and only if it has not responded to a prepare request having a number greater than n, is shown to subsume P1, so the two-phase protocol needs no separate rule to keep a lone proposal choosable.
A newly chosen leader can execute phase 1 for infinitely many consensus instances by sending a single reasonably short message, because an acceptor answers with more than a simple OK only for those instances in which it has already received a phase 2 message.
In steady state a command costs only phase 2, and citing Keidar and Rajsbaum (MIT-LCS-TR-821, 2001) the paper states that phase 2 of Paxos has the minimum possible cost of any algorithm for reaching agreement in the presence of faults, hence Paxos is essentially optimal.
Safety is proved independent of leader election: even when several servers each believe themselves leader and propose in the same instance, two different servers never disagree on the value chosen as the ith state machine command; only progress is lost.

Limits and trade-offs — conceded and discovered

The paper itself declines to specify precise liveness requirements, stating only the goal that some proposed value is eventually chosen, and it openly exhibits the dueling-proposer scenario in which no value is ever chosen.
The paper concedes that progress requires a single distinguished proposer and that, by the Fischer-Lynch-Paterson impossibility result, reliably electing one requires randomness or real time such as timeouts, so Paxos is not a purely asynchronous solution to consensus.
The paper concedes that message loss can let a value be chosen with no learner ever finding out, and that a failed acceptor can make it impossible to determine whether a majority accepted a proposal, in which case learners discover the value only when a later proposal is chosen.
The model assumes non-Byzantine failures and uncorrupted messages, stated as an assumption rather than defended; tolerating malicious or corrupting participants requires entirely different protocols, as later Byzantine agreement work such as PBFT supplied.
Later work exposed how much this eleven-page note leaves to the implementer: the Chubby team's Paxos Made Live (PODC 2007) reported that building a production system from this description required substantial unspecified engineering for disk corruption, master leases, snapshots, and group membership, and Ongaro and Ousterhout designed Raft (USENIX ATC 2014) on the premise that Paxos, and especially the multi-instance version sketched in section 3, remains hard to understand and to implement correctly.

What it became — the systems that inherited it

Paxos Made Simple is the version of Paxos that industry actually read, and its state machine section is the blueprint for essentially every modern replicated log. Google's Chubby lock service (Burrows, OSDI 2006) implemented exactly this multi-instance design and became the coordination and metadata layer beneath GFS and Bigtable, while its follow-up, Paxos Made Live, catalogued everything the note had left to the implementer. Spanner runs a Paxos state machine over the replicas of each tablet and Megastore ran one per entity group, both using the leader-as-distinguished-proposer, one-instance-per-log-slot structure described here. ZooKeeper's Zab protocol adopted the same leader-plus-ordered-log shape for coordination, and Raft was written explicitly as an easier-to-understand alternative to this algorithm while keeping its majority quorums, monotonically increasing terms in place of proposal numbers, and its log-gap discipline; etcd, CockroachDB, TiDB, Consul, and Kafka's KRaft are all Raft descendants and therefore Paxos descendants at one remove. Cassandra's lightweight transactions run a Paxos round per compare-and-set operation, keeping the prepare and accept phases visible to application developers. The vocabulary this note fixed — proposers, acceptors, learners, prepare and accept phases, quorums, instances, and no-op fill — is now the default vocabulary for discussing consensus at all.

In the paper’s words — verbatim

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

Abstract

“Instead of trying to predict the future, the proposer controls it by extracting a promise that there won't be any such acceptances.”

§2.2

“Election of a single leader is needed only to ensure progress.”

§3

Vocabulary — as this paper uses it

Acceptor: One of the agents that may accept numbered proposals and whose durable state carries the algorithm's memory. A value counts as chosen only when a majority of acceptors have accepted the same numbered proposal.
Learner: An agent whose only job is to find out which value was chosen; learners never affect safety. In the implementation the elected leader also serves as the distinguished learner that informs the others.
Proposal: A pair consisting of a unique natural proposal number and a value. Numbers are totally ordered and drawn from per-proposer disjoint sets so that two proposers never issue proposals sharing a number.
Chosen: A proposal, and hence its value, is chosen when a single proposal with that value has been accepted by a majority of acceptors. Several proposals may be chosen over time, but P2 forces them all to carry the same value.
Prepare request: The phase 1 message carrying a number n. It asks each acceptor for a promise never again to accept a proposal numbered less than n, plus the highest-numbered proposal that acceptor has already accepted.
Accept request: The phase 2 message asking acceptors to accept proposal number n with value v. The value is either forced by the phase 1 responses or freely chosen when no responder reported any accepted proposal.
P2c: The invariant a proposer must maintain when issuing proposal number n with value v: some majority S of acceptors has accepted nothing numbered below n, or v is the value of the highest-numbered sub-n proposal accepted within S. Maintaining P2c is the algorithm's sole safety obligation.
Distinguished proposer: The single proposer elected to be the only one that tries to issue proposals, called the leader in the implementation. It exists purely to ensure progress, and its absence or duplication costs liveness but never safety.
Instance: One complete run of the consensus algorithm. The state machine implementation runs a sequence of instances, with the value chosen by instance i becoming the ith command, and gaps in the sequence filled by no-op commands.

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