Paxos consensus

How N processes durably agree on a single value despite failures and delays — the algorithm that ran Google Chubby for twenty years.

Problem

Several distributed processes must decide on a single value among a proposed set (who is the current leader? what is the next log entry? what is the master schedule?). Processes may crash and restart; messages can be lost, duplicated or delayed but not corrupted. The FLP theorem (Fischer-Lynch-Paterson 1985) proves no deterministic consensus is possible in a purely asynchronous system with even one failure. Paxos circumvents this obstacle by guaranteeing safety unconditionally and liveness as soon as a sufficient synchrony window appears.

Forces

• FLP impossibility — perfect consensus is impossible under pure asynchrony; Paxos accepts looping in case of indefinite leader duels.
• Unconditional safety — no incorrect value is ever decided, even under failures or partitions.
• High conceptual complexity — Lamport himself acknowledges that the original article (Part-Time Parliament) was misunderstood for eight years.
• Fault tolerance: Paxos tolerates f failures among 2f+1 nodes (quorum N/2+1).
• Performance: multi-Paxos (optimised variant) amortises overhead to 1 round-trip per decision after stabilisation.

Solution

Paxos relies on three roles: proposers (propose values), acceptors (vote), learners (learn the decision). Each proposal uses a unique and monotonically increasing proposal number (round number). Phase 1a (prepare): the proposer sends prepare(n) to a quorum of acceptors. Phase 1b (promise): each acceptor promises not to accept any n' < n, and returns the most recently accepted value. Phase 2a (accept): the proposer sends accept(n, v) where v is its value (or the most recent returned value). Phase 2b (accepted): each acceptor accepts if no higher n' was promised. When a value is accepted by a quorum, it is chosen, and all future proposers will return it.

Structure

Proposer        Acceptors (A, B, C)         Learners
   │                  │                         │
   │ prepare(5) ───►  │                         │
   │ ◄── promise(5,_) │                         │
   │                  │                         │
   │ accept(5, "X") ► │                         │
   │ ◄── accepted(5,X)│                         │
   │                  │                         │
   │ if majority:     │                         │
   │ value "X" chosen ──────────────────────►   │
   │                                            │

Concurrent duel:
  P1 prepare(5) → some promises
  P2 prepare(7) → preempts P1 (higher n)
  P1 accept(5, "X") → rejected (acceptors promised 7)
  P1 retries with prepare(9) → ...
  → "dueling proposers" livelock prevented by leader election

Multi-Paxos optimisation:
  Elect distinguished proposer (leader)
  Skip phase 1 for subsequent rounds → 1 round-trip per decision

EDI implementation

As with Raft, you consume Paxos rather than write it. Apache Cassandra uses Paxos for its Lightweight Transactions (LWT) — useful if an EDI hub wants a compare-and-set guarantee on a partner status. Google Spanner combines Paxos and TrueTime for its multi-region transactions; a global EDI hub built on Spanner inherits the externalised guarantees. Apache ZooKeeper uses ZAB (Paxos variant) for its atomic broadcast. Understanding Paxos lets you calibrate the inter-DC latency needed for quorum consensus — a 3-region decision across 3 continents typically takes 80-200 ms per round-trip, capping per-leader consensus throughput to 5-12 decisions/second without pipelining.

Anti-patterns

• Implementing Paxos yourself — subtle bugs are countless; even Lamport recommends using a proven implementation.
• Ignoring message corruption — Paxos assumes non-corrupted messages; without MAC or TLS, an attacker can break consensus.
• Quorum of 2 nodes — any failure paralyses writes; always 3, 5 or 7.
• Confusing basic Paxos and multi-Paxos — the distinguished-leader optimisation radically changes performance.
• Believing Paxos handles Byzantine failures — BFT-Paxos or PBFT is needed for that.

Related patterns

• Raft — understandable reformulation of Paxos.
• Byzantine Fault Tolerance — extension to potentially malicious nodes.
• Leader Election — multi-Paxos depends on it.
• Partition Tolerance (CAP) — Paxos picks C+P, not A.

Sources

• Lamport L. — The Part-Time Parliament, ACM Transactions on Computer Systems, 1998 (written 1989). lamport.azurewebsites.net
• Lamport L. — Paxos Made Simple, 2001, pedagogical version. paxos-simple.pdf
• Chandra T., Griesemer R., Redstone J. — Paxos Made Live: An Engineering Perspective, Google, PODC 2007. Field report from Chubby. paxos made live
• Van Renesse R., Altinbuken D. — Paxos Made Moderately Complex, ACM Computing Surveys, 2015.
• Tanenbaum & van Steen — Distributed Systems, 3rd ed., 2017, ch. 6.