Raft leader election: timeouts, voting rules, and the four safety properties

The election timeout and heartbeats

A leader asserts its authority by sending AppendEntries heartbeats to every follower at a fixed interval — typically 50 ms. Each follower has an election timeout that resets on every valid heartbeat. If the timeout fires (no heartbeat received), the follower assumes the leader is dead and starts an election.

The timeout is randomised — typically in a range like 150–300 ms. Without randomisation, all followers would time out simultaneously, each vote for itself, and the vote would split. With a wide-enough range, one follower fires first with high probability, sends RequestVote to all others, and collects a majority before anyone else times out. Ties are still possible but become rare; any tie just starts a fresh term and a new random timeout resolves it quickly.

The RequestVote voting rule

A node grants a vote in RequestVote only if:

1. It has not already voted in this term (one vote per term per node).
2. The candidate’s log is at least as up-to-date as the voter’s own log.

“At least as up-to-date” is compared by: higher lastLogTerm wins; if terms are equal, higher lastLogIndex wins. This rule is the key to safety.

Why the log-completeness rule matters

Without the up-to-date check, a candidate with a stale log could win an election and become leader despite missing committed entries. Those entries would then be overwritten, violating the guarantee that a committed entry is durable forever.

The quorum-overlap argument shows why the rule works: every committed entry was acknowledged by a majority. Any election quorum overlaps with that commit quorum in at least one node. Through that shared node, the candidate must have the committed entry (or a voter refuses). Combined, the quorum overlap and the log-completeness rule give Leader Completeness: every leader in term T+1 has all entries committed in terms 1–T.

The four safety properties

Raft’s correctness proof reduces to four invariants:

1. Election Safety — at most one leader per term. Follows from “one vote per node per term + majority required.”
2. Leader Append-Only — a leader never overwrites or deletes its own log entries; it only appends.
3. Log Matching — if two logs share an entry at index i with term t, they are identical for all indices up to i. Follows from the AppendEntries consistency check.
4. Leader Completeness — any entry committed in some term is in the log of every leader of higher terms. Follows from quorum overlap + the voting rule.

These four invariants work as a chain: Safety prevents two leaders (1), Append-Only keeps a leader’s own log intact (2), Log Matching makes followers converge to it (3), and Completeness ensures no new leader starts with a gap (4). Without any single link, the chain breaks — which is why implementations like etcd treat each invariant as a non-negotiable protocol requirement, not a best-effort guideline.

State Machine Safety (derived): no two nodes ever apply different commands at the same index.