Paxos High-Level
Paxos is the foundational consensus algorithm for distributed systems, invented by Leslie Lamport in 1989, published in 1998 as “The Part-Time Parliament,” and re-explained in plainer language as “Paxos Made Simple” (2001). Paxos solves the same problem as Raft — get a cluster of unreliable processes to agree on a single value, despite message losses, delays, and a minority of node failures — but it does so in a more primitive and flexible form. The base protocol decides one value; Multi-Paxos chains Paxos rounds together to commit a log of values; Fast Paxos, Generalized Paxos, Egalitarian Paxos (EPaxos), Cheap Paxos, Vertical Paxos, and Flexible Paxos are variants that optimize for specific failure or latency models. The basic Paxos round has two phases — Prepare and Accept — each requiring a majority quorum, with the safety property hinging on the fact that any two majorities overlap. Paxos is famously hard: Lamport’s original 1998 paper was rejected for being incomprehensible; even after the 2001 simplification, deploying it correctly took the Google Chubby team multiple years and produced the influential “Paxos Made Live” engineering retrospective. Production deployments include Google’s Chubby, Spanner, Megastore, Microsoft’s Azure Storage, Apache Cassandra (Light-Weight Transactions), and Heroku’s matchmaker. Despite Raft’s recent popularity, Paxos remains the theoretical and historical backbone of distributed consensus.
1. Intuition — Two Phases, Always Two Phases
The fundamental problem: a cluster has N nodes, some may crash, the network is asynchronous, and we need to choose one value such that:
- Safety. No two nodes will ever decide on different values for the same instance.
- Liveness. Eventually, some value will be decided (assuming enough nodes are up and the network is non-malicious).
Lamport’s design is built around three roles (a single physical machine usually plays all three):
- Proposer. Wants to get a value chosen.
- Acceptor. Votes on proposals; their voting state is the heart of safety.
- Learner. Learns the chosen value (often the same as Acceptors).
The protocol runs in two phases. The two-phase structure is necessary, not stylistic — it is what guarantees that a partially-completed earlier round can never produce two conflicting decisions later.
Phase 1 — Prepare.
A Proposer picks a globally-unique, monotonically-increasing proposal number n (e.g., (timestamp, proposer_id) pairs ordered lexically). It sends Prepare(n) to a majority of Acceptors. Each Acceptor that receives Prepare(n) does two things:
- If
nis greater than any proposal number it has previously promised, it promises to ignore any future proposals numbered less thann. - It returns whatever value it most recently accepted (in any earlier Accept phase), along with that value’s proposal number.
If the Proposer collects promises from a majority of Acceptors, it moves to Phase 2.
Phase 2 — Accept. The Proposer must now decide which value to propose. The rule: if any Acceptor in the Phase-1 majority returned a previously-accepted value, the Proposer must reuse the value with the highest accepted proposal number among them. Only if no Acceptor returned any accepted value can the Proposer use its own freely-chosen value.
The Proposer then sends Accept(n, value) to the same (or any) majority of Acceptors. Each Acceptor that receives Accept(n, value) checks: did it promise (in some earlier Prepare phase) to reject proposals with n' > n? If not, it accepts (n, value). If a majority of Acceptors accept (n, value), the value is chosen.
The crucial subtlety: Phase 1’s purpose is not to get a value chosen — it is to (a) lock out lower-numbered competing proposals, and (b) discover whether some value might already be on its way to being chosen, so the Proposer can respect that. Phase 2’s purpose is to get the value committed.
Why two phases work, in three sentences. Two majorities must intersect (any two majorities of N share at least one node). If a value v was ever chosen, that means a majority accepted it; the intersecting Acceptor will report v to any future Phase-1 of any future round, which forces the future Proposer to re-propose v. So once any value is chosen, no subsequent round can choose a different value. Safety guaranteed.
2. Tiny Worked Example
Three Acceptors A1, A2, A3. Quorum is 2. Proposers P1, P2.
Step 1: P1 picks proposal number n=10 and sends Prepare(10) to A1, A2, A3.
Step 2: All three Acceptors have never seen any proposal. Each:
- records "highest promise = 10"
- replies Promise(n=10, accepted_value=None, accepted_n=None).
Step 3: P1 receives Promises from {A1, A2} (a majority).
P1 has no constraint (no accepted_value reported), so it picks its own value "X".
P1 sends Accept(10, "X") to A1, A2, A3.
Step 4: A1 and A2 each:
- check: their highest promise is still 10; no higher promise made; so accept.
- record (accepted_n=10, accepted_value="X").
- reply Accepted.
A3 happens to be slow; its message arrives late.
Step 5: P1 receives Accepted from {A1, A2} = a majority.
Value "X" is chosen.
--- Now P2 wakes up (didn't know about P1) and tries to propose value "Y":
Step 6: P2 picks n=11 and sends Prepare(11) to A1, A2, A3.
Step 7: A1 receives Prepare(11). 11 > 10, so A1:
- updates its promise to 11.
- reports its accepted state: accepted_n=10, accepted_value="X".
- replies Promise(n=11, accepted_value="X", accepted_n=10).
Same for A2 (it has accepted X).
A3 has never accepted anything, replies Promise(n=11, None, None).
Step 8: P2 collects Promises from a majority. The majority includes A1 (and/or A2),
which reports accepted_value="X".
The Paxos rule says: P2 must propose "X" (the value with the highest accepted_n
it has seen), not its preferred "Y".
P2 sends Accept(11, "X") — not Accept(11, "Y") — to A1, A2, A3.
Step 9: All three accept. The value chosen is still "X". (Two rounds, same value.)
This is the safety property in action: once a value is chosen, even a Proposer that has never heard of the chosen value will be forced to re-propose it. The Phase-1 Promise replies smuggle the chosen value into any future round.
The dance feels strange the first few times you trace it. Step 8 is the unintuitive bit — P2 wanted to propose Y, but the protocol forces it to propose X. This is why the protocol works at all.
3. The Algorithm — Single-Decree Paxos
# --- Acceptor state ---
promised_n: int = 0 # highest proposal number we've promised to ignore-below
accepted_n: int = 0 # proposal number of the value we last accepted
accepted_v: any = None # the value we last accepted
# --- Acceptor: handle Prepare ---
on receive Prepare(n):
if n <= promised_n:
reply Nack # rejected; don't break promise
else:
promised_n = n
reply Promise(n, accepted_n, accepted_v)
# --- Acceptor: handle Accept ---
on receive Accept(n, v):
if n < promised_n:
reply Nack # promised not to accept lower
else:
promised_n = n # implicit promise (accept = at-least-as-high)
accepted_n = n
accepted_v = v
reply Accepted(n)
# --- Proposer ---
function propose(my_value):
n = pick_unique_increasing_number()
# --- Phase 1 ---
send Prepare(n) to all Acceptors
promises = collect responses until majority OR timeout
if not majority: retry with higher n
# Determine value to propose
accepted_with_highest_n = max(promises, key=lambda p: p.accepted_n)
if accepted_with_highest_n.accepted_v is not None:
v = accepted_with_highest_n.accepted_v # MUST reuse
else:
v = my_value # free to choose
# --- Phase 2 ---
send Accept(n, v) to all Acceptors
accepts = collect responses until majority OR timeout
if not majority: retry with higher n
# v is now CHOSEN
return v
The proposal number’s monotonicity is enforced via unique numbers per Proposer — typically (round_counter, proposer_id) ordered lexicographically. Two Proposers will never pick the same number; if both want to propose round 7, one tags it (7, P1) and the other (7, P2).
3.1 Why the Two-Phase Structure Is Necessary
What if you tried to do consensus in one phase? Proposer sends (n, v) directly. Two competing Proposers send (10, "X") and (11, "Y") simultaneously. Acceptors receive them in different orders — A1 sees X first, accepts X, then rejects Y; A2 sees Y first, accepts Y, then rejects X; A3 partitioned. Now we have X accepted on A1 and Y accepted on A2 — neither has a majority, so neither is “chosen,” but the two halves are stuck. No retry can resolve it because the Acceptors’ state is conflicting at single-value granularity. Single-phase fails to give the Proposer the chance to learn the existing committed-or-in-flight state before deciding what value to propose. Phase 1 is exactly this: a “what’s everyone in the middle of doing?” probe before commit.
3.2 Why “Pick the Value with Highest Accepted_n” in Phase 2
Suppose multiple values were partially accepted by some Acceptors in earlier rounds — none reaching majority, all aborted because their Proposers crashed. Some Acceptor A reports accepted_v = "X", accepted_n = 7; another A’ reports accepted_v = "Y", accepted_n = 9. Why pick Y over X?
If Y was ever chosen (i.e., a majority accepted it), then the round numbered 9 is the latest round that could have chosen anything; anything chosen in round 7 (X) cannot have been chosen because round 9 happened after and any chosen value would have been carried forward. So the value with the highest accepted_n is the only one that could have been chosen. Picking it preserves whatever was chosen, if anything.
Lamport’s proof in “Paxos Made Simple” formalizes this argument. The key invariant — call it P2c — is: if a proposal (n, v) is issued, then there is a set S consisting of a majority of Acceptors such that either no acceptor in S has accepted any proposal numbered less than n, or v is the value of the highest-numbered proposal among all proposals numbered less than n accepted by acceptors in S.
P2c is what the “pick highest accepted_n” rule preserves. Once you internalize P2c you understand why Phase 1 returns accepted values, why Phase 2 must re-propose them, and why the protocol cannot be simplified.
4. Multi-Paxos — From One Decision to a Log
Single-decree Paxos chooses one value. Real systems need an ordered log of values (the replicated state machine pattern). The naive approach: run a fresh Paxos instance per log slot, two phases each. But Phase 1 is mostly wasted across slots if no leader change is happening — all the Acceptors will keep returning “no accepted value” because they are talking about distinct slots.
Multi-Paxos optimization. Elect a stable leader that runs Phase 1 once (for a range of slots, or implicitly for “all future slots”) and then issues only Phase-2 messages for each subsequent log entry. The Phase-1 promise covers all slots until a competing Proposer wins a higher-numbered Prepare. This brings the cost of each commit from 2 round trips to 1 round trip — the same as Raft.
The leader-election part is morally equivalent to Raft’s leader election; in fact, this is one of Raft’s design conceits — Raft is essentially Multi-Paxos with leadership made into a first-class concept rather than emerging from Phase-1 winning. (Howard & Mortier’s 2020 ApPLIED paper develops this equivalence formally.)
In practice, virtually no one runs single-decree Paxos in production; Multi-Paxos is the deployed form. When people say “Google uses Paxos,” they mean Multi-Paxos.
5. Pseudocode (Multi-Paxos with Stable Leader)
# --- Stable leader (one Proposer at a time) ---
function leader_main_loop():
n = elect_unique_proposal_number()
# Phase 1 across all slots, once at leader takeover
send Prepare(n) to all Acceptors
promises = collect majority
if not majority: re-elect; restart
# For each slot s where some Acceptor reported accepted_v_s:
# re-fill that slot with the highest-numbered accepted value
for s in slots_with_accepted_values:
v = highest_accepted_v_in_promises_for(s)
send Accept(n, s, v) to all Acceptors
# Now leader can issue new commands
while still_leader:
cmd = next client command
s = next free slot
send Accept(n, s, cmd) to all Acceptors
wait for majority Accepted
slot[s] is now CHOSEN; commit cmd to state machine
# --- Acceptors stay the same as single-decree, indexed per slot ---
The key practical issues — leader election, recovery of holes, stale-leader detection, log compaction — are exactly the engineering content of “Paxos Made Live” (Chandra et al., PODC 2007), the Google Chubby team’s report. Read that paper next if Multi-Paxos is interesting to you.
6. Python Implementation (Single-Decree Paxos, Stripped Down)
A working Paxos implementation is hundreds of lines once you account for retries, message loss, leader election, and persistent storage. The code below is a sketch of single-decree Paxos with synchronous, in-memory, lossy-only-via-test message passing. Network and concurrency are stubbed out.
from dataclasses import dataclass, field
from typing import Optional
@dataclass
class Promise:
proposal_n: int
accepted_n: Optional[int]
accepted_v: Optional[object]
@dataclass
class Acceptor:
node_id: str
promised_n: int = 0
accepted_n: Optional[int] = None
accepted_v: Optional[object] = None
def on_prepare(self, n: int) -> Optional[Promise]:
if n <= self.promised_n:
return None # Nack
self.promised_n = n
return Promise(n, self.accepted_n, self.accepted_v)
def on_accept(self, n: int, v: object) -> bool:
if n < self.promised_n:
return False # Nack
self.promised_n = n
self.accepted_n = n
self.accepted_v = v
return True
@dataclass
class Proposer:
proposer_id: int
acceptors: list[Acceptor]
round_counter: int = 0
def _new_proposal_number(self) -> int:
self.round_counter += 1
# Compose unique increasing number: high bits = counter, low bits = id
return (self.round_counter << 16) | self.proposer_id
def propose(self, my_value) -> object:
while True:
n = self._new_proposal_number()
# Phase 1
promises: list[Promise] = []
for a in self.acceptors:
p = a.on_prepare(n)
if p is not None:
promises.append(p)
if len(promises) <= len(self.acceptors) // 2:
continue # no majority, retry with higher n
# Determine value: reuse highest-accepted-n if any
accepted = [p for p in promises if p.accepted_v is not None]
if accepted:
v = max(accepted, key=lambda p: p.accepted_n).accepted_v
else:
v = my_value
# Phase 2
accepts = sum(1 for a in self.acceptors if a.on_accept(n, v))
if accepts > len(self.acceptors) // 2:
return v # CHOSEN
# otherwise retry
# --- Demo: two competing proposers, same value emerges -----------------------
if __name__ == "__main__":
acceptors = [Acceptor(node_id=f"A{i}") for i in range(3)]
p1 = Proposer(proposer_id=1, acceptors=acceptors)
p2 = Proposer(proposer_id=2, acceptors=acceptors)
chosen_v = p1.propose("X")
print("P1 chose:", chosen_v) # X
chosen_v2 = p2.propose("Y") # forced to re-propose X
print("P2 chose:", chosen_v2) # X
assert chosen_v == chosen_v2The implementation captures the safety-critical Phase-1 + Phase-2 dance and demonstrates the key property (P2 cannot override P1’s choice). What’s missing for production: asynchronous network with message loss/duplication/reordering, persistent state for promised_n and accepted_*, leader election, multi-decree extension, learner notification, and snapshot/log-compaction. The actual Paxos implementations at Google are reportedly closer to 7,000 lines per the “Paxos Made Live” paper.
7. Complexity and Math
| Quantity | Value |
|---|---|
| Cluster size for f failures | 2f + 1 nodes (same as Raft) |
| Quorum size | ⌊N/2⌋ + 1 (majority) |
| Latency per single-decree Paxos | 2 RTTs (Prepare + Accept) |
| Latency per Multi-Paxos commit (steady state) | 1 RTT (Phase 2 only) |
| Throughput ceiling | bound by leader (Multi-Paxos) or by all Proposers (multi-leader variants) |
The 2f+1 bound is fundamental: any two majorities of 2f+1 must overlap by at least 1 node. With fewer nodes, two majorities could be disjoint and accept conflicting values, breaking safety.
A subtle theorem (the “FLP impossibility result” — Fischer, Lynch & Paterson 1985) says no deterministic protocol can guarantee both safety and liveness in an asynchronous network with even one crash failure. Paxos chooses to guarantee safety always; liveness holds only when the cluster has a stable, single-leader, sufficiently-non-adversarial network. In adversarial scheduling, a series of Proposers can keep stepping on each other (each calling Prepare with a higher number, invalidating the previous Proposer’s promise) and no value gets chosen. This is the Paxos dueling proposers livelock — a real concern that Multi-Paxos addresses by funneling all proposals through a stable leader.
8. Variants
Paxos is more of a family than a single algorithm. The family is wide.
8.1 Multi-Paxos
The default. Stable leader runs Phase 1 once, then runs Phase 2 per slot. 1-RTT commits in steady state.
8.2 Fast Paxos (Lamport 2006)
Optimization for collision-free workloads. Acceptors can sometimes accept a value in 1 round trip without a Prepare phase, but if collisions occur (two Proposers race), it falls back to a regular Paxos round. Quorum size grows: Fast Paxos needs ⌈(3N+1)/4⌉ for the “fast” quorum (vs ⌈(N+1)/2⌉ for regular). Best for low-contention workloads.
8.3 Generalized Paxos (Lamport 2005)
Operates on commutative commands. Concurrent commutative commands can be committed in parallel without ordering them, raising throughput when the workload is mostly commutative.
8.4 EPaxos / Egalitarian Paxos (Moraru, Andersen & Kaminsky, SOSP 2013)
No designated leader. Every node can commit commands directly, in 1 RTT, if the commands don’t conflict. Conflicts are resolved by a second phase that establishes ordering. EPaxos achieves geographically-distributed low latency where any region’s local node can commit without crossing oceans for non-conflicting requests. Significantly more complex than Multi-Paxos.
8.5 Cheap Paxos (Lamport & Massa 2004)
Distinguishes “main” Acceptors from “auxiliary” Acceptors. Auxiliary Acceptors are activated only when main ones fail. Reduces normal-case message count; fault tolerance preserved.
8.6 Vertical Paxos / Reconfigurable Paxos
Handles changing the cluster membership. Important because real clusters need to add and remove machines without downtime; Lamport’s basic Paxos says nothing about this. Vertical Paxos provides a clean reconfiguration story.
8.7 Flexible Paxos (Howard, Malkhi, Spiegelman 2016)
Generalizes the quorum requirement: Phase 1 and Phase 2 can use different quorum sizes, as long as any Phase 1 quorum intersects any Phase 2 quorum. Enables tradeoffs like “small read quorum, large write quorum” for read-heavy workloads.
8.8 Byzantine Paxos / PBFT
Extensions that tolerate not just crash failures but malicious nodes. Quorum sizes grow to 3f+1 (instead of 2f+1); messages need cryptographic authentication. Used in blockchains (Tendermint, HotStuff family) and high-assurance systems.
9. Production Examples
9.1 Google Chubby (Burrows, OSDI 2006)
Lock service used internally by GMail, Google Search index, BigTable, GFS. Implemented with Multi-Paxos. The “Paxos Made Live” paper (Chandra, Griesemer, Redstone, PODC 2007) is the engineering retrospective: 7,000 lines of C++ Paxos, plus a state-machine framework, plus their hand-written Paxos checker. The team explicitly says “we discovered that the Paxos algorithm as described in the literature does not even handle some of the problems that arise in practice.”
9.2 Google Spanner (Corbett et al., OSDI 2012)
Globally-distributed SQL database. Each Spanner “Paxos group” is a set of replicas (typically 3 or 5) holding a tablet of data; intra-group consensus is Paxos. Spanner additionally uses TrueTime for cross-group transaction ordering, but the per-group consensus is Paxos.
9.3 Google Megastore (Baker et al., CIDR 2011)
Earlier predecessor to Spanner; per-entity-group Paxos. Read latency was a known weakness of Megastore — a major motivation for Spanner.
9.4 Microsoft Azure Storage
Azure Storage uses Paxos in its stream layer, the lowest layer of the storage stack that handles durable, append-only “stream” (extent) replication. The published SOSP 2011 architecture paper (Calder et al. 2011) describes the Stream Manager (SM) — the component that tracks the stream namespace, the stream-to-extent mapping, and the placement of extents across extent nodes — as a small Paxos-replicated cluster (the paper states the SM “uses a standard Paxos algorithm”). Note the division of labor: Paxos in WAS replicates only the metadata/control plane (the SM’s view of which extents live where), while the bulk data-plane replication of extent bytes uses primary-driven chain replication, not Paxos — a common pattern where consensus governs the small, critical metadata and a cheaper scheme moves the bulk data.
9.5 Apache Cassandra Lightweight Transactions
Cassandra’s IF NOT EXISTS and similar conditional writes go through Paxos rounds. The classic (pre-Paxos-v2) implementation costs four round trips per lightweight transaction (LWT), corresponding to four message-pair phases: Prepare/Promise, Read/Results (read the current value to evaluate the condition), Propose/Accept, and Commit/Acknowledge (DataStax LWT docs). The extra Read phase versus textbook Paxos is what makes LWTs compare-and-set rather than blind agreement; the Commit phase persists and acknowledges the chosen value to the replicas. LWTs are notoriously slower than ordinary QUORUM writes — four round trips instead of one — so they are reserved for the rare queries that genuinely need linearizable conditional logic. Cassandra 4.0 introduced “Paxos v2” optimizations that reduce the round-trip count in the common case.
Uncertain
Verify: that “Paxos v2” in Cassandra 4.x reduces the LWT round-trip count and the exact mechanism/round-trip savings. Reason: drawn from a vendor (AxonOps) blog rather than the Apache Cassandra design docs / CEP, and the exact round-trip reduction was not pinned to a primary source during this pass. To resolve: read the relevant Cassandra Enhancement Proposal (CEP) for Paxos v2 and the 4.0/4.1 release notes. uncertain
9.6 Heroku Matchmaker
The Heroku platform’s resource-allocation matchmaker is reported to have historically used Paxos for leader election among the matchmaker instances (see the §9 uncertainty flag — this is the least well-sourced of the deployment claims here and should be treated as illustrative).
9.7 ScyllaDB Light-Weight Transactions
Same pattern as Cassandra LWT.
Uncertain
Verify: the Heroku Matchmaker (§9.6) Paxos-for-leader-election claim. Reason: it traces to a years-old engineering blog post and could not be confirmed against a current primary source during this pass; Heroku’s internal architecture is not publicly documented the way Google’s is. The Google deployments (§9.1–9.3) are well-documented in the cited OSDI/CIDR papers, and the Azure Storage Stream-Manager-uses-Paxos claim (§9.4) is confirmed by the Calder et al. SOSP 2011 paper. To resolve: find a current Heroku engineering source or treat the §9.6 claim as historical/illustrative only. uncertain
10. Pitfalls
10.1 “Famously Hard”
This isn’t snark — it’s an interview takeaway. Lamport’s 1998 paper was famously rejected and republished only after being pre-fictionalized as the parliament of an ancient Greek island. Even after “Paxos Made Simple” (2001), the algorithm remains a teaching disaster. The “Paxos Made Live” paper opens with: “Despite the existence of an extensive Paxos literature, building a fault-tolerant database from the algorithm proved to be a non-trivial task.” Treat any “I implemented Paxos in a weekend” claim with extreme suspicion.
10.2 Dueling Proposers Livelock
Two Proposers can keep escalating proposal numbers, each invalidating the other’s promises before either can complete Phase 2. No value gets chosen; the protocol is safe but not live. Fix: introduce a stable leader (Multi-Paxos), or use exponential backoff with random jitter on retry.
10.3 Forgetting Persistent State
promised_n and accepted_* must be fsynced before responding. If an Acceptor crashes after promising but loses its promise, a future round may be allowed to choose a different value, breaking safety. This is the same disaster mode as Raft skipping fsync.
10.4 Sloppy Proposal-Number Generation
Two Proposers must never pick the same proposal number. The (counter, proposer_id) lex-ordered scheme is standard. A common bug: using just a wall-clock timestamp without a tie-breaker — clock skew or simultaneity produces ties.
10.5 Conflating Phase 1 and Phase 2
Beginners often try to “merge the phases for efficiency.” The two phases are not redundant; collapsing them breaks safety (see §3.1). The only correct merge is the Multi-Paxos optimization, where Phase 1 happens once across many slots; even then it’s still two distinct phases conceptually.
10.6 Insufficient Reading of “Paxos Made Live”
The PODC 2007 paper documents the engineering corners that Lamport’s papers don’t cover: handling disk failures, log compaction, dynamic membership, abruptly aborted writes. Anyone implementing Paxos for production should read it before starting; many production-Paxos bugs are issues this paper anticipates.
10.7 Wrong Quorum for Variant
Switching from Multi-Paxos to Fast Paxos to EPaxos changes quorum sizes. Fast Paxos needs ⌈(3N+1)/4⌉, EPaxos has its own “fast quorum” rule. Mixing the wrong quorum with the wrong protocol breaks safety silently — the cluster may appear to work and lose correctness only in rare schedules.
10.8 Assuming Liveness = Safety
Paxos is safe even under partition; it just may not progress. Operators sometimes panic when Paxos halts during partition and “fix” it by lowering quorum requirements, which destroys safety. The right reaction to “Paxos isn’t choosing a value” is “majority of Acceptors must be unreachable; restore connectivity.”
11. Mermaid Diagram — Single-Decree Paxos Round
sequenceDiagram participant P as Proposer participant A1 as Acceptor 1 participant A2 as Acceptor 2 participant A3 as Acceptor 3 Note over P: Phase 1 - Prepare P->>A1: Prepare(n=10) P->>A2: Prepare(n=10) P->>A3: Prepare(n=10) A1-->>P: Promise(n=10, prev_v=None) A2-->>P: Promise(n=10, prev_v=None) Note right of A3: A3 slow / unreachable Note over P: Majority reached;<br/>no prev value seen;<br/>propose own value v=X Note over P: Phase 2 - Accept P->>A1: Accept(n=10, v=X) P->>A2: Accept(n=10, v=X) P->>A3: Accept(n=10, v=X) A1-->>P: Accepted(n=10) A2-->>P: Accepted(n=10) Note over P: Majority Accepted;<br/>v=X is CHOSEN
What this diagram shows. A single-decree Paxos round, with three Acceptors and a quorum of two. Phase 1 (top): the Proposer broadcasts Prepare(n=10) to all Acceptors. Two of them (A1, A2) reply with promises that include any previously-accepted value (here, none). A3 is unreachable but does not block the round — Paxos only needs a majority, not unanimity, which is the source of its fault-tolerance. Phase 2 (bottom): the Proposer, having seen no previously-accepted values in any of the promises, freely picks its own value v=X and broadcasts Accept(n=10, v=X). A1 and A2 accept (they have not promised anything higher than 10); their majority of accepts means v=X is now the chosen value of this round. The two-phase structure — Prepare to learn-and-lock, then Accept to commit — is the load-bearing structure that prevents two Proposers from concurrently picking different values: any subsequent Phase 1 with n > 10 will see A1 or A2 (whichever is in the next round’s quorum) report accepted_v=X, forcing the new Proposer to re-propose X. Once X is chosen, the protocol guarantees no future round can choose anything different.
12. Common Interview Problems / System-Design Questions
| Question | Expected hit |
|---|---|
| ”Explain Paxos” | Two phases, Prepare and Accept; majority quorum; safety from majority overlap |
| ”Why two phases? Can’t we collapse them?” | No — Phase 1 lets Proposer learn already-chosen values and forces re-proposal; safety hinges on this |
| ”Paxos vs Raft — when would you use each?” | Raft if you want simplicity and a strong leader; Paxos if you need flexibility (EPaxos, Fast Paxos, Generalized Paxos) for specialized workloads |
| ”Why is Paxos famously hard?” | The original 1998 paper was opaque; the protocol’s invariants are subtle (P2c); production gotchas are many (see Paxos Made Live) |
| “What is Multi-Paxos?” | Stable leader + Phase 1 once + Phase 2 per slot; brings commit cost from 2 RTT to 1 RTT |
| ”What’s the role of the proposal number?” | Total order over rounds; Acceptors promise to ignore lower numbers; ensures monotonic progress |
| ”Walk me through the Paxos safety argument.” | Any two majorities overlap; once a value is chosen, a future round’s Phase 1 must see it via the overlap; Proposer reuses it |
| ”What is the FLP impossibility result?” | No deterministic asynchronous protocol guarantees safety + liveness with even one crash failure; Paxos sacrifices liveness in adversarial scheduling |
| ”What is Fast Paxos?” | Optimization to commit in 1 RTT when no contention; larger quorums; falls back to regular Paxos on collision |
| ”Where is Paxos deployed in production?” | Google Chubby, Spanner, Megastore; Azure Storage; Cassandra LWT |
| ”What would happen without majority overlap?” | Two disjoint ‘majorities’ could each accept different values → safety violated |
| ”What is the dueling proposers problem?” | Two Proposers each escalating proposal numbers indefinitely; safe but not live; Multi-Paxos with stable leader fixes |
13. Open Questions
- In what regimes does EPaxos’s leader-free design measurably beat Multi-Paxos in production deployments?
- Is Howard & Mortier’s claim (“Paxos and Raft are equivalent up to engineering choices”) fully accepted, or is there still a meaningful theoretical separation?
- How should we think about the trade-off between Paxos’s flexibility (many variants) and Raft’s simplicity (one canonical algorithm)?
- Why has Raft so thoroughly displaced Paxos in new projects despite Paxos’s larger production footprint? Is it purely the “understandability” argument, or does Raft’s strong-leader primitive simplify operator tooling in ways that matter?
- What’s the smallest known correct production Paxos implementation? (Multi-thousand lines per “Paxos Made Live”; can we do better with modern languages and TLA+ verification?)
14. See Also
- Raft — the modern alternative; cleaner protocol with strong-leader primitive
- Consistent Hashing — used for sharding Paxos groups across many machines
- LSM Tree — common storage layer beneath Paxos-replicated logs
- B+ Tree — alternative storage layer
- Hash Table — internal state machine implementation
- Bloom Filter — used in Paxos-backed databases (Cassandra)
- Skip List — alternative ordered structure
- Big-O Notation
- SWE Interview Preparation MOC