beginnerintermediateadvanced

System Design · Section 44

Consensus

Level: intermediate
Read: 12 min
Concepts: 3

Consensus is the general problem of getting multiple nodes to agree on one value or one ordered log of operations despite some of them crashing or messages being lost or delayed — without it, a distributed system risks split brain, where two nodes both believe they are authoritative at once. Raft and Paxos-style algorithms solve this, conceptually, the same way: one leader proposes the next entry in a replicated log, and an entry only counts as committed once a majority of nodes acknowledge it, because any two majorities out of the same cluster are guaranteed to overlap. In practice, applications rarely run consensus themselves — they run a small etcd- or ZooKeeper-style coordination cluster and build leader election, distributed locks, and shared configuration on top of it as a client.

This section

Distributed Consensus - Raft Writes | Systems Design Interview 0 to 1 with Ex-Google SWEJordan has no life

What is true here

Consensus solves agreement on one value/ordered log across nodes that can crash or lose messages — without it, split brain (two "leaders" at once) becomes possible.
Raft/Paxos-style protocols, at a conceptual level: one elected leader proposes log entries, and an entry commits once a majority (quorum) of nodes acknowledge it.
Majority overlap — any two majorities from the same cluster share at least one node — is what keeps a committed decision from ever being silently lost or contradicted.
In practice, consensus lives inside a small dedicated cluster (etcd, ZooKeeper); applications become clients of it for leader election, distributed locks, and config stores rather than implementing consensus themselves.

What you will be able to do

Explain why a distributed system needs a formal agreement protocol instead of "just let any node decide"
Describe, at a conceptual level, how a leader and a majority quorum combine to make Raft/Paxos-style commits durable
Recognize split brain as the concrete failure consensus is designed to prevent
Identify etcd/ZooKeeper-style coordination services as where consensus actually shows up in a real architecture — leader election, distributed locks, config

Why nodes need to agree

The general distributed-systems problem consensus solves, and the split-brain failure it exists to prevent.

Why nodes need agreement under failures

coreintermediate

When the same data or decision is replicated across several nodes, those nodes must all end up agreeing on the same sequence of operations — otherwise they silently drift into different states while each one still believes it is correct. This is easy on a single machine (there is only one copy of the truth) and hard across a network, because nodes can crash, restart, or simply fail to hear a message in time, and the rest of the system cannot always tell the difference between "that node is dead" and "that node is just slow." Consensus is the general problem of getting a group of nodes to agree on one value or one ordered log of operations despite some of them crashing or messages being lost or delayed.

Think of it as

Picture three people scattered across a building, each with a walkie-talkie, trying to agree on a single meeting time by shouting messages that sometimes get lost in the static. If one person goes quiet, the other two cannot tell whether they stepped away for a minute or left the building for good — but the group still has to settle on one time everyone will show up to, without ever calling and asking the missing person directly. That is the consensus problem: agree on one answer, using only unreliable messages, without being sure who is still listening.

What we're doing: Show what goes wrong without any agreement mechanism when a leader node becomes unreachable.

no-consensus.txttext

Cluster: Node A (current leader), Node B, Node C

1. Network partition isolates Node A from B and C.
2. Node A still thinks it is the leader — it keeps
   accepting writes from clients on its side of the
   partition.
3. Nodes B and C, unable to reach A, independently
   elect Node B as the new leader.
4. Node B also starts accepting writes from clients
   on its side.
5. Two "leaders" now accept conflicting writes to the
   same keys at the same time — split brain.

Without a rule for what counts as a valid decision
(e.g. "only a majority can elect a leader"), there is
no way to tell afterward whose writes should win.

3: Node A cannot distinguish "network partition" from "everyone else crashed" — it has no way to know it lost quorum.
7: B and C proceed without A because they can still reach each other — this is the moment consensus rules (majority quorum) need to apply.
11: Two leaders accepting writes simultaneously is exactly the failure a consensus protocol is designed to make impossible.

Why this works: This is the concrete failure mode — split brain — that motivates the entire topic: without a formal agreement protocol, a distributed system has no principled way to decide which node's decisions are authoritative during a partition.

Assuming "the leader will notice it lost connectivity and step down"

Wrong

