Paxos

Imagine five servers that all need to agree on one fact, like which transaction commits first or who holds a lock. Some servers might be slow, some might crash mid-decision, and messages between them can arrive late, out of order, or not at all. Paxos is the protocol that gets these servers to agree on exactly one value and never change their minds, no matter how badly the network misbehaves.

The core promise is safety: two different servers will never believe two different values were chosen. The protocol gives up on liveness in the worst case, meaning it can stall during chaos, but it will never produce a wrong answer. This split matters because in distributed systems a slow answer is recoverable but a contradictory answer corrupts data permanently.

Paxos was published by Leslie Lamport in 1998 as The Part-Time Parliament, and again more plainly in 2001 as Paxos Made Simple. It is the theoretical foundation under most strongly consistent systems built since, even when those systems use a friendlier variant on top.

Each node plays one or more roles. Proposers suggest values, acceptors vote on them, and learners observe the final outcome. A single round of agreement on one value is called Basic Paxos, and it runs in two phases.

In Phase 1, a proposer picks a unique, increasing proposal number n and sends a prepare(n) message to the acceptors. Each acceptor that has not already seen a higher number promises not to accept anything numbered below n, and reports back any value it previously accepted. Once a proposer hears promises from a majority, it moves on.

In Phase 2, the proposer sends accept(n, value). The critical rule: if any acceptor already reported an accepted value in Phase 1, the proposer must reuse the value tied to the highest proposal number it heard about, not its own. This is what prevents two values from ever winning. When a majority of acceptors accept, the value is chosen and learners are told.

Because a value is chosen by a majority, any future majority must overlap in at least one acceptor that remembers it. That overlap is the whole trick. Running a fresh two-phase round for every single decision is expensive, so Multi-Paxos elects a stable leader that skips Phase 1 for a stream of decisions, getting you down to one round trip per value in the common case.

Reach for Paxos-style consensus when you need a small group of nodes to agree with strong consistency: leader election, distributed locks, replicating a config or metadata store, or ordering writes to a state machine. It needs a majority (a quorum) to make progress, so a 3-node cluster tolerates 1 failure and a 5-node cluster tolerates 2.

The biggest cost is not throughput, it is comprehension and correctness of implementation. Lamport's papers describe Basic Paxos clearly but leave the practical machinery (log compaction, membership changes, leader handoff) as an exercise, and teams have shipped subtly broken versions for years. Google engineers documented this pain in the paper Paxos Made Live.

Latency is also a real factor. Every decision needs a round trip to a majority, so spreading nodes across distant regions adds tens to hundreds of milliseconds per commit. This is why most consensus clusters keep an odd, small node count in one or a few nearby zones. If you find Paxos hard to reason about, Raft was designed in 2014 to be an equivalent but more understandable alternative, and most new systems now choose Raft for that reason.

Google's Chubby lock service is the textbook case. Chubby runs a cell of five replicas, uses Multi-Paxos to keep their logs identical, and elects one as the master. Services like Bigtable and the Google File System rely on Chubby to elect their own leaders and store small bits of critical metadata, so a single Paxos cluster quietly backstops much of Google's infrastructure.

When the Chubby master crashes, the remaining replicas run a Paxos round to agree on a new master and on exactly where the log left off. Clients see a brief pause of a few seconds, then service resumes with no lost or duplicated decisions. That pause is the liveness cost being paid so that safety is never violated, which is precisely the bargain Paxos was designed to make.