Consensus: how a group of nodes agree (Raft)

Everything in the distributed track eventually rests on one primitive: a group of machines agreeing on something. Which node is the leader? What's the current cluster configuration? Whose turn is it to hold the lock? What is the definitive order of these writes? Each is an instance of consensus — getting multiple nodes to agree on a single value (or an ordered sequence of values) and stay agreed, even as individual nodes crash and the network drops, delays, and reorders their messages. It is the hardest core problem in the field, and understanding it — even at the level of intuition — is what makes the rest of distributed systems stop feeling like magic.

Why agreement is genuinely hard

It sounds like it should be easy ("just take a vote"), and it is brutally hard for reasons that stack:

• No shared clock. Nodes can't agree on what time it is (clocks drift, as the conflict lesson showed), so they can't order events by timestamp or agree on "who was first."
• Messages are unreliable. They're lost, delayed arbitrarily, and reordered. A node that goes silent might have crashed — or might just be slow, or partitioned. You cannot distinguish a dead node from a slow one, and that ambiguity is the crux of the whole problem.
• Nodes crash and recover. Any participant can vanish mid-decision and come back later with stale state.

Consensus must be safe (never decide two different values — no contradictions, ever) and live (eventually decide something). And there's a famous result — the FLP impossibility — proving that in a fully asynchronous system where even one node can fail, no algorithm can guarantee both safety and liveness. Real systems escape this not by breaking the theorem but by adding timeouts (assuming partial synchrony: messages usually arrive within some bound): they keep safety absolute and accept that liveness can stall briefly during instability. That's the deal every practical consensus algorithm makes.

Raft: consensus you can actually understand

The foundational algorithm was Paxos, which is correct and famously baffling. Raft was designed explicitly to be understandable while giving the same guarantees, and it's what most modern systems use (etcd, Consul). It works by first electing a leader, then having the leader impose order — turning "everyone agree on a log" into "everyone follow one leader's log."

Roles. Every node is a follower, a candidate, or the leader. Normally there's one leader and the rest are followers.

Leader election. The leader sends periodic heartbeats. If a follower hears none within a randomized election timeout, it assumes the leader is dead, becomes a candidate, increments the term (a logical clock — an ever-increasing integer, with at most one leader per term), votes for itself, and asks everyone else for their vote. A node grants its vote to at most one candidate per term. A candidate that collects votes from a majority of nodes becomes the new leader. The randomized timeouts are the clever bit — they make it unlikely two nodes become candidates simultaneously, so split votes are rare and self-correcting (on a tie, everyone times out again after different random delays and one wins).

Log replication. Clients send commands to the leader. The leader appends each to its log, then replicates it to followers. Once a majority of nodes have stored an entry, the leader marks it committed and applies it to its state machine, telling followers to do the same. Because every node applies the same commands in the same order, they're replicated state machines — they all end up in identical states. That's the payoff: an agreed-upon, ordered, durable log.

Run the cluster yourself. Kill the leader and watch a follower time out, become a candidate, and win a majority to take over at a new term. Then partition the network 3 | 2 and try a client write from each side — only the majority side can elect a leader or commit, and the minority goes read-only rather than splitting the brain.

The majority rule, and why it defeats split-brain

The single most important idea is the majority quorum (N/2 + 1). Both electing a leader and committing an entry require a majority, and that one rule produces the whole safety guarantee, because of a simple fact: any two majorities of the same set must overlap in at least one node. So:

• No two leaders in the same term. Winning an election needs a majority; two candidates can't both get a majority of the same nodes, so at most one wins.
• A new leader always has all committed entries. A committed entry is on a majority; a winning leader got votes from a majority; those two majorities overlap, so the new leader's log includes every committed entry. Nothing committed is ever lost.
• A partition can't cause split-brain. If the network splits the cluster, only the side with a majority can elect a leader or commit anything. The minority side goes read-only — it literally cannot make progress, so it cannot diverge. This is the CP choice from CAP enforced mechanically: the minority sacrifices availability so the system never sacrifices consistency.

This is why consensus clusters run odd numbers (3, 5, 7). With 2f + 1 nodes you tolerate f failures and still have a majority. Five nodes survive two failures; three survive one.