Skip to main content

Fault-Tolerant Consensus

Adapted from: Martin Kleppmann, Designing Data-Intensive Applications (O'Reilly, 2017), Chapter 9 — rewritten and condensed for teaching.

Distributed Transactions and Two-Phase Commit worked through 2PC — a real, working solution to atomic commit, but a fundamentally blocking one: a crashed coordinator can leave the whole system stuck, indefinitely, waiting for it to recover. This lesson tackles the general consensus problem head-on, and shows how real algorithms fix exactly the weakness 2PC couldn't shake — by formalizing precisely what "reaching consensus" has to mean, and by using quorums (rather than unanimous agreement) to stay available even when some nodes are down.

Defining Consensus Precisely​

Consensus, formalized: one or more nodes propose values, and the algorithm decides on exactly one of them. (Picture several customers simultaneously trying to book the last seat on a flight — each node handling one customer's request proposes that customer's ID, and the algorithm's decision determines who actually gets the seat.) A correct consensus algorithm must satisfy four properties:

  • Uniform agreement — no two nodes ever decide differently.
  • Integrity — no node decides more than once.
  • Validity — whatever value a node decides on, it must have been genuinely proposed by some node (this rules out trivial "cheats," like an algorithm that just always decides null regardless of input — technically satisfying agreement and integrity, but obviously useless).
  • Termination — every node that doesn't itself crash must eventually decide something.

The first three — agreement, integrity, validity — are safety properties, in the precise sense already covered in Knowledge, Truth, and Lies: violated once, violated forever, no undoing it. Termination is different — it's a liveness property, and it's specifically what formalizes genuine fault tolerance: the algorithm can't simply sit around doing nothing forever; it has to make progress, even while some nodes have failed.

If you genuinely don't care about fault tolerance, satisfying agreement, integrity, and validity is trivial — just hardcode one node as a permanent "dictator" and let it decide everything. The catch, of course: the instant that one node fails, the whole system can no longer decide anything at all — which is precisely the failure mode 2PC has, with its coordinator playing the dictator role. A correct consensus algorithm has to keep making progress even when some nodes fail — which is exactly the piece 2PC was missing.

Naturally, there's still a hard limit: if literally every node crashes and none come back, no algorithm anywhere can decide anything. It's provable that any consensus algorithm needs at least a majority of nodes functioning correctly to guarantee termination — the exact same quorum concept from Leaderless Replication. Termination genuinely depends on that majority assumption holding — but the safety properties (agreement, integrity, validity) hold unconditionally, even during a severe outage where a majority of nodes are down or unreachable. A large-scale failure can stop the system from processing new requests entirely — but it can never make the consensus algorithm produce an outright wrong, corrupted decision.

An assumption worth stating explicitly

Nearly all standard consensus algorithms assume no Byzantine faults — every node that responds at all is assumed to be following the protocol honestly, exactly the assumption Knowledge, Truth, and Lies already covered in depth. Byzantine-tolerant consensus is possible, but it demands more than two-thirds of nodes to be honest, and it's considerably more complex — genuinely necessary in a few specific domains (aerospace, mutually-distrusting multi-organization systems), but well beyond what most datacenter systems actually need.

Check: the formal consensus properties​

Quiz

Uniform agreement, integrity, validity, and termination

1 / 3

Why is the validity property necessary, given that agreement and integrity already seem to define "everyone decides the same thing, once"?

Pick an answer to see if you are right.

Consensus Algorithms Are (Usually) Total Order Broadcast Algorithms​

The best-known fault-tolerant consensus algorithms — Viewstamped Replication (VSR), Paxos, Raft, and Zab (ZooKeeper's algorithm) — share real family resemblances, though they're far from identical in their details. Most of them don't actually implement the "decide one value" formalism directly at all — instead, they decide on a sequence of values, which makes them, functionally, total order broadcast algorithms. That's not a coincidence: total order broadcast is equivalent to running repeated rounds of consensus, one round per message delivered — agreement guarantees every node delivers the identical messages in the identical order; integrity guarantees no duplicates; validity guarantees nothing gets fabricated or corrupted; termination guarantees nothing gets silently lost. VSR, Raft, and Zab implement total order broadcast directly (more efficient than literally running one-value-at-a-time consensus repeatedly); Paxos has an equivalent optimization known as Multi-Paxos.

The Chicken-and-Egg Problem: Electing a Leader Requires... Consensus​

Here's a genuine puzzle worth sitting with. Leaders and Followers already covered single-leader replication — the leader determines write order, followers apply the exact same writes in the exact same order. Isn't that already total order broadcast? So why wasn't consensus a concern back then?

The honest answer comes down to how the leader gets chosen. If a human operator manually designates the leader, you effectively have a "dictator"-style consensus — trivially safe, but with zero termination guarantee: if that manually-chosen leader dies, the system stays down for writes until a human manually intervenes. Some databases instead perform automatic leader election and failover — genuinely closer to real, fault-tolerant total order broadcast. But Knowledge, Truth, and Lies already established the core problem here: all nodes need to agree on who the leader actually is — otherwise you risk exactly the split-brain scenario that whole lesson was built around. So electing a leader itself requires consensus. And if consensus is essentially just total order broadcast, and total order broadcast essentially requires a leader to sequence messages in the first place... it looks like electing a leader requires already having a leader. How does anything ever actually get off the ground?

Breaking the Loop: Epoch Numbers and Quorums​

Every one of these consensus protocols internally uses a leader in some form — but crucially, none of them guarantee that leader is globally, permanently unique. Instead, they make a strictly weaker — but still fully sufficient — guarantee: each protocol defines an epoch number (called the ballot number in Paxos, the view number in VSR, the term number in Raft), and guarantees the leader is unique only within a given epoch.

Whenever the current leader is suspected dead, the remaining nodes hold an election for a new one, tagged with a strictly incremented epoch number — so epoch numbers form a totally ordered, monotonically increasing sequence. If two nodes from different epochs ever conflict about who's really the leader, the one from the higher epoch always wins.

Before a leader is allowed to actually decide anything, it must first confirm no other node — possibly from a higher, more recent epoch — could override it. Since a node's own private belief about its leadership status proves nothing on its own (the exact theme from Knowledge, Truth, and Lies), a leader must actually collect votes from a quorum of nodes before every single decision — sending its proposal out and waiting for a quorum to affirmatively respond in favor, with each node only voting "yes" if it's not aware of any other leader with a higher epoch number.

This produces two full rounds of voting: one to elect a leader in the first place, and a second, separate round for every individual proposal that leader wants to actually decide on. The key structural insight that makes it all work: those two quorums are guaranteed to overlap — if a proposal vote succeeds, at least one node that voted for it must also have participated in the most recent leader election. So if a proposal's vote reveals no higher epoch number anywhere, the current leader can be genuinely, safely confident that no higher-epoch election has happened behind its back — and can commit to the decision.

This voting shape looks superficially similar to 2PC — but two differences are exactly what make it correct where 2PC fell short: the coordinator (leader) here is genuinely elected, not hardcoded, and — critically — a proposal only needs a majority of votes, not unanimous agreement from every single node, the way 2PC's coordinator required.

Practice: enforce epoch-based leader validity​

Implement the core rule directly: a node only accepts a proposal from a leader whose claimed epoch is at least as high as the highest epoch it has ever observed — anything lower gets rejected outright, exactly the mechanism that lets a node detect it's talking to a stale, already-superseded leader.

Check: consensus algorithms, leader election, and epochs​

Quiz

Total order broadcast, the leader-election puzzle, and epoch quorums

1 / 3

Why is total order broadcast equivalent to running repeated rounds of consensus?

Pick an answer to see if you are right.

Consensus Isn't Free​

Consensus algorithms are a genuine breakthrough — real, concrete safety guarantees in an environment where almost everything else is uncertain, while still remaining fault-tolerant (able to keep making progress as long as a majority of nodes are healthy and reachable). But that power comes at real, tangible cost, which is exactly why they aren't used absolutely everywhere:

  • The voting process is a form of synchronous replication. Leaders and Followers already covered why many databases deliberately choose asynchronous replication instead, purely for better performance — accepting the real risk that some committed data could be lost on failover, in exchange for speed.
  • A strict majority is always required to make progress. Tolerating one failure needs a minimum of three nodes (two of three remain a majority); tolerating two needs a minimum of five. A network fault that cuts off more than a minority of nodes leaves the majority-holding side able to keep working — and the rest simply blocked, echoing the same fundamental linearizability-vs-availability trade-off already covered in Linearizability.
  • Membership is typically fixed. Most consensus algorithms assume a static set of voting nodes — you can't just casually add or remove nodes from a live cluster. Dynamic-membership extensions do exist, but they're considerably less well-understood than the static-membership case.
  • Timeouts are still how failure gets detected. In environments with genuinely variable network delay — especially geographically distributed deployments — a node can easily, falsely conclude the leader has died purely from a transient network blip. This doesn't threaten the safety properties, but frequent, unnecessary leader elections can badly hurt performance, since the system can end up spending more wall-clock time re-electing leaders than actually doing useful work.
  • Some algorithms are unusually sensitive to specific, narrow network failure patterns. Raft, notably, has a documented edge case: if every link in the network works perfectly except one specific, consistently flaky connection, Raft can get stuck in a genuinely pathological state — leadership repeatedly bouncing back and forth between two nodes, or a leader being continually forced to resign, such that the system effectively never makes real progress. Designing algorithms that are more robust against this specific class of network pathology remains a genuinely open research area.

Membership and Coordination Services​

ZooKeeper and etcd get described as "distributed key-value stores" or "coordination services," and their basic API — read/write a value for a key, iterate over keys — genuinely does look database-like on the surface. So why do they go to the trouble of running a full consensus algorithm internally, when most databases don't?

You'll rarely reach for ZooKeeper directly as an application developer — it isn't actually well suited as a general-purpose database. More often, you end up depending on it indirectly, through some other project built on top of it (HBase, Hadoop YARN, Kafka, and many others all run ZooKeeper quietly in the background). ZooKeeper and etcd are deliberately designed to hold a genuinely small amount of data — small enough to comfortably fit entirely in memory (though still written to disk for durability) — replicated across every node using fault-tolerant total order broadcast, exactly the technique this lesson has been building toward. Modeled after Google's Chubby lock service, they bundle together a specific, particularly useful combination of features:

  • Linearizable atomic operations. An atomic compare-and-set lets you build a genuine lock: if several nodes race to perform the same operation, exactly one succeeds — and the consensus protocol underneath guarantees that outcome is atomic and linearizable, even through node failures or network interruptions. (Distributed locks are typically implemented as leases — with an expiry, so they eventually release automatically if the holding client itself fails, exactly the process-pause scenario already covered in Unreliable Clocks.)
  • Total ordering of operations. Knowledge, Truth, and Lies already covered fencing tokens as the fix for stale-leader lock disputes — ZooKeeper provides exactly this natively, via a monotonically increasing transaction ID (zxid) and version number (cversion) attached to every operation.
  • Failure detection. Clients hold a long-lived session against ZooKeeper servers, with periodic heartbeats confirming liveness on both sides. If heartbeats stop for longer than the configured session timeout, ZooKeeper declares the session dead — and any locks held under that session (its ephemeral nodes) can be configured to automatically release right then.
  • Change notifications. A client can watch a value or lock for changes, rather than having to poll repeatedly — letting it find out immediately when another client joins the cluster, or when another client's session times out and its locks vanish.

Only the first of these — linearizable atomic operations — technically requires consensus on its own. It's the combination of all four that makes systems like ZooKeeper so genuinely valuable for distributed coordination specifically.

What Coordination Services Are Actually Used For​

Allocating work to nodes. A classic fit: several instances of a service exist, and exactly one needs to be chosen as leader or primary — if it fails, another should take over. Equally useful for deciding which node owns which partition of a sharded resource, and rebalancing that ownership as nodes join, leave, or fail. Careful combination of atomic operations, ephemeral nodes, and change notifications lets an application recover from faults automatically, with zero human intervention — genuinely difficult to get exactly right (which is exactly why higher-level libraries like Apache Curator exist), but still meaningfully easier and more reliable than attempting to implement the underlying consensus algorithm entirely from scratch.

An application might start on a single node and eventually scale to thousands — running a majority vote across thousands of nodes directly would be hopelessly inefficient. ZooKeeper sidesteps this by running its own consensus only among a small, fixed number of dedicated nodes (typically three or five), while still supporting an arbitrarily large number of client applications built on top. In effect, it outsources the genuinely hard parts — consensus, operation ordering, failure detection — to a small, dedicated, purpose-built external service. ZooKeeper-managed data is also typically slow-changing by design — "node X is the current leader for partition 7" — not intended for high-frequency application runtime state that might change thousands of times per second.

Service discovery. ZooKeeper, etcd, and Consul commonly get used to answer "what IP address do I actually connect to for this service?" — particularly useful in cloud environments where instances routinely come and go. It's worth being precise, though: service discovery on its own doesn't actually require consensus — DNS solves basically the identical problem using layered caching, is famously not linearizable, and that's fine, since a little staleness there is rarely a real problem, so long as DNS itself stays reliably available. Leader election, on the other hand, genuinely does need consensus — so if your system already runs a consensus service for leader election, it's a natural, low-cost extra step to expose that same leader information for service discovery too, often via dedicated read-only replicas that stream the consensus log asynchronously without participating in voting, serving non-linearizable reads cheaply and at scale.

Membership services. This whole category traces back to research going back to the 1980s, historically important for genuinely high-reliability systems like air-traffic control. A membership service determines exactly which nodes currently count as live, active cluster members. Faults, Partial Failures, and Unreliable Networks already established that unbounded network delay makes reliably detecting node failure fundamentally impossible on its own — but pairing failure detection with consensus lets the whole cluster reach genuine agreement on membership, even though any individual node might still occasionally be wrongly declared dead. Having that agreed-upon membership list is nevertheless enormously useful — leader election, for instance, can simply mean "pick the lowest-numbered node among the current, agreed-upon members" — a rule that only actually works if every node genuinely shares the same view of who the current members even are.

Check: coordination services​

Quiz

ZooKeeper, etcd, and what coordination services are for

1 / 3

Of ZooKeeper's four bundled features (linearizable atomic operations, total ordering, failure detection, change notifications), which one is the ONLY one that strictly requires consensus on its own?

Pick an answer to see if you are right.

The whole chain, tied together

Across this lesson and the three before it, a genuinely striking pattern has emerged: linearizable compare-and-set, total order broadcast, atomic commit, and consensus itself are all formally equivalent problems. Solve any one of them in a fault-tolerant way, and you can mechanically build working solutions to all the others on top of it. That's exactly why real coordination services like ZooKeeper and etcd — built around one solid, well-tested consensus implementation — turn out to be such a powerful, broadly reusable foundation: locks, leader election, fencing tokens, and linearizable storage all fall directly out of that single underlying capability, rather than needing four separate, independently-hard problems solved from scratch.

Key takeaways
  • Consensus requires four properties: agreement, integrity, and validity (safety — must hold unconditionally) plus termination (liveness — genuine fault tolerance, requiring a majority of healthy, reachable nodes).
  • Most real consensus algorithms (VSR, Paxos, Raft, Zab) implement total order broadcast directly, since total order broadcast is equivalent to running repeated rounds of consensus, one per delivered message.
  • The apparent "you need a leader to elect a leader" paradox is resolved by epoch numbers (a leader is only guaranteed unique within its own epoch) plus overlapping quorum votes — a genuine improvement over 2PC's fixed, unelected coordinator and its unanimous-vote requirement.
  • Consensus isn't free: it behaves like synchronous replication, requires a strict majority of nodes to make progress, typically assumes static membership, and remains genuinely sensitive to specific network pathologies (Raft's flaky-single-link edge case, notably).
  • ZooKeeper and etcd bundle linearizable atomic operations, total ordering (fencing tokens), failure detection, and change notifications into a small, dedicated, consensus-backed service — used for leader election, work allocation, service discovery, and membership tracking, without every application needing to implement fault-tolerant consensus itself.

Further Reading​