Consensus Algorithms

Consensus is the problem of getting a set of distributed nodes to agree on a single value, or a single ordered sequence of values, even though nodes can crash, restart, or experience arbitrary network delays. It sounds simple, but the FLP impossibility result (Fischer, Lynch, Paterson, 1985) proves that no fully asynchronous consensus algorithm can guarantee both safety and termination if even one node may fail — so every practical consensus algorithm makes some timing assumption (like using timeouts) to make progress in practice, while still guaranteeing safety (never agreeing on two different values) under all conditions. Consensus is the foundation underneath distributed locks, leader election, configuration stores, and replicated logs — anywhere a cluster needs a single, agreed-upon source of truth despite individual node failures.

Paxos, introduced by Leslie Lamport, was the first widely studied consensus algorithm proven correct under partial synchrony. It works in two phases: a 'prepare' phase where a proposer asks a majority of acceptors to promise not to accept any proposal older than the one it's about to send, and an 'accept' phase where the proposer sends its actual value and acceptors accept it if they haven't promised otherwise in the meantime. Paxos guarantees safety (only one value is ever chosen) as long as a majority of nodes are reachable, but it is famously difficult to implement correctly and even harder to extend to a continuously replicated log (Multi-Paxos), which is why it earned a reputation for being conceptually elegant but practically painful — most engineers encounter it via derivative systems (like Chubby or Spanner) rather than implementing it directly.

Raft, published by Diego Ongaro and John Ousterhout in 2014, was explicitly designed to be easier to understand and implement than Paxos while providing equivalent guarantees. Raft decomposes consensus into three clearly separated subproblems: leader election (nodes use randomized timeouts to elect a single leader when the previous one fails or none exists), log replication (the leader appends entries to its log and replicates them to followers, committing an entry only once a majority have stored it), and safety (mechanisms ensuring a newly elected leader always has all previously committed entries, so committed data is never lost or overwritten). Because the leader is the single point that orders all writes during its term, clients get a strong, easy-to-reason-about model: all state changes flow through one leader at a time, and Raft's leader election guarantees at most one leader can be active per term. Raft powers etcd, Consul, and CockroachDB's metadata layer, among many others.

Consensus is expensive: it requires a network round-trip to a majority of nodes for every committed decision, which adds latency and limits throughput compared to systems that avoid coordination entirely (like AP/eventually-consistent stores). This is why well-designed systems use consensus sparingly — for a small amount of critical metadata (leader pointers, cluster membership, configuration) — rather than routing every single application write through a consensus protocol. Databases like CockroachDB and Spanner use consensus (Raft or Paxos variants) per data shard/range, so consensus overhead is bounded and parallelized across many independent groups rather than being a single global bottleneck. This is also why production clusters are almost always sized 3, 5, or 7 nodes: a cluster survives f failures with 2f+1 total nodes, and an even-sized cluster (like 4) tolerates no more failures than the next smaller odd-sized one (3), so the extra node adds cost without added fault tolerance.