Distributed Consensus: Why Agreement Is Hard

Two replicas of a fact that matters, (who the leader is, which ID was allocated last, whether a lock is held) have come to disagree. A single machine settles such a question by reading its own memory. A cluster cannot. The disagreeing nodes may be separated by a network partition, one of them may have crashed and returned with stale state, and no shared memory exists to consult. Distributed consensus is the protocol-level answer: a way for a group of machines to agree on one value even though every fact the decision rests on travels over a network that delays, loses, and reorders messages.

This is the problem the rest of the pillar leans on. Leader election, strongly consistent replication, distributed locks, and every coordination service in production are consensus in different clothes, and each inherits the same constraints: the participants fail independently, no node can observe the whole system, and there is no agreed clock to settle disputes. The substrate (why those constraints are unavoidable) is the pillar article, what is a distributed system.

Distributed consensus is a protocol in which several nodes each propose a value, and all correct nodes agree on exactly one of the proposed values; a decision that must survive nodes crashing and messages being delayed, lost, duplicated, or reordered along the way.

The consensus problem

Formally, a consensus protocol must deliver three properties, and the difficulty is that any two of them look easy until the third arrives:

• Agreement. No two correct nodes decide different values. Whatever is decided (a leader, an allocation, a log entry) every correct node acts on the same fact.
• Validity. The decided value was proposed by some node. Without it, a protocol could agree on a constant and technically never be wrong; validity is what makes the decision mean something.
• Termination. All correct nodes eventually decide. A protocol that stalls forever has not solved disagreement; it has stored it.

Some formulations add integrity; no node decides twice, and a decided value is never reopened. The properties must hold while some nodes crash: they stop, and possibly restart, without warning. A harder variant of the problem assumes byzantine faults (nodes that keep answering, but wrongly) and demands the same three properties despite them. The two variants cost different amounts of hardware, and the algorithms behind both are the subject of consensus algorithms, the next article in this series.

Why agreement is hard

The tempting design is a vote: each node proposes a value, everyone counts, majority wins. The vote fails in exactly the ways distributed systems fail, and every real consensus protocol is, structurally, this naive scheme with the failures patched:

• Slow is indistinguishable from dead. A timeout says “no answer within thirty milliseconds,” and the silence has three possible pasts: the request died on the way out, the node processed it and the reply died on the way back, or the node is down and doing nothing. No protocol can tell the pasts apart; failure detection is a bet, not an observation, and failure detection is covered in its own article.
• Partitions manufacture fake majorities. Split a five-node cluster 2-3 and the smaller side can still hold a vote among the nodes it can reach. Two nodes agreeing is not a cluster decision; reachability has silently replaced configuration as the electorate. A correct protocol requires majorities of the whole configuration, not of the visible part.
• Crashes leave half-finished work behind. A proposer can die after some nodes have seen its proposal and others have not. A voter can grant a vote, crash, restart, and vote again with no memory of the first round, unless the protocol deliberately makes votes durable across restarts.
• Messages misbehave. Delayed votes arrive after the next round has begun; duplicated proposals arrive twice; reordered traffic makes a later decision appear to precede the vote that created it. The protocol must be correct about ordering while the network refuses to provide any.

Underneath all four is one absence: there is no global state to consult, because none exists. Partial failure and the missing shared clock (the two defining properties from the pillar article) reappear here as the precise reasons naive voting cannot work. The repairs are nontrivial: proposals need ordered identities, votes need to survive crashes, and any new proposal must first answer “which values could already have been decided?” before it can safely compete. Consensus protocols are the arrangements that apply those repairs and still finish quickly when nothing is wrong.

Quorum: why majorities decide

The central repair is the quorum. Instead of asking every node to agree, a decision requires a majority, more than half of the configuration, fixed in advance. A cluster of 2f+1 nodes tolerates f failures: any majority has f+1 or more members, so the cluster keeps deciding while f or fewer nodes are down. Odd sizes are conventional because the arithmetic is exact; a fourth node tolerates nothing more than a third does, and a fifth buys tolerance for a second failure.