text

"If Node A gets cut off from the cluster, it will
just notice and stop accepting writes on its own."

Better

text

"Node A cannot reliably distinguish being
partitioned from everyone else being slow. It
needs an explicit rule — e.g. it can only keep
acting as leader while it holds a majority, or a
lease that expires without renewal — because
self-detection isn't possible from inside a
partition."

What you see: Two nodes both serve writes as if they were the sole leader after a network blip, and reconciling the two histories afterward requires manual intervention or silently drops data.

Why: A node on the wrong side of a partition has no direct way to observe that it is cut off — it can only infer this from silence, and silence is indistinguishable from "everyone is just slow." Only an explicit majority/quorum rule, not self-awareness, can prevent both sides from acting as leader.

No agreement rule → two leaders, same time

Node A

Node B

Node C

1. network partitionA isolated from B and C
2. still accepts writesbelieves it is still leader
3. elect B (no quorum rule)B and C proceed without A
4. also accepts writessplit brain — no way to tell whose writes win

Remember: Consensus is the general problem of getting nodes to agree on one value or ordered log despite crashes and lost/delayed messages — the danger without it is split brain, where two nodes both believe they are authoritative at once.

How Raft/Paxos-style consensus works, conceptually

Leader-based log replication and majority quorum — the two ideas that transfer, without the implementation detail.

The high-level purpose of Raft/Paxos-style consensus

coreintermediate

Raft and Paxos are algorithms that let a cluster of nodes agree on an ordered log of operations even while nodes crash or messages are lost. At a conceptual level (not the implementation detail) they share the same two ideas: one node is elected leader and is the only one allowed to propose the next entry in the log, and an entry only counts as committed once a majority (quorum) of nodes have stored it. Because a majority is required, any two majorities out of the same cluster must overlap by at least one node — so a committed decision can never be silently forgotten or contradicted by a later majority, even if some nodes are down. Raft was explicitly designed to be easier to understand and implement than Paxos while providing the same guarantees; Paxos came first and is more general but notoriously hard to reason about correctly.

Think of it as

Think of a small board of directors voting on decisions by mail, where the chair (leader) drafts each proposal and only that draft becomes official once signed ballots come back from more than half the board. If the chair goes silent (crashes), the remaining directors hold a new election among themselves for a new chair — but a new chair can only take over if they too can round up more than half the board's votes. Because "more than half" of any two votes must share at least one common director, no rogue faction smaller than that can ever push through a conflicting decision behind the group's back.

What we're doing: Show conceptually how a 5-node Raft-style cluster commits one log entry and survives a leader crash.

raft-quorum.txttext

Cluster: 5 nodes (N1 leader, N2, N3, N4, N5)

1. Client sends a write to N1 (the leader).
2. N1 appends the entry to its own log, then sends
   AppendEntries to N2..N5 in parallel.
3. N2 and N3 acknowledge before N4/N5 respond.
4. N1 now has itself + N2 + N3 = 3 out of 5 acks —
   a majority. N1 marks the entry committed and
   applies it, then tells followers on the next
   heartbeat.
5. N1 crashes immediately after.
6. N2 and N3 (both already having the entry) are
   eligible to win the next leader election, because
   a candidate must get votes from a majority too —
   and any such majority overlaps with {N1, N2, N3}.
7. Whichever of N2/N3/N4/N5 becomes leader next will
   already have (or must catch up to) the committed
   entry before the cluster proceeds — it is never
   silently lost.

8: 3 out of 5 acknowledgments is the majority quorum — the entry is committed at this point, before N4 or N5 have even responded.
11: The leader crashing right after committing is exactly the scenario consensus must survive without losing or contradicting the decision.
15: Any future majority election must overlap with the {N1, N2, N3} group that already committed the entry — this overlap is what makes the guarantee hold.

Why this works: The mechanics that matter conceptually are entirely visible here without touching Raft's internal term numbers or RPC formats: a leader proposes, a majority acknowledges, and majority overlap is what keeps a committed decision durable across a crash.

Assuming consensus requires ALL nodes to acknowledge before committing

Wrong

text

"The write isn't safe until every single node in
the cluster has stored it."

Better

text

