Part 2 of 6 · 3 min read
The problem and its four properties
Several nodes propose values, and exactly one is chosen.
Think of friends trying to pick one restaurant by text message. Some phones are slow, one friend's battery dies, and two friends suggest different places at the same moment. The group still must end with one choice that everyone stands by.
The DDIA book calls consensus one of the most important and basic problems in distributed computing. Informally: get several nodes to agree on something. It seems simple, and many broken systems were built in the belief that it is easy.
Situations where nodes must agree, per the book:
- Leader election: all nodes agree who the leader is, to avoid split brain, where two nodes both accept writes and the data diverges.
- Atomic commit: a transaction over several nodes must either commit everywhere or abort everywhere (module 9).
- Uniqueness: several people try to book the last seat or take the same user name, and one must win.
The formal version: one or more nodes propose values, and the algorithm decides one of them. In the seat example each node proposes the customer it serves, and the decision says who got the seat.
Consensus
Consensus is the problem of getting several nodes to agree on one value that one of them proposed, even if some nodes crash.
Example: nodes A, B and C receive three different requests for the last seat. After consensus all three agree that customer 17 gets it, and nobody changes their mind.
The four properties the book lists:
| Property | Meaning |
|---|---|
| Uniform agreement | No two nodes decide differently |
| Integrity | No node decides twice |
| Validity | A decided value was proposed by some node |
| Termination | Every node that does not crash eventually decides |
The first three are safety properties (nothing bad happens) and termination is a liveness property (something good happens), as in module 5. Validity rules out cheats such as always deciding "nothing".
Without fault tolerance it is easy: choose one node as dictator. The trouble is that if it fails, the system cannot decide. Termination demands progress even when nodes fail. The book gives a vivid picture of the failure model: a crashed node vanishes and never returns (imagine the data centre buried by a landslide). An algorithm that waits for a node to come back cannot satisfy termination. Two-phase commit has this weakness.
What can be tolerated. The book says any consensus algorithm needs a majority of nodes working to guarantee termination. Most implementations keep the safety properties even if a majority fails: a big outage can stop the system from answering, but cannot make it decide wrongly. Most algorithms assume no Byzantine faults (module 4); tolerating them needs fewer than one-third faulty nodes.
The FLP result. A famous proof (Fischer, Lynch and Paterson) says no algorithm can always reach consensus if a node may crash. The book explains why that does not stop practice. The proof assumes a very restricted model with no clocks or timeouts. With timeouts, or even random numbers, consensus becomes solvable. In practice, systems reach consensus.
A worked example. Five nodes. Three propose different values: A proposes "red", C proposes "blue", E proposes "green". Node D crashes forever. The algorithm decides "blue". All four live nodes decide "blue". Agreement holds, validity holds ("blue" was proposed), nobody decides twice, and the four live nodes all decided. Deciding "yellow" would break validity. A and C deciding different colours would break agreement.
Check yourself:
- Why can a single dictator node not be the answer?
- Which of the four properties is the liveness one?