Paxos Consensus Protocol

Paxos separates the consensus problem into three logical roles. A proposer suggests a value it wants the system to agree on. An acceptor is a voting member that can promise not to accept old proposals and can accept new ones; agreement is defined in terms of what a majority (quorum) of acceptors accept. A learner simply finds out what value was chosen, typically by listening to acceptors or being told by the proposer that succeeded. In most deployments a single physical server plays all three roles simultaneously, but keeping the roles conceptually distinct is what makes the correctness argument tractable. Every proposal carries a strictly increasing round number (also called a ballot number or proposal number), unique to the proposer that issues it — typically constructed as `(counter, proposer_id)` so that ties never occur across different proposers. The protocol's central mechanism is that a higher round number can always interrupt a lower one, but any proposer using a higher round is obligated to re-propose whatever value a majority may already have locked in, rather than inventing a new value freely. This is the crux of the design: rounds provide liveness through retry (a stalled proposer can always try again with a bigger number), while the value-carrying obligation provides safety (no round can silently overwrite a decision already made). A value is considered chosen once a majority of acceptors have accepted it in the same round. Because any two majorities among $n$ acceptors must overlap in at least one acceptor (this is the Quorum Intersection property), no two different values can ever both be chosen — the overlapping acceptor cannot have accepted two different values in the round that chose them, and the protocol's rules ensure it cannot be tricked into doing so across rounds either. This single overlap fact, formalized below, is the entire safety proof of Paxos.

Single-decree Paxos decides one value. It runs in two phases, each itself a request/response round between a proposer and the acceptors.

Phase 1 (Prepare / Promise). The proposer picks a round number $n$ higher than any it has used before, and sends `Prepare(n)` to a majority of acceptors. An acceptor that receives `Prepare(n)`:

• If $n$ is greater than every round number it has seen so far, it replies `Promise(n, acceptedRound, acceptedValue)` — promising never again to accept any proposal numbered less than $n$ — and reports the highest-numbered value it has already accepted, if any.
• Otherwise it ignores the request (or replies with a rejection carrying the higher round it already knows about, so the proposer can jump ahead).

Phase 2 (Accept / Accepted). If the proposer receives `Promise` replies from a majority, it must choose the value to propose:

• If any acceptor reported a previously accepted value, the proposer must adopt the value from the highest `acceptedRound` among the replies — it is not free to substitute its own value.
• Only if no acceptor reported any previously accepted value may the proposer use its own value.

It then sends `Accept(n, value)` to the same majority. An acceptor that receives `Accept(n, value)` accepts it (recording `acceptedRound = n`, `acceptedValue = value`) unless it has already promised a higher round number in Phase 1, in which case it rejects the request. Once a majority accepts $(n, value)$, that value is chosen and can be revealed to learners — typically by having acceptors notify learners directly, or by having the proposer collect enough `Accepted` messages and broadcast the decision itself. ```pseudocode

# --- Proposer --- function Propose(proposer_id, value_hint): n = next_round_number(proposer_id) # e.g., (counter++, proposer_id), globally unique & increasing promises = []

# Phase 1: Prepare send Prepare(n) to all acceptors wait for replies from a majority of acceptors, or timeout for each reply Promise(n, acc_round, acc_value) received: promises.append((acc_round, acc_value)) if reply is Reject(higher_n): n = higher_n + bump() # back off and retry with a bigger number goto Phase 1 if len(promises) < majority_count: retry with a larger n after backoff # no quorum reached -> contention or failures

# Determine the value to propose if any promise carries a non-null acc_value: value = value_with_highest(acc_round, promises) # MUST reuse this value else: value = value_hint # free to propose own value

# Phase 2: Accept send Accept(n, value) to the same majority wait for Accepted(n) replies, or timeout / Reject if majority of Accepted(n) received: value is CHOSEN notify learners(value) return value else: retry with a larger n after backoff

# --- Acceptor state (persisted to stable storage before replying) --- promised_round = -infinity accepted_round = -infinity accepted_value = null function OnPrepare(n): if n > promised_round: promised_round = n persist(promised_round) reply Promise(n, accepted_round, accepted_value) else: reply Reject(promised_round) function OnAccept(n, value): if n >= promised_round: promised_round = n accepted_round = n accepted_value = value persist(promised_round, accepted_round, accepted_value) reply Accepted(n) else: reply Reject(promised_round) ``` Two subtleties matter for correctness. First, an acceptor must persist its state to stable storage before replying — otherwise a crash-and-restart could forget a promise and violate safety. Second, the `OnAccept` check uses `n >= promised_round` rather than strict equality: an acceptor may `Accept` a proposal numbered exactly equal to its highest promise, since that promise was made for this very proposer's Phase 2 message.

