Distributed Consensus

Distributed consensus is the problem of getting a group of independent nodes to agree on a single value (or an ordered log of values) even when some nodes crash, messages are delayed or lost, and there is no shared clock. It underpins replicated state machines: databases, configuration stores (etcd, ZooKeeper), and leader election. The classic algorithms — Paxos and the more understandable Raft — guarantee safety (nodes never disagree on a committed value) and, under reasonable conditions, liveness (progress is eventually made).

Raft simplifies consensus by electing a single leader that handles all client writes and replicates its log to followers. When followers stop hearing from the leader (a heartbeat timeout), one becomes a candidate and starts an election by requesting votes. If it wins a majority, it becomes the new leader. This strong-leader design makes Raft easier to reason about than Paxos: log entries flow only from leader to followers, and the leader's log is authoritative. Each election is tagged with an increasing term number to detect stale leaders.

A quorum is the minimum subset of nodes whose agreement is required to commit a decision — usually a strict majority: (N/2)+1. For a 5-node cluster, quorum is 3. Requiring a majority guarantees that any two quorums overlap in at least one node, which prevents two different decisions from being committed simultaneously (the safety guarantee). It also explains why consensus clusters use odd numbers: a 5-node cluster tolerates 2 failures, the same as a 6-node cluster, so the extra node adds cost without improving fault tolerance.

Split-brain occurs when a network partition divides a cluster and more than one side believes it is in charge, leading to divergent, conflicting state. Quorum prevents this: since a commit requires a majority, only the partition that contains a majority of nodes can make progress; the minority side cannot elect a leader or commit writes and must wait. Term/epoch numbers and leader leases add fencing so a deposed leader on the minority side cannot keep writing. This is why availability is sacrificed for the minority partition — a deliberate CP (consistency-over-availability) choice.

The replicated state machine model says: if every node starts in the same state and applies the same commands in the same order, they all end in the same state. Consensus algorithms achieve this by replicating an append-only log of commands. The leader appends a client command, replicates it to followers, and once a quorum has persisted the entry it is committed and applied to the state machine. Determinism is essential — every replica must produce identical results from identical input, which is why nondeterministic operations (random, wall-clock time) must be handled carefully.