Catalog My learning Blog
Raft and Paxos Explained: Consensus, ZooKeeper and etcd · Phase 1 · Lesson 1 · 9 min read

What Is Consensus in Distributed Systems?

On this page
  1. Learning Objective
  2. Concept Explanation
  3. Worked Example: Why Naive Primary Failover Is Not Consensus
  4. Real-World Examples
  5. Review Questions & Answers

Learning Objective

State the formal properties a consensus algorithm has to provide - agreement, validity, integrity, and termination - explain why the interesting difficulty lives entirely in the failure cases rather than the happy path, and recognise which everyday infrastructure decisions are secretly consensus problems.

Concept Explanation

Consensus, stripped of all the algorithm names, is one deceptively small problem: a set of processes each propose a value, and they must all decide on exactly one of those proposed values, even though some of them will crash partway through and the network between them will drop, delay, duplicate, and reorder messages. That is the whole problem statement. It sounds like it should be a short afternoon of work, and the fact that it instead produced four decades of research papers, a famous impossibility proof, and a well-earned reputation as the hardest thing in distributed systems is the single most useful piece of intuition to carry into the rest of this course.

The problem is usually specified by four properties. Agreement says no two correct processes decide different values, which is the safety property everything else exists to protect. Validity, sometimes called non-triviality, says the decided value must be one that some process actually proposed, ruling out the degenerate algorithm that always decides the number seven and trivially satisfies agreement. Integrity says a process decides at most once and never un-decides, which is what makes a decision durable enough to build on. Termination says every correct process eventually decides something, which is the liveness property: an algorithm that simply never decides anything satisfies agreement, validity, and integrity perfectly while being completely useless.

The critical distinction to internalise here is between safety and liveness, because almost every practical consensus system trades them against each other deliberately. Safety properties say nothing bad happens: two replicas never disagree about what was committed. Liveness properties say something good eventually happens: the cluster eventually accepts your write. Real consensus implementations are built to never violate safety under any network behaviour whatsoever, and to sacrifice liveness instead when the network misbehaves badly enough. When an etcd cluster stops accepting writes during a partition, that is not a bug in etcd, it is etcd choosing to stop making progress rather than risk two nodes disagreeing. A system that stayed available in that situation would be one that had chosen to give up agreement, which is a different and usually much worse kind of system.

It is worth being precise about what consensus is not, because the surrounding vocabulary is used loosely. Consensus is not the same as replication: you can replicate data with no agreement at all, which is exactly what asynchronous primary-replica replication does, and the resulting divergence on failover is the reason people reach for consensus in the first place. Consensus is not the same as a distributed transaction: two-phase commit needs every participant to vote yes and blocks indefinitely if the coordinator dies mid-protocol, whereas a consensus algorithm needs only a majority and specifically survives the failure of its leader. And consensus is not the same as eventual consistency, where replicas converge on their own schedule with no single moment at which a value became official.

A surprising amount of infrastructure turns out to be a consensus problem wearing a different hat. Electing exactly one leader is consensus on the identity of the leader. Deciding whether a distributed transaction commits or aborts is consensus on a single bit. Agreeing on cluster membership after a node is removed is consensus on the membership list. Assigning a uniquely-owned lock, agreeing on the order of entries in a replicated log, deciding which of two datacentres is currently authoritative: all the same underlying problem. This is why one well-implemented consensus module, sitting inside etcd or ZooKeeper or embedded in a database, ends up supporting so many apparently unrelated features.

PropertyWhat It RequiresWhat Breaks Without It
AgreementNo two correct processes decide different valuesSplit brain: two nodes both believe they are the authoritative leader
ValidityThe decided value was proposed by some processA decision unrelated to any real input, technically consistent and practically useless
IntegrityEach process decides at most once and never reverses itCommitted writes that later disappear, so nothing downstream can trust a commit
TerminationEvery correct process eventually decidesA cluster that is perfectly consistent and permanently stuck, accepting no writes

Worked Example: Why Naive Primary Failover Is Not Consensus

The clearest way to feel what consensus buys you is to watch a system that does not have it. Consider a plain primary-replica database pair with an external health checker that promotes the replica when the primary stops answering. Every individual step looks reasonable, and the combination has no way to satisfy agreement.

Code
# A naive failover, step by step, with no consensus anywhere in the loop

t=0     primary A accepts writes; replica B streams from A asynchronously
        B has applied up to offset 1000; A has accepted up to offset 1040