To decide many values in sequence — the realistic case of a replicated log — systems run Multi-Paxos: a single elected proposer (the leader) runs Phase 1 once to reserve a round number for an entire range of log slots, then repeatedly runs only Phase 2 for each new log entry, skipping Phase 1 as long as it remains the recognized leader. This amortizes the expensive round-trip of Phase 1 across many decisions, reducing steady-state latency to one round trip per committed value.

Message and round complexity. In the common case with no contention, single-decree Paxos takes exactly two round trips: Prepare/Promise, then Accept/Accepted, each fanning out to a majority of $n$ acceptors. This is $O(n)$ messages per phase, so $O(n)$ total messages and $O(1)$ round trips when uncontested. Under contention — two proposers dueling with increasing round numbers — the protocol can, in principle, retry indefinitely (the classical "dueling proposers" livelock), which is exactly the manifestation of FLP Impossibility Result: no bound on termination can be guaranteed in a fully asynchronous, failure-prone system. Practical deployments break this livelock by electing a stable leader (via randomized backoff or a separate leader-election protocol), reducing steady state to $O(1)$ round trips per decision.

Fault tolerance. With $2f+1$ acceptors, Paxos tolerates up to $f$ crash failures while still being able to form a majority quorum of $f+1$. It does not tolerate Byzantine (malicious/arbitrary) failures without extension — the base protocol assumes acceptors follow the algorithm faithfully but may crash and restart.

Space. Each acceptor stores only $O(1)$ state — its highest promised round and its single highest accepted `(round, value)` pair — regardless of how many proposers have competed, because the protocol only ever needs the latest promise and latest acceptance to answer future messages correctly.

Correctness proof sketch (safety). The goal is: if a value $v$ is chosen (accepted by a majority) in round $n$, then any value chosen in any round $n' > n$ is also $v$. The proof is by strong induction on round number. Invariant P1 (quorum intersection). Any two majority sets of acceptors, out of a fixed total set, share at least one common acceptor. This is pure counting: if $|Q_1|, |Q_2| > n/2$ out of $n$ acceptors, then $|Q_1 \cap Q_2| \ge |Q_1| + |Q_2| - n > 0$. Invariant P2. If a proposer issues `Accept(n, v)`, then either no acceptor has accepted any value in a round less than $n$, or $v$ is the value with the highest-numbered prior acceptance reported to that proposer in its Phase 1 promises. Invariant P2a. If `Accept(n, v)` can be issued, then $v$ equals the value of every value chosen (by a majority) in any round less than $n$.

Base case: Let $n_0$ be the smallest round in which a value $v$ is chosen (accepted by majority $Q_0$). By definition no earlier chosen value exists, so vacuously P2a holds for $n_0$.

