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