The Consensus Problem

Consensus is the problem of getting a group of nodes to agree on a single value, even when some of them crash and messages are delayed or lost. It sounds narrow, but it underlies a lot: who the leader is, which write came first, whether a transaction commits, who holds a lock.

The definition

A correct consensus algorithm guarantees:

• Agreement: no two correct nodes decide different values.
• Validity: the decided value was actually proposed by someone (no deciding “42” out of thin air).
• Termination: every correct node eventually decides.

The first two are safety properties (nothing bad happens). Termination is a liveness property (something good eventually happens). That split matters, because the famous impossibility result says you can’t guarantee both in a fully asynchronous system. See FLP Impossibility.

Why it’s hard

Nodes can crash at any moment, including halfway through telling others what they decided. Messages can arrive late or out of order. And as failure detectors show, a node can’t reliably tell a crashed peer from a slow one. Naive approaches, such as “everyone votes and the coordinator announces the result”, fail when the coordinator dies at the wrong moment. That’s Two-Phase Commit‘s weakness.

Paxos, briefly

Leslie Lamport’s Paxos was the first widely known practical solution for crash failures. Roles:

• Proposers suggest values, tagged with increasing proposal numbers.
• Acceptors promise not to accept older proposals, and accept values.
• Learners find out what was chosen.

It runs in two phases: prepare/promise (a proposer claims a proposal number and learns of any value already accepted) and accept/accepted (it asks acceptors to accept a value, which has to be the previously accepted one if any). A value is chosen once a majority accepts it. Majorities always overlap, so two different values can never both be chosen.

Paxos is correct and notoriously hard to understand and implement. That’s why Raft was designed: the same guarantees, structured for humans.

Where you meet it

You rarely implement consensus yourself; you use systems built on it, such as etcd, ZooKeeper, Consul and consensus-backed databases. Knowing the problem explains their behaviour: why clusters have odd sizes (3 or 5, so a majority survives failures), why writes slow down when nodes are far apart, and why a cluster that loses its majority stops accepting writes rather than risk disagreeing. That last one is the CP choice in the CAP Theorem.