Consensus

Quorums, Raft leader election and log replication, split brain, and what consensus costs.

Consensus is how a group of machines agrees on a value — who the leader is, what the next log entry is, whether a transaction commits — even when some of them crash or messages are lost. You'll rarely implement it in an interview, but it underpins leader election, distributed locks, replicated logs and strongly consistent databases, so you should know what it gives you and what it costs.

Why it's hard

Messages can be delayed, lost or reordered; a slow node looks exactly like a dead one.
Clocks are unreliable, so "who wrote first" can't be decided by timestamps.
Two nodes that each think they're the leader (split brain) can corrupt data.

The FLP result shows no algorithm can guarantee consensus in a fully asynchronous system with even one faulty node. Practical algorithms stay safe (never disagree) always, and make progress whenever the network behaves reasonably — using timeouts.

Quorums

The key idea: decisions require a majority. Any two majorities of the same group overlap in at least one node, so two conflicting decisions can't both be approved.

Use odd sizes: a 4-node cluster tolerates only 1 failure, same as 3. Bigger clusters tolerate more failures but every write waits for more acknowledgements, so 3 or 5 is typical.

Raft in one page

Raft is the most widely taught algorithm (etcd, Consul, CockroachDB, TiKV, Kafka's KRaft). Paxos (Spanner, Chubby) and ZAB (ZooKeeper) are equivalent in what they guarantee.

Client -> [Leader: append to log] -> [Follower A: append + ack] -> [Leader: majority acked → commit + apply] -> Client: reply
[Leader: append to log] -> [Follower B: append + ack] -> [Leader: majority acked → commit + apply]

Leader election — nodes start as followers. If a follower hears no heartbeat within a randomized timeout, it becomes a candidate, increments the term number and asks for votes. A node votes once per term, and only for a candidate whose log is at least as up to date as its own. A majority of votes makes it leader.
Log replication — the leader appends each command to its log and sends it to followers. Once a majority has stored it, the entry is committed: applied to the state machine and acknowledged to the client.
Safety — a new leader always has every committed entry, so committed data is never lost. Stale leaders discover a higher term and step down.

This pattern — a replicated log feeding a deterministic state machine — is how consensus turns into a fault-tolerant database or coordination service.

What it costs

Latency — every write needs a round trip to a majority. Within a region that's around a millisecond; across continents it's tens to hundreds of milliseconds.
Throughput — all writes go through one leader per group. Systems scale by running many consensus groups, one per shard (Spanner, CockroachDB, Kafka partitions).
Availability — a minority partition can't make progress. That's the CP choice in CAP.

Where you'll use it in a design

Leader election and locks — use a coordination service rather than rolling your own. See ZooKeeper & etcd.
Fencing tokens — the term or epoch number from consensus is monotonically increasing; pass it to storage so it rejects writes from a deposed leader.
Strongly consistent storage — Spanner, CockroachDB and etcd replicate each shard with Paxos or Raft.
Metadata services — shard maps, cluster membership and configuration in systems like Kafka, a distributed file system or a key-value store.

[!TIP] Don't put consensus on the hot path unless you need it Coordinate on the small, critical decisions (who owns shard 7, who is leader) and let the bulk data path run without it — for example, a leader elected through etcd then serves reads and writes on its own until its lease expires.

[!INTERVIEW] Explaining failover safely "Each shard's replicas run Raft, so a write is acknowledged only after a majority stores it. If the leader fails, the remaining two of three elect a new one within a couple of seconds and no acknowledged write is lost. A partitioned old leader can't commit anything without a majority, so there's no split brain."