Consensus Algorithms

What it is

Distributed consensus is the problem of getting a set of nodes in a network to agree on a single value (or sequence of values) even when some nodes fail or messages are delayed. A consensus algorithm must satisfy three properties: agreement (all non-faulty nodes decide on the same value), validity (the decided value must have been proposed by some node), and termination (all non-faulty nodes eventually decide). In practice, consensus underpins replicated logs, leader election, distributed locks, and coordination services.

Why it exists

Without consensus, replication is unreliable: two nodes can independently accept conflicting writes, diverge in their state, and produce inconsistent results. Consensus is the theoretical and practical foundation for strong consistency in distributed systems. The FLP impossibility result (Fischer, Lynch, Paterson 1985) proves that no deterministic consensus algorithm can guarantee termination in an asynchronous system with even one faulty process. In practice, this is resolved by adding timing assumptions (partially synchronous model) and randomisation, allowing algorithms like Paxos and Raft to make progress under realistic conditions.

When to use

• You need a replicated log with linearisable semantics (etcd, ZooKeeper, Consul for configuration).
• Leader election must be safe: exactly one leader at a time with no split-brain.
• Distributed locking with strong safety guarantees.
• Metadata services or coordination primitives that underpin a larger system.
• Cluster sizes are small (3–7 nodes) — consensus does not scale to hundreds of peers.

When not to use

• High-throughput data paths — consensus adds latency (at least one round trip to a majority before committing).
• Geographically distributed clusters with hundreds of milliseconds of latency between regions.
• Systems tolerating eventual consistency — CRDTs or gossip provide better throughput with weaker guarantees.
• Large clusters — consensus quorum overhead grows with cluster size; use hierarchical or sharded designs.

Typical architecture

Raft is the most widely understood modern consensus algorithm. It separates the problem into three sub-problems: leader election, log replication, and safety.

Raft — Log Replication
═══════════════════════

       Leader                Follower 1        Follower 2
         │                      │                   │
  Client write                  │                   │
         │                      │                   │
    Append to local log         │                   │
         │──── AppendEntries ───►│                   │
         │──── AppendEntries ────────────────────────►
         │◄─── ACK ─────────────│                   │
         │◄─── ACK ──────────────────────────────────│
         │                      │                   │
   Majority ACKs received                           │
   Commit entry, advance commitIndex               │
         │──── AppendEntries (commitIndex) ─────────►│
         │──── AppendEntries (commitIndex) ───────────►
         │                      │                   │
   Reply to client              │                   │

  Election term: each node has a random timeout.
  Node that times out first sends RequestVote.
  Candidate needs majority votes to become leader.
  Terms prevent stale leaders from committing.

Pros and cons

Implementation notes

Paxos vs Raft: Paxos (Lamport 1989) is the original consensus algorithm. Single-decree Paxos agrees on one value; Multi-Paxos extends it to an ordered log by reusing a leader across multiple rounds. Paxos is correct but underspecified — real implementations make dozens of undocumented decisions. Raft was designed explicitly to be understandable and fully specifies log matching, election safety, and log compaction. For new implementations, choose Raft. Viewstamped Replication (VSR) predates Paxos and is equivalent; it is the basis of some production systems including the original Google Chubby design.

Byzantine Fault Tolerant (BFT) consensus: Paxos and Raft assume crash-fault tolerance — nodes fail by stopping, not by sending malicious messages. Practical Byzantine Fault Tolerance (PBFT) and its successors (Tendermint, HotStuff, used in blockchain consensus) tolerate Byzantine nodes but require 3f+1 nodes to tolerate f failures and have higher message complexity.

etcd uses Raft with a WAL for durability. ZooKeeper uses ZAB (ZooKeeper Atomic Broadcast), which is similar to Paxos. Both provide linearisable reads (with appropriate settings) and are suitable for coordination metadata but not as general-purpose databases.

Common failure modes

• Leader thrashing: unstable network causes frequent elections; heartbeat and election timeout tuning is critical.
• Split vote: two candidates receive equal votes in the same term; Raft resolves by randomising election timeouts.
• Stale leader: a leader that has been partitioned from the majority continues serving reads, returning stale data without read linearisation (use quorum reads or lease-based reads).
• Log divergence: a crashed leader had uncommitted entries that followers didn't replicate; Raft's log matching property resolves this on recovery.
• Membership change races: adding or removing nodes incorrectly can create two independent majorities; use joint-consensus or single-server-at-a-time membership changes.

Decision checklist

• Do you require linearisability, or would eventual consistency suffice?
• Is your cluster size appropriate (3, 5, or 7 nodes for standard fault tolerance)?
• Have you tuned heartbeat intervals and election timeouts for your network latency?
• Are you protecting against Byzantine failures or only crash failures?
• Have you considered using an existing consensus service (etcd, ZooKeeper) rather than implementing your own?
• Is the consensus group small enough to avoid quorum-majority bottlenecks at your target write throughput?

Example use cases

• etcd serving as the backing store for Kubernetes control plane state.
• Apache ZooKeeper providing distributed coordination for Kafka (leader election, topic metadata).
• CockroachDB using Raft per-range to replicate SQL data with serialisable isolation.
• Consul using Raft for service registry and key-value store with strong consistency.

Related patterns

• Leader Election — a primary application of consensus; Raft's leader election is consensus-based.
• Distributed Locking — consensus-backed stores (etcd, ZooKeeper) provide the safest locking primitives.
• Distributed Coordination — ZooKeeper and etcd expose consensus as a coordination service.

Further reading

• In Search of an Understandable Consensus Algorithm (Raft) — Ongaro & Ousterhout — the original Raft paper, highly readable.
• Paxos Made Simple — Leslie Lamport — accessible description of Paxos from its inventor.
• Impossibility of Distributed Consensus with One Faulty Process — Fischer, Lynch, Paterson (FLP) — the foundational impossibility result.