Paxos rounds.
Single-decree Paxos: get a cluster to agree on exactly one value. Two phases (Prepare and Accept), majority quorums, and a single safety property — once chosen, a value never changes. Watch a second proposer learn that the hard way.
Paxos has roles. Proposers want to get values agreed on. Acceptors vote. (Leaders/learners simplified out.) Here we have two proposers (P1, P2) and five acceptors (A1-A5). They're about to compete to get a value chosen.
- Single-decree Paxos
- The basic protocol: a cluster agrees on ONE value. Multi-Paxos / Raft chain many of these together to agree on a sequence (a log).
- Acceptor majority
- A proposal needs majority of acceptors to be chosen. With 5 acceptors that's 3. Any two majorities overlap by at least one — that overlap is what enforces consistency.
Why the protocol has two phases
One phase isn\'t enough. If a proposer just sent "Accept(v)" directly, two proposers racing with different values could both get majorities and disagree. The Prepare phase establishes the proposer\'s right to propose at a specific number, lets it learn about any previously-accepted value, and forces it to use that value instead of its own. Phase 2 is then just confirmation.
Multi-Paxos · what real systems run
Single-decree Paxos agrees on one value. To agree on a log of operations, you run a separate instance per slot. Multi-Paxos optimizes: elect a stable leader, skip Phase 1 for subsequent values (the leader already has its number). When the leader is steady, every commit is one round-trip — Accept + Accepted. Drops to 2 round-trips per commit when the leader changes. Chubby (Google), Zab (ZooKeeper), and many proprietary systems use Multi-Paxos variants.
Paxos vs Raft side by side
Both pick a leader, replicate a log, tolerate minority failure. Raft splits the problem into named subproblems with explicit state machines, making the safety arguments easier to follow. Paxos uses a more abstract two-phase protocol that\'s harder to reason about but more symmetric. In practice every new system since ~2014 picks Raft, including most of Google\'s internal systems\' replacements. Paxos lives on in Spanner, Chubby, and many legacy systems.
Consensus algorithms →
Multi-Paxos, Fast Paxos, Egalitarian Paxos, Flexible Paxos, the relation to Byzantine algorithms like PBFT.
Open the Codex →