1. Why Distributed Systems Need a Leader
Some decisions in a distributed system are safe for any node to make independently. Others aren't — specifically, anything that requires a single, agreed-upon order: which write happened first, who holds a lock, which value was actually committed. If every node in a cluster could accept conflicting writes at the same time with no coordination, you'd end up with divergent histories that have to be reconciled after the fact, which is exactly the messy, conflict-resolution-heavy world AP systems (Week 9) accept in exchange for availability. A leader sidesteps that by funneling the decisions that need a strict order through one node at a time, so there's never a question of which of two simultaneous writes came "first."
This shows up constantly in systems you've already studied this course. Week 5's leader-follower replication routes all writes through a single primary specifically so replicas apply changes in the same order. Kafka assigns a single broker as the leader for each partition — every producer and consumer for that partition talks to that one broker, which is what keeps the partition's log in a strict, unambiguous order. Coordination services like ZooKeeper and etcd elect a leader to arbitrate distributed locks and configuration changes, so two clients can never both believe they hold the same lock.
No leader (every node accepts writes independently):
Node A accepts: set(x = 5)
Node B accepts: set(x = 9) -- at nearly the same instant
Which one is "the" value of x? Every node has to reconcile this
after the fact (last-write-wins, vector clocks, CRDTs, ...).
With a leader:
All writes to x are routed to whichever node is the current
leader. The leader assigns each write a position in a single
ordered log: ... set(x=5) at position 41, set(x=9) at position 42.
There is no ambiguity about which happened first -- position 42 did.
The obvious problem: a single leader is a single point of failure. If it crashes and nothing replaces it, the system stops making progress on anything that required the leader. So leader-based systems need a reliable way to detect that the leader is gone and elect a new one quickly — which is exactly what Section 2 covers.
Candidates sometimes worry that funneling writes through one node inherently caps throughput. In practice, the leader typically just decides ordering and coordinates replication — the actual storage and read work is often still spread across the cluster, and per-partition leadership (as in Kafka) means the "one leader" constraint applies per partition, not to the whole system, so overall throughput scales with the number of partitions.
2. Leader Election, Conceptually
Leader election is how a cluster detects a missing leader and agrees on a replacement, without any single node unilaterally declaring itself in charge. The mechanics are broadly the same across Raft-style protocols: every node expects periodic heartbeats from the current leader; if a follower doesn't hear one within a timeout, it assumes the leader is gone and starts an election by voting for itself and requesting votes from the rest of the cluster. Each election is tagged with a monotonically increasing term (or epoch) number, so nodes can always tell a stale, out-of-date leader claim from the current one and reject it.
A node only becomes leader once it collects votes from a majority of the cluster for that term — not just a plurality, and not a single self-vote. To reduce the odds of two followers timing out and starting elections at the exact same moment (which would split the vote and force a re-election), Raft-style protocols randomize each node's election timeout, so one node almost always times out first and wins the vote before a competing election even starts.
Cluster: [N1(leader)] [N2] [N3] [N4] [N5], term = 7
N1 crashes. N2, N3, N4, N5 stop receiving heartbeats.
N3's randomized timeout fires first:
N3 increments term to 8, votes for itself, requests votes
N2 votes for N3 (hasn't voted this term, N3's log is current)
N4 votes for N3
-- N3 now has 3 votes (itself + N2 + N4) out of 5 nodes --
3 is a majority of 5, so N3 becomes leader for term 8
N5 votes late / N1 eventually recovers and tries to act as
leader for term 7 -- every node rejects it, since term 7 is
stale and term 8 already has a recognized leader.
Requiring a strict majority — not just "the most votes" — is what prevents two nodes from both believing they're leader at the same time. During a network partition, only the side of the cluster that contains a majority of nodes can elect a leader at all; the minority side can't reach quorum, so it can't elect anyone and effectively stops accepting leader-dependent writes until the partition heals. That's a direct consequence of Week 9's CP choice: this design deliberately sacrifices availability on the minority side to guarantee there's never more than one leader making decisions.
If leadership only required "more votes than any other candidate" rather than a strict majority, a badly-timed partition could let each side of a 3-3 split independently elect a different leader — two leaders, both accepting writes, is exactly the split-brain scenario distributed systems most want to avoid. The majority requirement makes that mathematically impossible, which Section 3 explains in more general terms.
3. Consensus & Majority Quorums
Consensus is the general problem of getting multiple nodes to agree on a single value or decision, correctly, even though some nodes might crash or messages might be delayed. Leader election (Section 2) is one instance of consensus — agreeing on who the leader is — but the same majority-quorum mechanism also governs ongoing decisions like "was this write committed."
For a cluster of N nodes, a majority quorum is
floor(N / 2) + 1 nodes. The reason this specific threshold matters: any
two majorities out of the same N nodes are mathematically guaranteed to overlap by at
least one node. That overlap is what prevents two conflicting decisions from both
being "committed" — if any decision requires a majority's agreement, two different
majorities can never independently agree on two different, conflicting things, because
they'd have to disagree through at least one shared node.
N (cluster size) Quorum needed Failures tolerated (N - quorum)
3 2 1
5 3 2
7 4 3
Note: going from N=4 to N=5 still only tolerates 1 failure
(quorum for N=4 is 3, so N - quorum = 1) -- an even-sized
cluster gets none of the extra fault tolerance you'd expect
from the extra node, which is why production clusters
(etcd, ZooKeeper, Raft-based systems) are almost always sized
as an odd number.
This is why a 5-node cluster, not a 4-node or 6-node one, is such a common real-world choice: it tolerates 2 simultaneous node failures while still making progress, and adding a 6th node wouldn't improve fault tolerance at all — it would only add replication overhead. The same quorum math governs both "can we elect a leader" and "can we commit a write," which Section 4 ties together.
If an interviewer asks how many nodes your coordination cluster should have, "an odd number, like 3 or 5" is a stronger and more specific answer than "several, for redundancy" — and being able to say why (even-sized clusters waste a node without adding fault tolerance) shows you understand the quorum math underneath the recommendation rather than repeating a rule of thumb.
4. Raft & Paxos: Log Replication
Paxos was the original general solution to distributed consensus: proven correct, widely used (ZooKeeper's underlying protocol, ZAB, is Paxos-derived), but famously difficult to understand and to implement correctly — its roles (proposers propose values, acceptors vote on them, learners find out what was chosen) and its multiple variants (Basic Paxos, Multi-Paxos) leave a lot of implementation detail unspecified. Raft was designed later, explicitly to solve the same problem while being easier to reason about, by decomposing consensus into three clearly separated pieces: leader election (Section 2), log replication, and safety guarantees.
Raft's log replication is the same majority-quorum idea from Section 3, applied continuously to every write, not just to electing a leader. A client sends a write to the leader; the leader appends it to its own log as an uncommitted entry and sends it to all followers in parallel; once a majority of nodes (leader included) have persisted that entry, the leader marks it committed, applies it, and responds to the client. Followers learn an entry is committed on a subsequent heartbeat and commit it locally too.
Client sends write W to the leader (N1).
1. N1 appends W to its log at index 42 (uncommitted)
2. N1 sends "AppendEntries(42, W)" to N2, N3, N4, N5 in parallel
3. N2 and N4 persist it and ack. N1 now has 3 acks (itself + N2 + N4)
out of 5 -- that's a majority (quorum = 3 for N=5)
4. N1 marks index 42 COMMITTED, applies W, responds to the client
5. N3 and N5 may be slow or briefly unreachable -- doesn't matter,
the write is already safely committed once a majority has it
6. On the next heartbeat, N3 and N5 learn index 42 is committed
and apply it too, catching the log up to match the leader
Two things fall directly out of the majority requirement here. First, the system keeps making progress even if a minority of nodes are slow, unreachable, or crashed — exactly the fault tolerance from Section 3's quorum table. Second, and just as important for Week 9's framing: a Raft- or Paxos-based system is fundamentally CP. If the leader can't reach a majority of nodes — say, during a partition — it cannot commit new writes, and correctly-behaving followers will refuse to serve a write as committed until they know a majority has it. The system deliberately gives up availability rather than risk two different nodes disagreeing about what was committed.
In practice, Raft powers etcd and Consul directly; ZooKeeper uses ZAB, a protocol in the same Paxos-derived family; and several distributed databases (CockroachDB, TiDB) run an independent Raft group per shard or range, so that each piece of the data has its own leader and its own quorum rather than coordinating the entire cluster through one global leader.
System design interviews essentially never ask you to implement Raft or Paxos from scratch — they ask whether you know when a component needs consensus at all (a distributed lock, a leader-based database, a coordination service) and can reason about the consequence: that component will be CP, it will pay a majority-quorum round trip in latency, and it will lose availability if it can't reach a majority. Naming "I'd use etcd/Raft here for leader election, which means this becomes CP" is the level of depth expected.
5. Hands-on Exercise
Design leader election for a distributed feature-flag store
Your team runs a small configuration store (a mini etcd) that holds feature flags read by every service in the company, deployed across 3 datacenters, 5 nodes total.
Requirements:
- State the cluster size and the majority quorum for it, and how many simultaneous node failures it can tolerate while still making progress (use Section 3's math).
- Walk through, step by step, what happens from the moment the current leader crashes to a new leader being elected (reference heartbeats, timeouts, and terms from Section 2).
- Now assume the 3 datacenters split into a 3-node partition and a 2-node partition. State which side (if either) can still elect a leader and serve writes, and why.
- Explicitly classify this system as CP or AP per Week 9's framework, and justify it in 1–2 sentences using what happens to the minority side during the partition in step 3.
- Write one sentence describing an operational risk of this specific 5-node, 3-datacenter layout (hint: think about which single datacenter's loss could tip the balance).
For step 5, think about how the 5 nodes are likely distributed across only 3 datacenters — if one datacenter happens to hold 2 of the 5 nodes, losing that single datacenter takes out 2 nodes at once, which is different from losing any single node elsewhere in the cluster.
6. Knowledge Check
Four quick questions. Expand each to check your answer.
Q1
Why do distributed systems route certain operations through a single leader instead of letting any node accept them?
Why do distributed systems route certain operations through a single leader instead of letting any node accept them?
Some operations require a strict, unambiguous order — which write happened first, who holds a lock. If multiple nodes could accept these independently and concurrently, the system would end up with conflicting histories that need reconciliation after the fact. Funneling those operations through a single leader at a time removes the ambiguity: the leader assigns each one an order, so there's never a question of which happened first.
Q2
Why does leader election require a strict majority of votes rather than just the most votes among candidates?
Why does leader election require a strict majority of votes rather than just the most votes among candidates?
Any two majorities drawn from the same cluster are guaranteed to overlap by at least one node, which makes it mathematically impossible for two different nodes to each win a majority in the same term. A weaker rule like "most votes" doesn't have that guarantee — a network partition could let each side independently elect a different node as leader, producing exactly the split-brain scenario (two nodes both believing they're in charge) that leader election exists to prevent.
Q3
What was Raft's main design goal relative to Paxos, and what mechanism does it use to replicate a write safely?
What was Raft's main design goal relative to Paxos, and what mechanism does it use to replicate a write safely?
Raft was designed to be easier to understand and implement correctly than Paxos, by explicitly decomposing consensus into separate leader election, log replication, and safety mechanisms rather than leaving those details underspecified. For log replication specifically, the leader appends a write to its log and replicates it to followers, and only marks it committed once a majority of nodes (the same quorum math from Section 3) have persisted it — followers pick up the committed state on a later heartbeat.
Q4
Why is a Raft-based or Paxos-based system fundamentally CP rather than AP, in Week 9's terms?
Why is a Raft-based or Paxos-based system fundamentally CP rather than AP, in Week 9's terms?
Committing a write requires acknowledgment from a majority of nodes. If the leader can't reach a majority — for instance because a partition has separated it from enough followers — it cannot safely commit new writes, and the system will reject or block requests rather than risk two sides of the cluster disagreeing about what was committed. That's a direct trade of availability for consistency during a partition, which is exactly the CP choice Week 9 describes.