Inductive step: Suppose P2a holds for all rounds less than $n$, and suppose `Accept(n, v')` is issued by some proposer $P$. We must show $v' = v$ for the (unique, by induction hypothesis extended) value $v$ chosen in $n_0 \le n' < n$. By the Phase 1 rule, $P$ collected `Promise` replies from a majority $Q$ before issuing `Accept(n, v')`. By quorum intersection (P1), $Q \cap Q_0 \ne \emptyset$: some acceptor $a$ is in both the majority that chose $v$ in round $n_0$ and the majority that promised $P$ in round $n$. Because $a$ accepted $v$ at round $n_0 \le n' < n$, and $a$ replied to `Prepare(n)` with `Promise` (meaning $n$ is greater than every round $a$ has promised, hence greater than $n_0$ at the time it accepted), $a$'s reply must report `acceptedRound \ge n_0` and some accepted value. By the Phase 2 rule, $P$ is forced to adopt the value carried by the highest `acceptedRound` among all its promises — and since a chosen value's acceptance is reported by at least one acceptor in every subsequent majority (by repeated quorum intersection across every round between $n_0$ and $n$), that highest-reported value must be $v$. Hence $v' = v$. $\blacksquare$ This gives the headline safety guarantee: at most one value is ever chosen, and it is chosen permanently — no failure pattern, message reordering, or duplicate delivery can unchoose it or cause a different value to be chosen afterward. Liveness (that some value eventually gets chosen) is explicitly not guaranteed in general, matching FLP; it requires eventual synchrony and typically a stable leader in practice.

Tradeoff to be honest about: Paxos as described is famously hard to map onto engineering artifacts — the roles blur, log compaction and membership changes are not specified by the base algorithm, and "which proposer is the leader right now" is left to auxiliary mechanisms. This gap is exactly what motivated Raft Consensus Algorithm, which keeps Paxos's safety core but bakes in leader election and log matching as first-class, more mechanically checkable rules.

Consider $5$ acceptors $A_1 \ldots A_5$ (majority = 3). Two proposers, $P$ (client wants value `"X"`) and $Q$ (client wants value `"Y"`), race after a partial network partition.

Now suppose instead that step 5 had not lost the message — $A_2$ had already accepted `(1,"X")` before $Q$'s `Prepare(2)` arrived. Then in step 7, $A_2$'s `Promise(2, ...)` reply would carry `acceptedRound=1, acceptedValue="X"`. At step 10, $Q$ is no longer free to propose `"Y"`: the rule forces $Q$ to adopt the highest-numbered reported value, which is `"X"` from $A_2$. $Q$ sends `Accept(2, "X")` instead, and the same value `"X"` ends up chosen — illustrating exactly the safety mechanism proved above: a higher round can steal the round number, but never the already-chosen value.

Paxos originated from Leslie Lamport's whimsical framing of the problem as the parliamentary procedure of a fictional Greek island, "The Part-Time Parliament" — a paper so playfully written that its seriousness was initially missed by reviewers and readers alike. Lamport later republished a plainer version, "Paxos Made Simple," to correct the reception. The protocol is now considered one of the most important and most subtly difficult results in distributed computing, spawning an entire cottage industry of "Paxos made X" papers (live, simple, moderately complex, practical) attempting to make it more approachable to engineers.

Paxos and its Multi-Paxos extension underlie some of the most widely used distributed infrastructure in existence. Google's Chubby lock service and Spanner database use Paxos-replicated logs to keep metadata and transaction ordering consistent across data centers spanning continents. Apache ZooKeeper, used for coordination in Kafka, HBase, and countless distributed systems, runs ZAB, a protocol built on the same quorum-and-round principles as Paxos, tailored for a primary-backup log. Cloud object stores and distributed databases (CockroachDB, YugabyteDB, TiDB) use Paxos-family protocols, often via the Raft variant, to replicate ranges of key-value data with strong consistency guarantees. Understanding Paxos is prerequisite to understanding Raft Consensus Algorithm (a deliberately more teachable re-derivation of the same guarantees) and to reasoning correctly about Replication and Consistency Models used throughout modern cloud databases and coordination services.

Ask the tutor: How does Raft's leader-election term mechanism map onto Paxos's round numbers, and why does that mapping make Raft easier to reason about?