Consensus is the guarantee that a group of nodes will agree on the same value or sequence of operations, even when some of them crash, some messages are lost or delayed, and the network itself occasionally partitions. It sounds abstract until you name what depends on it: a replicated database agreeing on transaction order, a cluster agreeing on who the leader is, a configuration store agreeing on the current value of a key. Consensus algorithms, Paxos and Raft chief among them, are the formally proven protocols that make these agreements safe, and understanding what they actually guarantee, and what they cost, is the difference between using them correctly and quietly breaking their assumptions.
What consensus actually guarantees
A consensus algorithm gives you, at minimum:
- Agreement — no two non-faulty nodes decide on different values for the same slot.
- Validity — the value decided was actually proposed by some node, with no invented values.
- Termination — every non-faulty node eventually decides, given enough of the network is working.
- Fault tolerance — the system keeps working as long as a majority, or quorum, of nodes are up and can talk to each other.
Crucially, consensus does not promise progress when a majority is unreachable, and this is deliberate, not a limitation to work around. A system that kept accepting writes during a network partition without a quorum would be choosing availability over correctness, which is a different and generally more dangerous tradeoff for anything requiring strong consistency.
Why quorums, not unanimity
Requiring every node to agree would mean one dead node halts the entire system forever. Consensus algorithms instead require a majority, ⌊n/2⌋ + 1 of n nodes:
| Cluster size |
Nodes needed for quorum |
Nodes that can fail |
| 3 |
2 |
1 |
| 5 |
3 |
2 |
| 7 |
4 |
3 |
This is also why cluster sizes are almost always odd. A 4-node cluster tolerates the same 1 failure as a 3-node cluster while costing an extra node, because you still need 3 out of 4 for majority.
Where consensus shows up
| System |
What it uses consensus for |
| etcd, Consul |
Agreeing on the current value of configuration keys, and on leader election |
| CockroachDB, TiDB |
Agreeing on transaction commit order across replicas |
| Modern Kafka (KRaft mode) |
Agreeing on partition metadata and controller leadership |
| Distributed lock services |
Agreeing on who currently holds a lock |
If you're not building one of these systems yourself, you almost certainly consume consensus indirectly, through etcd, your database's replication layer, or your orchestrator, rather than implementing Paxos or Raft directly.
Common mistakes
Confusing consensus with simple replication. Copying data to replicas is not consensus; consensus is specifically the protocol that lets replicas agree on order and value despite failures and delays. Asynchronous replication without consensus can silently lose committed data on failover.
Assuming consensus means always available. By design, consensus systems refuse to make progress without a quorum. That's a deliberate consistency-over-availability choice, not a bug. See the PACELC theorem for how this tradeoff is usually framed.
Treating Byzantine fault tolerance as the default assumption. Most infrastructure consensus, including Raft, Paxos, and ZooKeeper's ZAB, assumes crash failures, not malicious nodes. Byzantine fault-tolerant protocols exist but cost significantly more messages and are overkill for a typical internal cluster.
Under-sizing the cluster. A 2-node cluster has no majority possible if either node is unreachable; it can't tolerate any failure and isn't really doing consensus. Odd numbers of 3 or 5 are the practical minimums for real fault tolerance.
FAQ
What's the difference between Paxos and Raft?
Both solve the same problem; Raft was explicitly designed to be easier to understand and implement correctly, decomposing the problem into leader election, log replication, and safety as separate concerns. See Raft vs Paxos for the full comparison.
Do I need to implement a consensus algorithm myself?
Almost never. Use an existing, battle-tested implementation, such as etcd, ZooKeeper, or a consensus-backed database, rather than writing Paxos or Raft from scratch. The edge cases are notoriously easy to get subtly wrong.
How is consensus related to the CAP theorem?
Consensus algorithms are inherently CP: consistent and partition-tolerant. They refuse to decide without a quorum rather than risk disagreement. See the PACELC theorem for the fuller latency-vs-consistency picture.
Can consensus tolerate a minority of nodes lying, not just crashing?
Only Byzantine fault-tolerant variants can, and they need 3f+1 nodes to tolerate f malicious nodes, versus 2f+1 for crash-only fault tolerance, a meaningfully higher cost.
Where to go next