Two-phase commit blocks when the coordinator dies. Three-phase commit trades blocking for extra round trips but still assumes bounded message delays. Paxos is the algorithm that survives what both fear: nodes crashing, messages dropping, arbitrary delays — while still guaranteeing that all live nodes eventually agree on the same value.

Paxos has three roles (often collapsed onto the same nodes): proposers suggest values, acceptors vote on them, and learners discover the outcome. It runs in two phases:

• Phase 1 (Prepare): A proposer picks a unique, monotonically increasing proposal number n and sends prepare(n) to a majority of acceptors. Each acceptor promises never to accept a proposal numbered lower than n, and replies with the highest-numbered proposal it has already accepted (if any).
• Phase 2 (Accept): If the proposer hears back from a majority, it sends accept(n, v). Crucially, v must be the value from the highest-numbered previously-accepted proposal it saw — or its own value if none exists. Once a majority accepts, the value is chosen.

The magic is in that "must reuse the previous value" rule. It's what prevents two proposers from getting different values chosen. Any future majority overlaps with the majority that already accepted, and Phase 1 forces the new proposer to see and reuse that value.

Real-world example: Google's Chubby lock service (which coordinates GFS and Bigtable) uses Multi-Paxos to elect leaders and replicate lock state across five nodes. When a Chubby master dies, the remaining four run Paxos to pick a new one. Traffic pauses for a few seconds — not minutes — and no split-brain occurs even if the old master briefly comes back. Apache ZooKeeper's ZAB and etcd's Raft are both Paxos-inspired (Raft is essentially "Paxos, but understandable").

Rule of thumb: With 2f + 1 nodes, Paxos tolerates f failures. So 3 nodes survive 1 failure, 5 survive 2, 7 survive 3. Going beyond 5 rarely helps — you pay more coordination cost per decision than you gain in fault tolerance. Most production systems (etcd, Consul, CockroachDB) run 3 or 5 replicas per Paxos group.

The gotcha: Basic Paxos runs both phases per decision, which is expensive. Multi-Paxos elects a stable leader that skips Phase 1 for subsequent decisions, reducing steady-state cost to one round trip. Dueling proposers can also cause livelock — solved by randomized backoff or leader election.