t=10s   the network link between the health checker and A drops.
        A is perfectly healthy and still accepting writes from clients
        that reach it on a different path. The checker cannot tell the
        difference between "A crashed" and "I cannot reach A".

t=12s   the checker promotes B to primary. B now accepts writes from
        t=12s onward, starting from its own offset 1000.

t=12s+  TWO primaries are accepting conflicting writes.
        Offsets 1001-1040 exist only on A.
        New writes on B reuse those same offsets with different content.

t=90s   the link heals. There is now no correct answer to the question
        "what is the committed state of this database?" Someone has to
        pick a winner by hand and throw away real, acknowledged writes.

# What consensus changes:
#   B may only become leader by collecting votes from a MAJORITY of the
#   cluster. A, isolated on the minority side, cannot collect a majority,
#   so it cannot keep committing. Only one side can ever have a majority,
#   so only one side can ever commit. Agreement is preserved by
#   construction, and the price is that the minority side stops serving
#   writes - liveness traded away to protect safety.
The four consensus properties shown against a single decision round: multiple processes propose values, one value is chosen, and agreement, validity, integrity and termination each guard a different way that choice can go wrong.
The four consensus properties shown against a single decision round: multiple processes propose values, one value is chosen, and agreement, validity, integrity and termination each guard a different way that choice can go wrong.

Real-World Examples

  • Google built Chubby, its internal lock service, on Paxos precisely because so many of its systems needed the same primitive: the 2006 OSDI paper describes Chubby being used for leader election in GFS and Bigtable, as a small store for the metadata those systems needed everyone to agree on, and as a coarse-grained lock service - three features that look unrelated in a design review and are all the same consensus problem underneath.
  • Kubernetes stores the entire authoritative state of a cluster in etcd, which uses Raft, rather than in a conventional replicated database, because the API server needs a guarantee that two controllers reading the state never see contradictory answers about which pods are scheduled where. Every kubectl apply ultimately becomes an entry committed by a consensus algorithm before it is visible to any controller.
Key TakeawaysConsensus is the problem of getting a set of processes to agree on exactly one value despite crashes and an unreliable network, specified by agreement, validity, integrity, and termination. Real systems treat agreement as inviolable and sacrifice termination instead: when a consensus-backed cluster stops accepting writes during a partition, that is the algorithm working as designed, deliberately trading liveness to protect safety.

Review Questions & Answers

It violates validity, which requires the decided value to be one that some process actually proposed. It satisfies agreement trivially, since every process decides 0 and therefore no two processes disagree, and it satisfies integrity and termination as well. This is exactly why validity exists as a separate property: without it, agreement alone can be satisfied by an algorithm that ignores its inputs entirely and is therefore useless.

A liveness failure is recoverable and observable: the cluster stops accepting writes, monitoring fires, the partition heals, and the system resumes from a state everyone agrees on with nothing lost. A safety failure is silent and often unrecoverable: two nodes both accept conflicting writes, both sets of writes are acknowledged to real users, and when the partition heals there is no correct way to reconcile them without discarding acknowledged data. Downtime costs hours; divergence costs correctness permanently, and every system built downstream on the assumption that a commit means something inherits the damage.

Two-phase commit requires unanimity - every participant must vote yes for the transaction to commit - and it blocks indefinitely if the coordinator fails after participants have voted but before they learn the decision, because no participant can safely decide on its own. Consensus requires only a majority and specifically tolerates the failure of any minority including the current leader, because a new leader can be elected from the surviving majority and can reconstruct the decision from the votes that majority holds. That is the difference between a protocol that is blocking by construction and one that is fault-tolerant by construction.

Leader election is consensus on the identity of the current leader. Distributed locking is consensus on which client currently holds the lock. Cluster membership change is consensus on the contents of the membership list. Others include agreeing on the order of entries in a replicated log, which is repeated consensus on what occupies each log position, and deciding whether a distributed transaction commits, which is consensus on a single bit. This shared shape is why one well-tested consensus implementation inside etcd or ZooKeeper can back a dozen features that look unrelated on an architecture diagram.

It fails agreement. The health checker cannot distinguish a crashed primary from a primary it merely cannot reach, so it can promote a replica while the original primary is still alive and still accepting writes on another network path, producing two primaries with divergent committed state. A better health checker does not fix this, because the impossibility is informational rather than a matter of detection quality: no observer can reliably tell a crash from a partition from the outside. The fix is structural - require a majority quorum for promotion, so that the isolated old primary is arithmetically unable to keep committing.