Skip to main content

Consensus Algorithms

Consensus is the problem of getting multiple nodes to agree on a single value — even when some nodes might be slow, crash, or become unreachable — and having every node that does agree end up with the same answer. It sounds abstract, but it's the problem underneath several very concrete things covered elsewhere in this course: which replica becomes the new database leader, which node holds a distributed lock, what the current, authoritative state of a cluster's membership is.

Why this is hard, in one sentence​

On an unreliable network, a node can never fully distinguish "that other node is dead" from "that other node is just slow, or the network between us is." Heartbeats approximate an answer with a timeout, but a timeout is a guess, not a certainty — and consensus algorithms exist specifically to let a group of nodes reach a safe, agreed-upon decision despite that fundamental uncertainty, rather than each node guessing independently and risking two different nodes both believing they're in charge.

The concrete case: leader election​

The clearest instance of consensus in this course is exactly the scenario Database Architectures names as needing it: when a database's leader dies, its followers need to agree on exactly one replacement. If two followers each independently decide "the leader is unreachable, I'll promote myself," and both start accepting writes, the result is split-brain — two nodes both believing they're the authoritative leader, accepting conflicting writes that can never be fully reconciled. Consensus is what prevents this: a properly implemented algorithm guarantees that even if multiple nodes propose themselves as the new leader simultaneously, all surviving nodes converge on the same one.

System Design Lab

Why a simple majority vote is the key idea​

Most practical consensus algorithms (Paxos and its more approachable successor, Raft, are the two named constantly in this space) are built around quorum: a decision is only final once a majority of nodes agree to it. This is what makes split-brain structurally impossible rather than just unlikely — in a cluster of 5 nodes, a majority is 3, and it's mathematically impossible for two disjoint groups of nodes to each independently gather a majority at the same time, since any two majorities out of 5 nodes must overlap by at least one node. That overlapping node is what prevents two conflicting decisions from both becoming "official" simultaneously.

This is also why consensus clusters are typically sized with odd numbers of nodes (3, 5, 7) — it maximizes fault tolerance per node added without wasting a node on a size that doesn't actually improve the majority threshold.

Consensus as a building block, not just leader election​

Once a cluster can reliably agree on values, that capability becomes reusable infrastructure for other problems: Distributed Locking is frequently implemented on top of a consensus system (ZooKeeper, etcd, and similar tools are themselves built on Paxos- or Raft-like consensus), because "who holds the lock right now" is exactly the kind of single, agreed-upon value consensus is designed to guarantee. This is why it's common to see the same underlying consensus-backed coordination service used for leader election, configuration management, and distributed locks all at once — they're the same problem wearing different names.

The cost: consensus isn't free​

Reaching agreement requires multiple round trips between nodes before a decision is final, which is real added latency compared to a single node just deciding something on its own — this is the same latency-for-safety tradeoff that runs through CAP Theorem: a consensus-backed system is deliberately choosing consistency and correctness at the cost of speed and, during a severe enough partition, availability (a cluster that can't reach a majority can't make progress at all, by design, rather than risk a wrong answer).

Why this matters in an interview​

Naming "consensus" (and ideally Raft or Paxos by name) is the right move whenever a design needs multiple nodes to agree on one thing safely — leader election, distributed configuration, a distributed lock — rather than describing it vaguely as "the nodes coordinate." It's also worth being ready to explain why it's hard (the network can't reliably distinguish slow from dead) and why majority quorum is the standard fix (it makes split-brain mathematically impossible, not just unlikely).

Consensus-based coordination vs. a single coordinator: pros and cons​

Pros

  • Makes split-brain mathematically impossible via majority quorum, not just unlikely
  • Survives the failure of a minority of nodes without losing correctness
  • Reusable as the foundation for leader election, locking, and configuration together

Cons

  • Requires multiple round trips before a decision is final, adding real latency
  • Needs an odd-sized cluster and enough healthy nodes to form a majority to make progress at all
  • Considerably more complex to implement and reason about than a single coordinator

Further Reading​

Saved locally in your browser — visible in the sidebar as you go.