06.04 · Concept
Consensus
Explain leader election and log replication, why R + W > N matters, and why three replicas rather than two.
Consensus keeps replicated state single-valued and ordered when machines crash, pause, or lose contact. Raft does this with majority-based leader election and log replication: a leader needs quorum support to be legitimate, and a write is durable only when quorum overlap prevents a later leader from choosing a conflicting history.
What this lesson answers
- why does Raft need a majority quorum
- why are three replicas better than two
- when is a replicated log entry committed
Notes
Consensus — Consensus exists so distributed nodes can agree on one ordered state despite crashes, delays, or partitions; without it, leaders split, writes diverge, and clients read conflicting histories.
Key Concepts: - A quorum system prevents conflicting decisions when read quorum and write quorum satisfy ; for , common choices are or . - Three replicas tolerate one crash because majority is ; with two replicas, majority is also , so losing one node makes progress impossible.
Common questions
- Why does R plus W need to be greater than N?
- The read and write quorums must overlap. If they do not, a read can contact only replicas that missed the latest committed write, so it may return stale state. When R plus W is greater than N, every successful read quorum intersects every successful write quorum, giving the system a place where the latest decision is visible.
- Why is a two-replica cluster not highly available?
- With two replicas, a majority still means both nodes. If either node is down or unreachable, the remaining node cannot prove it is safe to accept writes, because the other node might have seen a different history. Three replicas can lose one node and still form a majority, so progress remains possible.
- How does Raft stop two leaders from committing different writes?
- Raft divides time into terms, and a server grants at most one vote per term. A candidate must win votes from a majority, so two candidates cannot both win the same term. Committed log entries also require majority replication, which makes later legitimate leaders inherit or respect the already chosen entries.
Short definition: what is Consensus?