Why Consensus Is Hard

Getting a group of computers to agree on a value sounds like it should be straightforward. After all, humans form consensus all the time—committees vote, juries deliberate, and teams make decisions. Surely computers, with their precise logic and fast communication, can do better?

This intuition is dangerously wrong. The consensus problem in distributed systems is so fundamentally hard that it took decades of research to develop correct solutions, and even today, implementing them correctly is considered one of the most challenging tasks in systems engineering. Distinguished engineers have spent years developing and refining consensus protocols, and bugs in consensus implementations have caused some of the most severe distributed systems failures in production.

In this page, we'll explore exactly why consensus is so hard. Understanding these challenges deeply is essential—not just for implementing consensus protocols, but for reasoning about the fundamental limits of distributed systems.

The most fundamental challenge in distributed consensus is asynchrony—the absence of bounds on message delivery time and process execution speed. In an asynchronous system:

• Messages can take arbitrarily long to be delivered (though they eventually are)
• Processes can execute at arbitrary speeds (even pausing for unbounded periods)
• There is no global clock that all processes can reference
• We cannot assume any bound on how long anything takes

This is the model that best describes real networks like the Internet, where congestion, routing changes, and transient failures can cause arbitrary delays.

Why Asynchrony Breaks Simple Solutions:

Consider the simplest possible 'consensus protocol': designate one node as the decider, everyone sends their proposal to the decider, and the decider picks one and announces it.

This approach fails catastrophically in an asynchronous system:

The Fundamental Dilemma:

Asynchrony creates an impossible situation: we cannot distinguish between a process that has crashed and a process that is merely slow. This seemingly simple observation has profound implications:

• If we wait forever for a slow process, we may never terminate (violating liveness)
• If we proceed without a slow process, it might actually be correct and later interfere (violating safety)

Every consensus protocol must somehow navigate this dilemma. As we'll see when studying the FLP impossibility result, no deterministic protocol can solve consensus in a purely asynchronous system with even one potential failure. This forces real protocols to make timing assumptions or use randomization.

Unlike a single computer that is either working or not, a distributed system experiences partial failures—some components fail while others continue operating. This seemingly obvious observation has deep implications for consensus.

The Spectrum of Partial Failure:

In a distributed system, failure is not binary. Consider all the things that can independently fail:

Why Partial Failure Complicates Consensus:

When failures were total (everything fails together), systems could use simple all-or-nothing approaches. Partial failure creates combinatorial complexity:

1. State divergence: Different nodes may have received different subsets of messages
2. Observational differences: Nodes may have different views of which other nodes are alive
3. Split-brain scenarios: Groups of nodes may become isolated and proceed independently
4. Recovery complications: A node that recovers may have stale state and must be brought up to date

The Quorum Insight:

The fundamental technique for handling partial failures is quorums—requiring decisions to involve overlapping groups of nodes. If every decision requires a majority, then any two decisions must have at least one node in common. That overlapping node provides the 'memory' that prevents conflicting decisions.

But quorums alone aren't sufficient—you also need protocols that correctly use them. A majority vote doesn't help if the voters can change their minds arbitrarily.

A network partition occurs when a network failure divides nodes into two or more groups that cannot communicate with each other. Each group can communicate internally but not with nodes in other groups. Partitions are particularly challenging for consensus because they create isolated 'islands' of nodes.

Why Partitions Are Special:

Network partitions are distinct from node failures in important ways:

• Nodes in a partition are fully functional—they just can't talk to some other nodes
• Both sides of a partition may believe they are the 'correct' side
• Partitions can heal suddenly, requiring reconciliation
• During a partition, requests may still arrive on both sides

The CAP Theorem Connection:

The CAP theorem states that during a network partition, a system must choose between:

• Consistency: Refusing to serve requests to avoid inconsistency
• Availability: Serving requests but potentially becoming inconsistent

Consensus protocols that guarantee safety (agreement) must sacrifice availability during partitions—the minority side of a partition cannot make progress because it cannot achieve a quorum.

Real-World Partition Scenarios:

Network partitions are not theoretical concerns—they happen regularly in production:

1. Cloud availability zone failures: A network issue isolates one AZ from others
2. WAN link failures: Multi-region deployments lose connectivity between regions
3. Switch failures: Top-of-rack switch failure isolates a rack
4. Misconfiguration: Firewall rules incorrectly block traffic
5. Asymmetric partitions: Node A can reach B but not C, while B can reach C

Google's Chubby paper famously noted that network partitions are rare but not rare enough to ignore. Any system that doesn't correctly handle partitions will eventually fail catastrophically.

The Two Generals Problem is a classic thought experiment that illustrates a fundamental limitation of communication over unreliable channels. Understanding it helps explain why achieving consensus is inherently difficult.

The Scenario:

Two allied armies, led by General A and General B, are camped on opposite sides of an enemy city. They can only win if they attack simultaneously. If only one attacks, they lose. The generals can communicate only by sending messengers through the enemy-held city, where messengers may be captured (messages lost).

