Remote islands must agree on decisions—when to hold festivals, which trading routes to use, who leads the council. Messages travel by boat, boats sink, islanders leave for fishing trips. How reach agreement with unreliable communication and partial failures? Paxos solves this: achieving consensus despite unreliable communication. Like islanders using a clever mailbox protocol, Paxos ensures everyone eventually agrees on the same decision.
The Island Communication Problem
Unreliable Boats
Messages arrive out of order, some vanish, others arrive twice. Cannot assume reliable communication.
Fishing Trip Dilemma
Participants come and go. Chief goes fishing, misses votes, returns needing to catch up. Decisions made in absence must be honored.
The Paxos Mailbox Protocol
Paxos uses two phases with proposal numbers for ordering.
Phase 1: Prepare
Proposer chooses a proposal number higher than any seen, sends Prepare to acceptors.
This diagram requires JavaScript.
Enable JavaScript in your browser to use this feature.
Acceptors respond: “Yes, N is highest I’ve seen” or “No, I’ve seen higher number M”. If higher, include any previously accepted values.
Phase 2: Accept
If proposer receives promises from a majority, it sends Accept with value. Acceptors accept if N is still highest seen. Majority accepts, value is chosen.
Proposal Numbers
Structure: (round, proposer_id). (5, island_2) > (5, island_1) because round is primary, ID breaks ties. No two proposals have identical numbers.
Behavior Examples
Clean Agreement
Island A proposes “Festival on Full Moon”. Prepare(1,A) to all, all promise, Accept(1,A,“Full Moon Festival”), majority accepts. Consensus in two round trips.
Competing Proposals
Island A proposes “Trade with East”, Island B proposes “Trade with West”. Both send Prepare(1). Some promise A, others B. Neither gets majority. A retries with Prepare(2,A), gets majority, proceeds. Consensus on “Trade with East”.
Learning Previous Values
Island C proposed “Elect Elder Kim” earlier. Only one island remembers. Island D prepares new proposal. Response includes “I accepted ‘Elect Elder Kim’ for (1,C)”. D must propose same value. Kim remains elected.
Safety Properties
Single Value Chosen
Only one value per decision. Multiple proposals may race, only one achieves majority accept. Cannot have two different decisions for same proposal number.
Chosen Value Stability
Once value chosen by majority, future proposals discover it and must propose the same value. Decision carved in stone.
Learner Consistency
All learners receive accepted values or learn nothing. Never learn different values for the same proposal.
Advanced Patterns
Multi-Paxos
Single Paxos per decision is expensive. Elect stable leader, run Phase 1 once, then many Phase 2 rounds. Amortizes prepare cost across many decisions.
Fast Paxos
Often no conflict. Skip Phase 1, clients propose directly to acceptors. Collisions fall back to classic Paxos. Lower latency when uncontended.
Byzantine Paxos
Classic Paxos assumes honest mistakes. Byzantine variant handles malicious nodes with cryptographic signatures and requires 2/3 + 1 majority.
Flexible Paxos
Prepare and Accept quorums can differ. Requirement: quorums must overlap. Better availability trade-offs possible.
Common Challenges
Dueling Proposers
Livelock: A prepares 1, B prepares 2 (disrupts A), A prepares 3 (disrupts B), continues forever. Solution: random backoff or leader election breaks symmetry.
FLP Impossibility
No consensus algorithm can guarantee termination in fully asynchronous networks with even one faulty process. Timeouts break the assumption. Works well enough in practice.
Latency Cost
Two round trips minimum. Prepare phase + Accept phase. Learn phase may add third. Optimizations: Multi-Paxos leader, geographic placement, batching decisions.
Complexity Burden
Paxos is notoriously difficult to understand. Core idea is simple, edge cases are complex, implementation is error-prone. Raft was designed specifically for understandability.
When Paxos Applies
Paxos fits:
- Systems requiring proven correct consensus
- Applications where correctness is paramount
- Foundation for distributed databases and coordination
Paxos adds complexity for:
- Simple coordination where less rigor suffices
- High-latency geo-distributed deployments
- Teams lacking time to implement correctly
Decision Rules
Use Paxos when:
- You need proven safety guarantees
- Formal verification is a goal
- Building foundational coordination infrastructure
- You understand the complexity
Consider Raft when:
- Implementability matters more than theoretical foundation
- Team lacks consensus protocol expertise
- Same safety guarantees suffice
- Understandability is a priority
The boats sail between islands. Messages seek majority approval. Consensus emerges from chaos.