Consensus

Why it matters

Which node is the leader? What is the current configuration? Who holds the lock? Which transaction committed first? Every one of these needs a group of machines to agree on a single answer even while some of them crash or lose connectivity, and to never disagree. Consensus is the algorithmic core that makes that possible, and it sits inside every coordination service, every strongly consistent database and every leader election that actually works. Knowing what it guarantees, what it costs and where to put it is senior-level system design.

The idea

Consensus is the problem of a set of nodes each proposing a value and all deciding on the same one, under failures. A correct algorithm satisfies:

1. 1

   Agreement (safety)

   No two correct nodes decide different values. Ever. Even during partitions, crashes and message loss.
2. 2

   Validity (safety)

   The decided value was proposed by some node; the algorithm cannot invent one.
3. 3

   Termination (liveness)

   Every correct node eventually decides, provided the network is eventually well-behaved enough.

Safety is never traded. Liveness is what you give up when the network misbehaves: FLP proves no asynchronous algorithm can guarantee termination with even one faulty node, so practical algorithms guarantee safety always and liveness when timeouts and leaders stabilise.

Why majorities

With 2f+1 nodes, any two majorities (f+1 each) overlap in at least one node. That overlap is the whole trick: a value accepted by a majority cannot be contradicted by another majority without some node knowing about both, so later rounds can discover and preserve earlier decisions. A cluster of 2f+1 tolerates f failures: three nodes survive one, five survive two. Even sizes buy nothing (four nodes still survive only one failure) and seven or more is unusual because every decision costs a round trip to a majority.

From one value to a service: replicated state machines

Agreeing on one value is a building block; what systems need is a replicated log: an ordered sequence of commands that every replica applies in the same order, so that deterministic replicas stay identical. Run consensus once per log slot (or, more efficiently, elect a stable leader that proposes slots in order and only runs full consensus to choose the leader), and you have a replicated state machine: a service with the semantics of one machine and the fault tolerance of many. This is how etcd, ZooKeeper, Consul, Spanner's groups, CockroachDB's ranges and Kafka's controller work.

The algorithms

The next two lessons cover Paxos and Raft; the rest of this module shows what you build on top of them.

What consensus costs

Every decision is at least one round trip from leader to a majority and back: a few milliseconds in one data centre, 50 to 150 ms across regions. Throughput is bounded by the leader. Under partition, the minority side cannot decide anything, which is the CP choice made concrete. Membership changes, disk durability of the log and leader failover are each sources of subtle bugs. These costs are why consensus is used for small, critical state and not as a general database.

Where to put it

Use a consensus-based coordination service (etcd, ZooKeeper, Consul) for cluster membership, configuration, leader election and locks: small data, modest write rates, correctness essential. Use consensus-replicated storage (Spanner, CockroachDB, distributed SQL) when the data itself needs strong consistency across machines. Do not put high-volume application data through a consensus log unless the product requires linearizability for it, and never use consensus where a single leader with asynchronous replicas and clear failover already meets the requirement.

Trade-offs

Consensus buys agreement that survives f failures with no possibility of divergence, and pays with majority round trips on every decision, leader bottlenecks, unavailability for the minority under partition and real implementation complexity. The design skill is to confine it to the small pieces of state where its guarantee is worth that price and to build everything else on top.

In an interview

Place it precisely: "Leader election, configuration and locks live in a three-node etcd cluster (Raft), which tolerates one failure and decides in a few milliseconds. Application data is in Postgres with a synchronous standby, not in the consensus log. If we go multi-region with strong consistency we would use a consensus-replicated database and accept the cross-region commit latency." Saying "2f+1, tolerates f" and naming the latency cost is what the question is checking.