"The write is safe (committed) once a MAJORITY
of nodes have stored it — waiting for every node
would mean one slow or dead node could block all
writes, which defeats the point of tolerating
failures."

What you see: A team assumes a 5-node cluster has zero fault tolerance for writes ("if any node is down, we can't write"), when in fact it tolerates 2 node failures and still commits writes via majority.

Why: Requiring unanimous acknowledgment would make the whole system only as available as its least reliable node — majority quorum is precisely the design choice that lets the cluster keep making progress while a minority of nodes are down.

5-node cluster: majority (3/5) commits the entry

Majority — committed

Not yet responded

Raft vs Paxos, conceptually

Raft vs Paxos, conceptually
Property	Raft	Paxos (classic)
Roles	Explicit leader, followers, candidates	Proposers, acceptors, learners (roles can overlap)
Design goal	Understandability, decomposed into clear subproblems	Generality and provable correctness first
Log model	Strong leader appends entries in order	Value-per-instance agreement, leader is an optimization (Multi-Paxos)
Common real-world use	etcd, Consul, CockroachDB	Chubby (Google), classic distributed databases

Remember: Raft/Paxos, conceptually: one leader proposes the next log entry, a majority (quorum) must acknowledge before it counts as committed, and any two majorities out of the same cluster always overlap — so a committed decision can't be silently lost or contradicted. Raft optimizes for understandability over Paxos's generality.

Where consensus shows up in real systems

etcd/ZooKeeper-style coordination clusters, and the leader election, locks, and config stores built on top of them.

Where consensus actually gets used in practice

standardintermediate

Application code almost never implements Raft or Paxos itself — instead, teams run a small, dedicated cluster of a consensus-backed coordination service (etcd, ZooKeeper, or a cloud-managed equivalent) and build features like leader election, distributed locks, and shared configuration on top of it. The consensus algorithm's job is confined to keeping that small coordination cluster's own data consistent; everything else in the larger system talks to it over a normal client API rather than running consensus itself.

Think of it as

A consensus-backed coordination service is like a courthouse in a town: instead of every business in town running its own dispute-resolution process from scratch, they all send their disputes to the one courthouse, which uses a slow, careful, well-audited process internally and hands back a single authoritative ruling. Most businesses never need to know how the courthouse's internal procedure works — they just need one place everyone trusts to give the same answer to the same question.

What we're doing: Show the same conceptual pattern — one coordination cluster, many application services as clients — for leader election, locking, and config.

consensus-in-practice.txttext

Coordination cluster (etcd/ZooKeeper): 3-5 nodes,
running Raft/ZAB internally to stay consistent.

  Use 1 — Leader election:
    App instances A, B, C each try to create/hold a
    key "current-leader". Only one succeeds; the
    others watch that key and retry if it disappears
    (the holder crashed or its lease expired).

  Use 2 — Distributed lock:
    Worker processes W1, W2 both want to process
    job #42. Both attempt to acquire lock key
    "/locks/job-42". Only one gets it; the other
    waits or picks a different job.

  Use 3 — Config store:
    100 API server instances all watch key
    "/config/rate-limit". An operator updates it
    once; every instance is notified and picks up
    the new value within one watch round-trip,
    instead of each server holding a possibly-stale
    local copy.

1: The consensus protocol runs only inside this small 3-5 node cluster — not across the (possibly hundreds of) application instances that use it.
10: The lock pattern reuses the exact same "only one client can hold this key" guarantee as leader election — it is the same primitive applied to a different problem.
16: The config-store use case turns a fan-out consistency problem (100 servers agreeing on one value) into a fan-out READ problem against one already-consistent source.

Why this works: These three uses look different from the outside but rest on the identical underlying guarantee — a small consensus-backed cluster can hand out one authoritative answer to "who holds this / what is this value right now" — which is the payoff of learning consensus conceptually rather than per use case.

Three uses of the same consensus guarantee

Leader election

only one holds "current-leader"

Distributed lock

only one holds the job key

Config store

one consistent value, many readers

Remember: Applications rarely run consensus themselves — they run a small etcd/ZooKeeper-style cluster that runs Raft/Paxos-family consensus internally, then build leader election, distributed locks, and shared config as client features on top of that one consistent source.