Paxos

Paxos, first described by Leslie Lamport in his 1989 paper 'The Part-Time Parliament' and later clarified in 'Paxos Made Simple' (2001), is the canonical algorithm for achieving consensus in asynchronous distributed systems subject to crash failures. The core problem Paxos solves is deceptively simple: how do N processes agree on a single value when any process can crash at any time and messages can be delayed, duplicated, or lost (but not corrupted)? Paxos guarantees that at most one value is chosen (safety) and that a value is eventually chosen if a majority of processes remain alive (liveness, under partial synchrony).

Basic Paxos operates in two phases. In Phase 1 (Prepare), a proposer selects a ballot number (a globally unique, monotonically increasing identifier) and sends a Prepare(n) message to a majority of acceptors. Each acceptor responds with a Promise not to accept any proposal with a ballot number less than n, and includes the highest-numbered proposal it has already accepted (if any). In Phase 2 (Accept), if the proposer receives promises from a majority, it sends an Accept(n, v) message where v is either the value from the highest-numbered previously accepted proposal, or the proposer's own value if no prior proposals exist. An acceptor accepts the proposal if it has not promised to a higher ballot. Once a majority of acceptors accept a value, consensus is achieved.

Basic Paxos decides a single value, which is rarely useful on its own. Production systems use Multi-Paxos, which elects a stable leader and runs consecutive Paxos instances to build a replicated state machine (a replicated log of commands). The leader skips Phase 1 for subsequent slots because it already holds the highest ballot, reducing each consensus round to a single Phase 2 exchange. This optimization transforms Paxos from a theoretical curiosity into a practical replication protocol with message complexity of 2 messages per decision (leader to acceptors, acceptors acknowledge).

Paxos is notoriously difficult to understand and implement correctly. Google's Chubby paper (2006) noted that implementing Paxos 'proved to be non-trivial' despite the team's deep expertise. The subtleties include handling leader changes, managing the gap between chosen and learned values, snapshotting and log compaction, and reconfiguring the cluster membership. These implementation challenges led Diego Ongaro to design Raft as a more understandable alternative. Nevertheless, Paxos remains the theoretical benchmark -- most consensus proofs reference Paxos, and understanding it is prerequisite knowledge for evaluating any consensus system.

Three office managers (acceptors) need to agree on which room to book for an all-hands meeting. Manager A proposes Room 101 with ticket #1. Before the vote completes, Manager B proposes Room 202 with higher ticket #2. The acceptors who already promised ticket #1 now receive a higher ticket and must honor ticket #2 instead. Manager B hears that no prior value was accepted, so Room 202 is chosen. If Manager A tries again with ticket #3, they first learn that Room 202 was already accepted at ticket #2, so they must re-propose Room 202 (not Room 101) -- this is how Paxos preserves the previously chosen value.