Consensus is the problem of getting several machines to agree on one value, or one ordered sequence of values, even though some of them crash and messages are delayed or lost. Raft and Paxos are the two algorithms every interviewer means when they say "consensus". They matter because they are the machinery underneath "the primary failed, who is primary now?", replicated metadata stores (etcd, ZooKeeper-style coordination services), and the per-shard replication of several distributed SQL databases. For a Backend or AI engineer the practical payoff is being able to say precisely what a majority-replicated log guarantees, what it costs in latency and availability, and why "just add a second primary" gives you split brain instead of resilience. This page is the mechanism behind the linearizable "C" discussed on the CAP page and the failover described on the replication page.
Naive failover (no consensus): With consensus:
A (primary) ----X---- network partition ---- A is alone (1 of 3) -> cannot get a majority
B, C cannot reach A. Their monitor says B + C are 2 of 3 -> can elect a leader
"A is dead, promote B". A may still think it leads, but it can
A is NOT dead: it still accepts writes. never commit anything: it cannot reach
Now TWO primaries accept writes = split brain. a majority. When it heals it steps down.
Each side accepts different writes -> histories diverge -> someone's committed data is lost on merge.Failure detection is unreliable in an asynchronous network: "I cannot hear A" does not mean "A is down". If promotion is decided by a timeout alone, you will sometimes promote a healthy old primary's replacement and have two writers. Consensus solves this by making every decision require a majority (a quorum) of a fixed set of nodes. Any two majorities of the same set overlap in at least one node, so two conflicting decisions can never both collect a majority. That overlap is the whole trick; everything else in Raft and Paxos is bookkeeping to make it survive crashes, restarts and reordered messages.
Roles: FOLLOWER --(no heartbeat before randomized timeout)--> CANDIDATE
CANDIDATE --(votes from a majority)--> LEADER
any role --(sees a higher term)--> FOLLOWER
time -> term 1 | term 2 | term 3
[ leader = n0 ......... ]|[ election ][ leader = n2 ]|[ election ... ]
n0 crashes ---^ n2 timed out first,
term++ (=2), votes for itself,
sends RequestVote(term=2, lastLogIndex, lastLogTerm)
A node grants its vote iff:
1. request.term >= my term, and I have not already voted in that term (at most one vote per term)
2. candidate's log is at least as up to date as mine
(compare last entry's term first, then log length) (election restriction)A term is a logical clock: a number that only goes up, and each term has at most one leader because a node votes once per term and a leader needs a majority. Any message carrying a higher term makes the receiver adopt that term and step down, which is how a deposed leader learns it has been replaced. Election timeouts are randomized so that, usually, one follower times out first and wins before others start competing; if votes split, nobody wins that term and the timeouts fire again with new random values, so liveness relies on timing while safety does not. The log-up-to-date rule is what guarantees the new leader already holds every committed entry: a committed entry sits on a majority, a winning candidate needed votes from a majority, so at least one voter has that entry, and voters refuse candidates whose logs are behind theirs.
Leader (term 2) receives client command "x=3":
1. append (term=2, "x=3") to its own log at index 3 (durable on leader's disk)
2. send AppendEntries(prevLogIndex=2, prevLogTerm=1, entries=[x=3], leaderCommit=2) to followers
3. follower checks the entry at prevLogIndex has prevLogTerm; if not it rejects and the
leader backs up and retries earlier entries (this repairs divergent follower logs)
4. once the entry is stored on a MAJORITY (leader counts itself), leader advances commitIndex to 3
5. leader applies "x=3" to its state machine and replies to the client
6. commitIndex piggybacks on the next AppendEntries/heartbeat; followers apply up to it
5 nodes: n2(L) n3 n4 n0 n1
index 3: x x x . . -> 3 of 5 hold it -> committed, even with n0,n1 downCommitted means "stored on a majority and therefore guaranteed to survive in every future leader". The leader does not wait for all followers, so one slow or dead replica does not stall writes: the commit latency is the time of the fastest majority, which is the core performance/availability trade-off. There is a subtle rule worth mentioning if you want to sound informed: a Raft leader only advances the commit point by counting replicas of an entry from its own current term; older-term entries become committed indirectly when a newer entry after them commits. This prevents a scenario, described in the Raft paper, where an old entry that reached a majority could still be overwritten after a chain of leader changes. A write acknowledged to the client only after commit is what makes the replicated log usable as a linearizable store.
Cluster size N majority failures tolerated (f) note
1 1 0
2 2 0 worse than 1 node for availability
3 2 1
4 3 1 no better than 3, extra node = extra cost
5 3 2
7 4 3 diminishing returns; each commit waits on more nodes
Tolerating f crash failures needs N = 2f+1 nodes (majority = f+1 must be alive).
Partition of a 5-node cluster: [n0 n1 n2] | [n3 n4]
left side has 3 = majority -> keeps electing/committing. right side has 2 -> can only stall.With 2f+1 nodes, after f failures there are still f+1, a majority, so the cluster keeps going and any two majorities intersect. Even sizes waste hardware: four nodes need three for a majority, so they still tolerate only one failure, the same as three. This is why coordination clusters are almost always 3 or 5 nodes and are not stretched wider: a larger cluster tolerates more failures but every commit needs more acknowledgements, and consensus is not a way to scale throughput, since all writes still flow through one leader. This counts crash failures (nodes that stop); tolerating nodes that lie (Byzantine faults) needs more, generally 3f+1, and is not what Raft or Paxos address.
Paxos (basic, single-decree) Raft
decides one value per instance a replicated LOG with a strong leader
(Multi-Paxos chains instances)
roles proposer / acceptor / learner leader / follower / candidate
ordering ballot (proposal) numbers terms + log indexes
leader optional optimization in Multi-Paxos mandatory, built into the algorithm
membership left to the implementer specified (joint consensus / single-server change)
reputation correct but hard to turn into a system designed for understandability
safety core majority quorums intersect majority quorums intersect (same idea)Both are safe under the same assumptions (crash-recover nodes, an asynchronous network that may drop, delay or reorder messages, no Byzantine behaviour) and both may fail to make progress, though not to be wrong, when there is no stable leader. The FLP result says no deterministic algorithm can guarantee termination in a fully asynchronous system with even one crash; practical systems get liveness from timeouts and leader election. Raft is the one you can explain on a whiteboard and implement from the paper, which is why etcd, Consul and many distributed SQL stores build on it; Multi-Paxos variants sit under systems such as Google Spanner (per its published papers), while ZooKeeper uses a related protocol called ZAB. Split brain is prevented because a stale leader cannot commit without a majority; the residual risk is a stale leader serving reads from its own state, so real systems use leader leases or a read-index step (confirm leadership with a majority, or read after a committed marker) for linearizable reads.
# Real output of the script in "Try It Yourself" below (python3, deterministic, no randomness):
1) Elect node 0 in a healthy 5-node cluster
node 0 runs for term 1: votes=5, need=3, won=True
2) Replicate two commands
'x=1' acks=5/5 need=3 -> COMMITTED
'x=2' acks=5/5 need=3 -> COMMITTED
n0 up=True term=1 log=['x=1', 'x=2'] commit=2
n1 up=True term=1 log=['x=1', 'x=2'] commit=2
n2 up=True term=1 log=['x=1', 'x=2'] commit=2
n3 up=True term=1 log=['x=1', 'x=2'] commit=2
n4 up=True term=1 log=['x=1', 'x=2'] commit=2
3) Leader 0 and node 1 crash (3 of 5 remain); node 2 stands for election
node 2 runs for term 2: votes=3, need=3, won=True
4) New leader commits with 3/5 (majority)
'x=3' acks=3/5 need=3 -> COMMITTED
n0 up=False term=1 log=['x=1', 'x=2'] commit=2
n1 up=False term=1 log=['x=1', 'x=2'] commit=2
n2 up=True term=2 log=['x=1', 'x=2', 'x=3'] commit=3
n3 up=True term=2 log=['x=1', 'x=2', 'x=3'] commit=3
n4 up=True term=2 log=['x=1', 'x=2', 'x=3'] commit=3
5) Node 3 also crashes (2 of 5 remain); leader 2 tries to commit
'x=4' acks=2/5 need=3 -> NOT committed (stays uncommitted)
6) Stale node 0 (old term, missing x=3,x=4) recovers and tries to win an election
node 0 runs for term 2: votes=2, need=3, won=False
7) Up-to-date node 2 wins instead
node 2 runs for term 3: votes=5, need=3, won=True
n0 up=True term=3 log=['x=1', 'x=2'] commit=2
n1 up=True term=3 log=['x=1', 'x=2'] commit=2
n2 up=True term=3 log=['x=1', 'x=2', 'x=3', 'x=4'] commit=3
n3 up=True term=3 log=['x=1', 'x=2', 'x=3'] commit=3
n4 up=True term=3 log=['x=1', 'x=2', 'x=3', 'x=4'] commit=3Read the trace as the invariants in action. Steps 1-2 replicate with all five nodes alive. After two crashes (step 3) node 2 still gets 3 of 5 votes and can commit x=3. After a third crash (step 5) only 2 of 5 remain, so x=4 gets two acks and is not committed; it sits in the leader's log, unacknowledged to any client. In step 6 a stale node, whose log is missing x=3, asks for votes: the up-to-date nodes refuse it because of the log-up-to-date rule, so it cannot win. The toy deliberately omits timers, RPC failures and follower log repair, so it shows the rules and not a full implementation. Do not read the final state as full Raft: nodes 0 and 1 are left behind and a real leader would bring them up to date through AppendEntries.
# Save as raft_toy.py and run: python3 raft_toy.py
# Toy Raft-style simulation: leader election by term + majority-commit of log entries.
# Not real Raft (no timers, no RPC failures, no log-matching repair); it shows the core rules.
class Node:
def __init__(self, nid):
self.id = nid
self.term = 0
self.voted_for = None
self.log = [] # list of (term, command)
self.commit = 0 # number of committed entries
self.up = True
def last_info(self):
return (self.log[-1][0] if self.log else 0, len(self.log))
def elect(nodes, candidate):
c = nodes[candidate]
c.term += 1
c.voted_for = c.id
votes = 1
for n in nodes:
if n.id == c.id or not n.up:
continue
if c.term > n.term:
n.term, n.voted_for = c.term, None # newer term: step down / reset vote
# grant only if not yet voted this term AND candidate log is at least as up to date
if n.term == c.term and n.voted_for in (None, c.id) and c.last_info() >= n.last_info():
n.voted_for = c.id
votes += 1
up = sum(n.up for n in nodes)
need = len(nodes) // 2 + 1
won = votes >= need
print(f" node {c.id} runs for term {c.term}: votes={votes}, need={need}, won={won}")
return won
def replicate(nodes, leader, cmd):
L = nodes[leader]
L.log.append((L.term, cmd))
acks = 1
for n in nodes:
if n.id != L.id and n.up:
n.log = list(L.log) # simplification: follower log copied wholesale
n.term = L.term
acks += 1
need = len(nodes) // 2 + 1
if acks >= need:
for n in nodes:
if n.up:
n.commit = len(L.log)
print(f" '{cmd}' acks={acks}/{len(nodes)} need={need} -> COMMITTED")
else:
print(f" '{cmd}' acks={acks}/{len(nodes)} need={need} -> NOT committed (stays uncommitted)")
def show(nodes):
for n in nodes:
print(f" n{n.id} up={n.up!s:5} term={n.term} log={[c for _,c in n.log]} commit={n.commit}")
nodes = [Node(i) for i in range(5)]
print("1) Elect node 0 in a healthy 5-node cluster")
elect(nodes, 0)
print("2) Replicate two commands")
replicate(nodes, 0, "x=1"); replicate(nodes, 0, "x=2")
show(nodes)
print("3) Leader 0 and node 1 crash (3 of 5 remain); node 2 stands for election")
nodes[0].up = nodes[1].up = False
elect(nodes, 2)
print("4) New leader commits with 3/5 (majority)")
replicate(nodes, 2, "x=3")
show(nodes)
print("5) Node 3 also crashes (2 of 5 remain); leader 2 tries to commit")
nodes[3].up = False
replicate(nodes, 2, "x=4")
print("6) Stale node 0 (old term, missing x=3,x=4) recovers and tries to win an election")
nodes[0].up = nodes[1].up = True
nodes[3].up = True
nodes[0].term = 1
elect(nodes, 0)
print("7) Up-to-date node 2 wins instead")
elect(nodes, 2)
show(nodes)
# Exercises:
# 1. Change the cluster to 4 nodes and confirm it still tolerates only one crash (majority = 3).
# 2. Remove the "c.last_info() >= n.last_info()" check in elect() and see a stale node win in step 6.
# That check is the election restriction; without it committed entries can be lost.
# 3. Add a step where two nodes both call elect() for the same term and see that
# one-vote-per-term prevents two winners.
# To see the real thing: the raft.github.io visualization, or run a 3-node etcd cluster
# locally and kill the leader (not runnable here, so no output is claimed).Q: Why do distributed systems need a consensus algorithm at all? Why not just use a failure detector to pick a new primary?
A: Because in an asynchronous network you cannot tell a crashed node from a slow or partitioned one, so a timeout-based promotion sometimes creates two primaries that both accept writes (split brain) and their histories diverge. Consensus replaces "I think it is dead" with "a majority agreed on this decision", and since two majorities always overlap, two conflicting leaders cannot both commit. The cost is that a minority side stops accepting writes, so you are choosing consistency over availability during a partition.
Q: How does leader election work in Raft, and what is a term?
A: A follower that stops hearing heartbeats waits a randomized timeout, becomes a candidate, increments the term and requests votes; each node votes at most once per term and only for a candidate whose log is at least as up to date as its own. A term is a logical epoch number: a node that sees a higher term steps down and adopts it, which is how stale leaders are discovered. The randomization makes split votes rare and recoverable, but during an election there is no leader and writes are unavailable for at least an election timeout, typically in the range of hundreds of milliseconds in common configurations.
Q: Walk me through how a write is replicated and when it is committed.
A: The leader appends the entry to its log, sends AppendEntries to followers with the previous index and term for consistency checking, and marks the entry committed once a majority (including itself) has stored it. It then applies the entry and replies to the client; followers apply it after learning the new commit index. The trade-off is that latency equals the fastest majority round trip plus a durable write (fsync) on each of those nodes, so cross-region clusters pay a WAN round trip on every commit.
Q: Why majorities, and how many failures does a cluster of N nodes tolerate?
A: Any two majorities of the same set share at least one node, so a decision made by one majority is visible to any later majority, and that shared node prevents conflicting decisions. A cluster of 2f+1 nodes tolerates f crashed nodes. That is why 3 nodes tolerate 1 failure, 5 tolerate 2, and 4 tolerate only 1: the fourth node adds cost and commit latency without adding tolerance.
Q: How do Raft and Paxos differ, and which would you pick?
A: Both rely on majority quorums and give the same safety under crash faults. Paxos, in its basic form, agrees on a single value and needs Multi-Paxos plus a lot of implementer-supplied detail (leader election, log gaps, membership change) to become a replicated log; Raft specifies a strong leader, log matching and membership change in one coherent design that is easier to reason about and test. In practice you almost never write either: you pick a proven library or use an existing system like etcd, and you choose Raft-family systems mainly because they are easier to operate and audit.
Q: What is split brain, and how does a consensus system avoid it?
A: Split brain is two nodes both acting as leader and accepting conflicting writes, usually after a partition or a false failure detection. Raft avoids committing on both sides because committing needs a majority of the fixed membership and only one side can have one; the old leader's writes never commit and it steps down on seeing a higher term. The remaining hazard is a stale leader serving reads from local state, which real systems close with leader leases or a read-index round with a majority.
Follow-up: A five-node cluster is split 3 and 2. Client A talks to the 2-node side. What does it observe?
A: The 2-node side cannot elect a leader or, if the old leader is there, commit anything, so writes time out or fail; depending on the system, reads there either fail or are stale unless they are explicitly allowed to be. The 3-node side elects (or keeps) a leader and continues normally. That is the CP behaviour in CAP terms: the minority gives up availability to keep the log consistent.
Follow-up: Can Raft lose a write that was acknowledged to the client?
A: Not if the entry was committed and the nodes fsync before acknowledging, because a committed entry is on a majority and every future leader must have it. Loss can still happen when you turn durability off (acknowledging before fsync, or running with volatile storage) and then a majority restarts, or when the client got a timeout, since a timed-out write may or may not have committed, which needs idempotency keys or client-side deduplication.
Follow-up: Would you use consensus for every write in your application database?
A: Usually no. A single-leader database with replication is enough for many workloads, and full consensus per write adds a majority round trip and limits throughput per group. Use consensus for the small, critical control-plane state (leader election, config, locks, metadata) or inside a database that shards data into many independent consensus groups so each group stays small.
In a design interview, consensus appears whenever you need exactly one owner of something: exactly one primary for a database, one holder of a distributed lock, one scheduler leader, one coordinator for a transaction. The common pattern is to keep the big data path on cheap, scalable machinery and put only the small, critical decision state in a 3- or 5-node Raft/Paxos-backed store (etcd, ZooKeeper-style services, or the per-range groups inside a distributed SQL database). That gives you leader election and fencing (a monotonically increasing term or lease token that downstream systems check so a paused old leader cannot cause damage) without inventing your own protocol. Place the nodes in three failure domains (three availability zones) so a single zone outage still leaves a majority; two zones cannot do that because losing the bigger one loses the majority. Be honest about limits: cross-region consensus adds a WAN round trip to every commit, and a consensus group's throughput is bounded by its leader, so scale by sharding into many groups, not by adding nodes.
You are buying linearizable, fault-tolerant agreement and paying with write latency (a majority round trip plus fsync on every commit), availability of the minority side during partitions, a leader bottleneck, and operational complexity (odd cluster sizes, careful membership changes, disk latency sensitivity, clock and timeout tuning). It is the wrong tool when the data does not need linearizable writes (use asynchronous replication or a leaderless design and accept eventual consistency), when you only have one or two failure domains and cannot form a meaningful majority, or when you want to scale writes throughput by widening the cluster, since adding nodes makes commits slower and not faster. It also does not protect against bugs, corrupted disks written consistently on every node, or a bad DELETE, which replicates to every member just like any other committed command, so consensus does not replace backups.