Consensus and Leader Election

Define the problem

Several machines hold copies of the same data. A change arrives, and the copies must not end up with different truths.

A majority is more than half of a group. A decision is safe when a majority has accepted it.

Two majorities of one group always overlap. They share at least one machine, and that machine carries the earlier decision into the next one.

How a leader election works

Leader election chooses one machine as leader for a stretch of time. The other machines act as followers.

Each follower waits to hear from the leader. A regular heartbeat message proves the leader is still alive.

Silence starts an election. A follower that hears nothing for a set time becomes a candidate and asks the others for votes.

A candidate that wins a majority of votes becomes the new leader. It then sends heartbeats, and the group settles again.

Random waiting times stop repeated tied elections. Each candidate waits a different random time before standing again.

How consensus reaches a decision

The leader receives a proposed change. It spreads the change to the followers before the change counts as decided.

The followers write the change into their write-ahead log and answer. Writing first keeps the change safe if a machine restarts.

A majority of 3 servers is 2 servers. That group tolerates 1 failure.

A majority of 5 servers is 3 servers. That group tolerates 2 failures.

A majority of 7 servers is 4 servers. That group tolerates 3 failures.

Once a majority holds the change, the leader reports it as decided. A later leader overlaps that majority, so the decision survives.

How consensus fails

A group with no majority makes no decisions. It stays safe, but it stops accepting changes.

A slow leader triggers elections it does not deserve. The group wastes time changing leaders instead of deciding.

Elections themselves can tie. Two candidates can split the votes so that neither reaches a majority.

A network failure can strand a leader with a minority of the group. That leader must stop deciding, because its group cannot reach a majority.

Trade-offs

Bigger groups tolerate more failures. They also decide more slowly, because more machines must answer.

Odd group sizes are the common shape. Even sizes add a machine without adding protection.

Consensus protects agreement, not speed.

Consensus trades speed for one shared decision that failures cannot split.

Group size, majority, and failures tolerated