Consensus

Getting a set of nodes to agree on one value when some of them may fail. It is the primitive under every replicated database commit, leader election and failover in this spoke, and the reason those mechanisms look as awkward as they do. Documented from podc-lecture-notes.

The result everything else works around

Theorem 16.14. “There is no deterministic algorithm which always achieves consensus in the asynchronous model, with f > 0.”

Fischer, Lynch and Paterson (1985). One crash-faulty node, no timing assumptions, and no deterministic algorithm can guarantee agreement — not “is slow”, cannot. The proof runs on bivalent configurations: there is always an initial state whose outcome is undecided, and an adversary can keep the system in undecided states by crashing the one node whose step would resolve it.

So every consensus system that works in practice buys its way out by weakening a premise:

Add timing. Assume partial synchrony — messages arrive within some unknown bound — which is what timeouts and failure detectors are. Paxos and its descendants live here. Confirmed from the primary source 2026-08-10 (part-time-parliament): the paper states that any protocol achieving its progress condition “must involve measuring the passage of time,” and cites FLP in the footnote. Safety in Paxos rests on three conditions with no notion of time in them; only termination needs a clock.
Add randomness. Randomised consensus with a shared coin terminates with probability 1 rather than always. The notes develop this immediately after the impossibility proof, which is the right ordering: it is a response, not an alternative.

A production database that says it “does consensus” is asserting one of those assumptions. Which one, and what happens when it is violated, is the question the assertion hides.

When failures are arbitrary rather than clean

A crashed node stops. A byzantine node does “anything imaginable” — sends nothing, sends different and wrong messages to different neighbours, lies about its input. The model came from avionics, where sensors were observed failing into arbitrary behaviour before stopping.

The resilience bound is f < n/3: agreement under arbitrary faults needs more than three times as many nodes as faults tolerated. That is where the 3f+1 replica counts in byzantine-tolerant systems come from. Authentication changes the bound — signatures stop a node lying differently to different peers, which is why authenticated agreement is treated as its own chapter.

The primary source arrived 2026-08-10 and sharpens both halves (byzantine-generals-problem, Lamport, Shostak and Pease, 1982). The bound is a property of the problem, not of any algorithm: three generals cannot tolerate one traitor, and any solution for 3m or fewer could simulate its way down to that case, so none exists. And authentication does not merely change the bound — with unforgeable signatures the paper’s algorithm SM(m) solves the problem for any number of nodes and any number of faults, and also drops the connectivity requirement to the weakest one that keeps the correct nodes connected. The 3f+1 count exists solely to compensate for a node’s ability to tell different lies to different peers.

Two limits the primary source states about itself and the secondary account does not. Detecting a missing message needs synchronized clocks, and synchronizing clocks under faults is “as difficult a problem as the Byzantine Generals Problem itself”. And unforgeable signatures are achievable only probabilistically — against a malicious operator rather than a random malfunction, the assumption becomes a cryptography problem.

Why it belongs in this spoke

The spoke’s axis runs from in-process to 768 machines, and everything past the embedded pole needs agreement to commit. vitess-style routing and scatter-gather describe how a query finds its shards; consensus is what decides whether a write that touched several of them counts. The corpus had the mechanisms and not the limits they were designed against.

Why majorities, exactly

Answered 2026-08-10 by part-time-parliament, and it is smaller than the surrounding machinery suggests. Paxos’s safety rests on three conditions on the set of ballots: unique ballot numbers, any two quorums share at least one member, and a new ballot must adopt the decree of the latest earlier ballot any of its quorum members voted in. A majority is used because any two majorities of a set intersect, and that shared member is what carries a decided value forward into every later attempt. Quorum intersection is the mechanism; “majority” is just its cheapest implementation.

What a production consensus system looks like

Half of this gap closed 2026-08-10 with chubby-lock-service — Paxos in production at Google, with numbers. Five replicas, a master elected by majority plus a few-seconds master lease, writes acknowledged at a majority, and reads served by the master alone because the lease proves no other master exists. The lease is how a consensus-backed store serves linearizable reads at one machine’s speed.

Its rationale is the useful part for this spoke. Google had a Paxos client library and shipped a central lock service instead, partly because applications acquire high availability after they have users and a lock is a two-line change where a replicated state machine is a rewrite — and partly because a consensus library needs a quorum of the application’s own servers, while a lock service lets a single client make progress safely. The quorum does not disappear; it is relocated into a service that specialises in holding one.

What this corpus still lacks

Raft, the algorithm most production systems actually run, is not in these notes and not in this wiki — though part-time-parliament now supplies its ancestor, including the leader-per-instance amortisation Raft inherits. Nor is any database engine’s own account — Spanner’s TrueTime, CockroachDB’s use of Raft, Vitess’s failover path. chubby-lock-service is a lock service rather than a store, so the theory now has one production witness and the OLTP engines in this spoke still have none.

paxos · byzantine-generals-problem · part-time-parliament · paxos-made-simple · chubby-lock-service · leslie-lamport · podc-lecture-notes · consistency-models · database-sharding · cross-shard-queries · vitess · operational-databases