Paxos

The consensus algorithm underneath most replicated systems that survive a node failure without losing agreement. Split out on 2026-08-10 once the spoke held three sources on it — the original (part-time-parliament, 1998), the rewrite (paxos-made-simple, 2001), and a production system running it (chubby-lock-service, 2006).

What it guarantees, and what it does not

Safety, always. At most one value is ever chosen, and once chosen it never changes — regardless of message loss, reordering, delay, or how many nodes crash. No timing assumption is involved.

Liveness, conditionally. Progress requires electing a single distinguished proposer, and per FLP that election needs randomness or real time. A failed or contested election costs availability, never correctness (paxos-made-simple). This is why leader election in production systems can be best-effort and why a brief two-leader window is survivable.

The mechanism in one pass

Three roles: proposers, acceptors, learners.

Phase 1 (prepare / promise). A proposer picks number n and asks acceptors to promise they will accept nothing numbered below n. An acceptor that has seen nothing higher promises, and returns the highest-numbered proposal it has already accepted.

Phase 2 (accept / accepted). If a majority promised, the proposer sends an accept for n carrying the value from the highest-numbered accepted proposal any of them reported, or its own value if none reported any. A value is chosen when a majority accepts it.

Two properties carry the whole thing:

Quorum intersection. Any two majorities share a member, so a decision made by one majority is visible to every later one. Majority is the cheapest quorum system, not the principle (part-time-parliament's condition B2).

A proposer cannot invent a value once one might have been chosen. It must adopt what the quorum already knows about. Since it cannot observe accepts that have not happened yet, it forbids them — that is what the phase-1 promise is for (paxos-made-simple).

What production adds

chubby-lock-service shows the two things the papers leave out.

The master lease. A leader wins a majority plus promises that no rival will be elected for a few seconds, and can then serve reads alone — linearizable reads at one machine's speed, because the promise proves no other leader exists. Writes still cost a majority.

Amortisation. part-time-parliament's multi-decree construction runs one instance per slot but elects one leader across all of them, so phase 1 happens once and steady-state commits cost a single round trip. This is what "Multi-Paxos" names, and Raft inherits it.

Where it sits

The add-timing branch out of the FLP impossibility (consensus): Paxos does not evade the result, it accepts losing guaranteed termination and keeps safety unconditionally.

It also sits on the cheap side of byzantine-generals-problem's trade. Paxos assumes benign failure — a node stops, it does not lie — and in exchange tolerates failure of any number of nodes and links without a 3f+1 replica count. A corrupted node is outside its model.

Standing gap

Raft is still not in this wiki, and neither is any OLTP engine's own account of using either algorithm — Spanner's TrueTime, CockroachDB, Vitess failover. The spoke has the algorithm from three angles and no database's report of running it.

part-time-parliament · paxos-made-simple · chubby-lock-service · consensus · byzantine-generals-problem · consistency-models · leslie-lamport · operational-databases

The successor that displaced it in practice (added 2026-08-22)

Raft (2014) produces "a result equivalent to (multi-)Paxos" and is what the production systems in this spoke actually run — yugabytedb per tablet, and the etcd/Consul/ZooKeeper layer patroni rents its consensus from. The differences are deliberate restrictions rather than new power: only the leader may append, elections are settled by randomized timers rather than by proposal numbers, and membership changes go through joint consensus. Paxos's own literature treats leader election as an optimisation for liveness; Raft makes it structural, and gives up the generality in exchange for being explicable. Which of the two this spoke should treat as the default is now a real question rather than a historical one.