The question: Is there a protocol that guarantees both generals attack together?

Why No Protocol Works:

Consider any protocol with a finite number of message rounds:

1. General A sends 'Attack at dawn'
2. General B receives it and sends 'Confirmed'
3. General A receives confirmation and sends 'Reconfirmed'
4. ... and so on

At some point, the last message must be sent. The sender of that last message can never be sure it was received. If they attack anyway, they might be attacking alone (the message was lost). If they don't attack, they might be abandoning their ally who is committed.

The Fundamental Insight:

No amount of additional messages resolves the uncertainty. Each additional acknowledgment just shifts the problem to a new final message. This is not a solvable problem with finite protocols over unreliable channels.

Implications for Consensus:

The Two Generals Problem shows that we cannot guarantee simultaneous agreement over unreliable networks. Consensus protocols don't solve this impossibility—they work around it by:

1. Not requiring simultaneity: Processes can decide at different times
2. Using quorums: We don't need all processes, just a majority
3. Ensuring agreement is permanent: Once a value is decided, it stays decided

The key insight is that consensus guarantees agreement on what was decided, not when everyone learns the decision.

Because purely asynchronous consensus is impossible (as we'll see with FLP), practical consensus protocols must make some timing assumptions. Understanding the spectrum of synchrony models is essential for understanding what guarantees different protocols can provide.

The Synchrony Spectrum:

Partial Synchrony: The Practical Middle Ground:

Most practical consensus protocols assume partial synchrony, formalized by Dwork, Lynch, and Stockmeyer (DLS). Two variants exist:

1. Unknown bound model: There exists a bound Δ on message delay, but we don't know what it is. Protocols must work for any Δ.

2. Eventually synchronous model: The system is asynchronous until an unknown time called the Global Stabilization Time (GST), after which messages are delivered within Δ time.

Why Partial Synchrony Works:

These models allow consensus protocols to provide:

• Safety always: Agreement and validity hold regardless of timing (even during asynchronous periods)
• Liveness eventually: Termination is guaranteed once the system becomes synchronous

This separation is crucial: even if the network is misbehaving, the protocol never makes an incorrect decision. It may pause progress (violating liveness temporarily), but it never violates agreement (safety is never compromised).

The Role of Failure Detectors:

Another way to reason about timing is through failure detectors—abstract modules that provide hints about which processes have failed. Different failure detector properties enable different problems:

• Perfect failure detector (P): Never wrong, eventually suspects all failed processes. Too strong for asynchronous systems.
• Eventually perfect failure detector (◇P): May make mistakes during instability but eventually becomes perfect. Achievable in partially synchronous systems.
• Weakest failure detector for consensus (Ω): Provides eventual leader election—eventually all correct processes agree on a leader.

Chandra and Toueg's landmark result showed that Ω is the weakest failure detector that enables consensus. Paxos and Raft both implicitly implement Ω through their leader election mechanisms.

Even with a correct protocol specification, implementing consensus correctly is notoriously difficult. The gap between theory and practice is substantial, and many real-world failures stem from implementation errors rather than protocol flaws.

Why Implementation Is Hard:

Famous Implementation Bugs:

The history of consensus implementation is littered with subtle bugs:

• Zookeeper ZOOKEEPER-1154: Race condition in leader election could cause data loss
• etcd #8980: Crash during configuration changes could violate safety
• Raft implementations: Multiple open-source Raft libraries have had correctness bugs discovered years after release

Verification Approaches:

Given the difficulty, how do we gain confidence in implementations?

1. Formal verification: Mathematically prove the implementation matches the specification (expensive but highest assurance)
2. Model checking: Exhaustively explore the state space for small configurations
3. Jepsen testing: Black-box testing that injects failures and checks invariants
4. TLA+ specifications: Formally specify the protocol before implementing
5. Linearizability checking: Verify that the implementation's behavior is linearizable

Beyond the technical difficulties, consensus is hard because it requires thinking in ways that contradict our everyday intuitions. Our mental models, shaped by centralized and synchronous experiences, lead us astray in distributed settings.

Common Intuition Failures:

The Need for New Mental Models:

Effective reasoning about consensus requires adopting new mental models:

1. Think in asynchrony: Assume no timing guarantees. What could happen with arbitrary delays?

2. Consider all interleavings: Messages can be reordered, delayed, lost. What are all possible orderings?

3. Assume failures at any point: What if a process crashes after sending but before receiving acknowledgment?

4. Distinguish knowledge from state: Just because a value was decided doesn't mean all processes know it yet.

5. Embrace uncertainty: Accept that some things cannot be known at any given moment—design around the uncertainty.

The Byzantine Generals Analogy:

Leslie Lamport's Byzantine Generals Problem (which we'll explore next) captures this intuition challenge perfectly. Even a simple coordination task becomes surprisingly complex when participants might fail or lie. The puzzle is that the 'obvious' solutions all have subtle flaws that only become apparent upon careful analysis.