Consensus
What does consensus deliver, why 2f+1, and why does it scale fault tolerance rather than throughput?
What consensus provides is not agreement on a single value but agreement on a sequence: a replicated log in which every correct replica applies the same commands in the same order. Agreement on a single value ("single-decree" Paxos) is a building block that nobody deploys alone.
Why 2f+1
Any two quorums must intersect. Let N be the number of members, Q the quorum size and f the number of failures to tolerate. You must be able to form a quorum from the survivors: Q ≤ N − f. Any two quorums must share a member: 2Q > N. Substituting the first into the second gives 2(N − f) > N, so N > 2f, so N ≥ 2f + 1. Everything about cluster sizing is that line.
| N | Quorum (majority) | Failures tolerated |
|---|---|---|
| 3 | 2 | 1 |
| 4 | 3 | 1 |
| 5 | 3 | 2 |
| 6 | 4 | 2 |
| 7 | 4 | 3 |
It also explains why even cluster sizes buy nothing: N = 4 tolerates one failure exactly as N = 3 does, and costs an extra copy of everything.
Why it does not scale out
In steady state a decision costs one RTT and one durable write, with 2(N − 1) messages. But the leader sends and receives all of them, so leader work is O(N) per decision. Adding members increases fault tolerance and decreases throughput. So consensus is never a data path (what goes through it). You run thousands of small groups, one per partition, instead of one wide group: sharded consensus, not bigger consensus.
Why the four algorithms look alike
Multi-Paxos, Raft, ZAB and Viewstamped Replication all have the same skeleton:
- a monotonic epoch;
- a quorum-elected leader per epoch;
- a rule that a new leader adopts the most up-to-date committed prefix of the log;
- commit once a quorum has replicated the entry.
The differences are entirely in where the reconciliation work sits. Raft restricts who may be elected: a candidate whose log is behind cannot win, so recovery is trivial, and the constraint is paid at election time. Paxos allows anyone to be elected and makes the new leader re-propose whatever it discovers, paying at recovery time. It is the same total work, relocated. The reason Raft won mindshare is not performance. It is that moving the work into election moved it into the rarely executed path, and made the invariant statable in one sentence.
EPaxos: the right algebra removes the coordinator
An interesting variant is EPaxos and its descendants. If two commands commute (their order does not matter, like adding two different items to a set), they need no order between them. So non-conflicting commands commit in one round trip with no leader at all. That is "the right algebra removes the coordinator" in its consensus form. Honest status: it is contested engineering, not settled practice. Dependency tracking and recovery complexity have kept deployment rare, and the systems that ship it hedge. It is worth knowing as proof that leadership is a consequence of assumed non-commutativity, not a requirement of agreement.
The leader as the one designated write
Finally, the leader is the designated version cell at its plainest: the entry committed at index i by a quorum is the single designated write that defines what all other replicas mean. No simultaneity anywhere, one designated event, everything else defined by reference to it.
Compression: consensus buys a total order over decisions at one RTT plus one fsync, scales fault tolerance rather than throughput, and its variants differ only in whether log reconciliation is paid at election or at recovery.