Majorities do the real work through intersection. Any two majorities of the same configuration share at least one node: two groups of three cannot be drawn from five nodes without overlap. Since nodes remember what they have seen, a value decided by one majority leaves a witness inside every future majority, and two conflicting values cannot both assemble majorities without sharing a witness, who then refuses to let the second through. That overlap is the safety mechanism underneath Paxos, Raft, and ZAB alike: not a lock, not a leader, just membership that cannot avoid intersecting.

The majority rule is also why consensus is never free. A decision costs round trips to a majority, and that payment is what buys availability; the system stays decidable through f failures precisely because it declines to wait for the stragglers. Leaderless data stores borrow the same arithmetic for quorum reads and writes, with overlap thresholds such as R + W > N that trade freshness for availability; the difference between quorum access and consensus on one committed history is drawn in database replication and revisited below under common mistakes.

The FLP impossibility result

In 1985, Fischer, Lynch, and Paterson proved a theorem that still shapes every production consensus protocol. In an asynchronous system (unbounded message delay, no reliable way to observe another node’s state) no deterministic consensus protocol can guarantee both agreement and termination if even one node may crash. There is always some execution, some adversarial arrangement of delays, in which the protocol never decides: the FLP impossibility result.

The result is narrow, and the narrowness is the useful part. It does not say consensus never terminates; real clusters decide thousands of values per second. It says termination cannot be guaranteed for every possible run under fully asynchronous assumptions, which forces every practical algorithm to weaken something. Three weakenings cover the field:

• Assume some timing. Paxos, Raft, and ZAB all assume partial synchrony: bounds on delay that hold eventually, or once the system stabilizes. Under that assumption, timeouts can drive progress safely.
• Suspect failures. Treat “no answer within a timeout” as a crash and proceed. Suspicions can be wrong (the node was slow, not dead) but well-designed protocols survive wrong suspicions without breaking agreement.
• Randomize. Randomized consensus protocols give each round a fresh chance of breaking symmetry, so termination happens eventually with probability one, at the cost of a probabilistic rather than deterministic liveness claim.

All three share one posture: safety always, liveness with assumptions. Serious consensus algorithms preserve agreement under every execution, including fully adversarial ones, and purchase progress with assumptions about timing, suspicion, or chance. When a paper states its liveness conditions, it is disclosing the assumption it bought. When an operations team tunes election timeouts, it is tuning the same assumption. FLP is why both exist.

The replicated state machine

Consensus on one value would be a curiosity. What makes the problem load-bearing is repetition: agree on a sequence of values and the sequence becomes shared history. Nodes that start identical, execute the same deterministic state machine, and feed it the same entries in the same order end up in the same state indefinitely: the replicated state machine pattern, and the shape of nearly every coordination system built since.

The mechanics are quiet. Client commands enter the system; consensus decides each command’s position in a shared log; every node applies the log in order to its local copy of the state machine. Agreement on each entry is agreement on history, and a committed entry (one stored on a majority) can never be lost, because any majority that could replace a failed node overlaps the majority that committed it. Strongly consistent leader-follower replication, covered in database replication, is this pattern operating on table rows; etcd and ZooKeeper are this pattern operating on a small store of configuration, membership, and lock records.

What consensus is used for

The applications are more familiar than the protocol, which is the point: consensus is infrastructure, and it usually ships under a different name.

• Leader election. Deciding which node leads is a consensus decision: one answer, visible to all. Elections and the split-brain risk that shadows them have their own article, leader election; increasingly, production systems settle elections with a consensus protocol rather than an ad hoc vote.
• Distributed locks. A lease is one log entry; consensus makes the grant unambiguous and the holder’s identity consistent across the cluster. Lock semantics, expiry, and fencing tokens belong to distributed locks.
• Configuration and membership. The best-known use: a small store of strongly consistent data (service records, feature flags, cluster membership) replicated through consensus. etcd, ZooKeeper, and Consul are this pattern at production scale; Kubernetes stores its entire cluster state in etcd.
• Committing distributed transactions. A transaction coordinator is a single point of failure at the worst moment. Replacing it with a consensus cluster keeps the commit decision available through node loss; the mechanics of two-phase commit and its alternatives are covered in distributed transactions.
• Strongly consistent storage. Spanner commits each write through a Paxos group; CockroachDB replicates each of its ranges through Raft. Consensus-priced writes are the foundation strong consistency models are built on, a trade mapped in the CAP theorem and consistency models.

Common mistakes

• Counting a majority of the reachable. A partitioned group that votes among itself has decided nothing. Majorities are defined over the whole configuration, not over the nodes that happen to answer.
• Confusing quorum reads with consensus. Leaderless stores with R + W > N overlap their read and write sets, yet during churn a write can be visible to some reads and absent from others. Consensus provides one committed history; quorum access provides a freshness probability. The difference matters exactly when correctness does.
• Running even-sized clusters. Four nodes tolerate one failure, the same as three, at higher cost. The valid sizes are 2f+1: three, five, seven.
• Expecting consensus to be cheap across regions. Every decision pays a round trip to a majority. A five-node cluster spread across three regions pays an inter-region hop on every commit; place quorums with the write path in mind.
• Tuning timeouts as if pauses never happen. A long garbage-collection pause looks identical to a crash from outside. Election timeouts set near the worst-case pause length produce leadership flapping under load, the operational form of the slow-versus-dead ambiguity.

FAQ

What is distributed consensus?

A protocol in which several nodes each propose a value and all correct nodes agree on exactly one of them, with the decision surviving crashes, lost messages, and partitions. It is the mechanism beneath leader election, distributed locks, strongly consistent replication, and coordination systems such as etcd and ZooKeeper.

Why do consensus systems need a majority?

Because majorities intersect: any two majorities of a five-node cluster share at least one node, so a value decided by one majority is witnessed inside every later majority, and a conflicting value cannot also win. A majority is also the most demanding requirement that still survives failure; requiring f+1 of 2f+1 nodes keeps the cluster decidable through f crashes, where requiring all nodes would stop at the first one.

Does the FLP impossibility result mean consensus is impossible?

No. It means no deterministic protocol can guarantee termination under fully asynchronous assumptions with even one crash. Real protocols preserve agreement in every run and add assumptions for progress (partial synchrony, failure suspicion, or randomization) so consensus is impossible only in the sense that its liveness cannot be unconditional.

What is the difference between consensus and consistency?

Consistency models are guarantees about what readers can observe; consensus is a protocol for agreeing on values. Strong consistency (everyone sees one history) is usually implemented with consensus underneath, while weaker models can skip it. The trade space is mapped in the CAP theorem and consistency models.

What real systems use distributed consensus?

etcd (Raft), ZooKeeper (ZAB), Consul (Raft), CockroachDB (Raft), Spanner (Paxos groups), and Kafka’s KRaft controller (Raft) commit their most important decisions through consensus. Kubernetes depends on it transitively: cluster state is etcd data, and every change is a consensus commit.

Where this series goes

This article fixed the problem. The rest of the Consensus & Coordination series moves to the algorithms that solve it and the systems built on top of them:

• Consensus algorithms: Paxos, Raft, ZAB, and PBFT compared, and how to choose between the families.
• The Raft consensus algorithm, the modern default, in depth: leader election, log replication, and safety.
• The Paxos algorithm; the classic, its production descendant Multi-Paxos, and why it is the way it is.

Adjacent articles apply the machinery: leader election is consensus’s most common job, distributed locks build leases on top of it, and distributed transactions and the saga pattern show coordination inside transaction processing.

Related articles

• Next read: consensus algorithms: Paxos, Raft, ZAB, and byzantine fault tolerant consensus, compared for the decision an engineer actually faces.
• what is a distributed system, the pillar article this series builds on: partial failure, clocks, and the fallacies.
• fault-tolerant systems: redundancy, failover, and the failure detection consensus protocols depend on.
• the CAP theorem and consistency models; the trade space every consensus decision lives in.
• distributed transactions; two-phase commit, and how consensus removes the coordinator’s single point of failure.