Consensus algorithms let multiple processes in a distributed system agree on a value. They aim to provide three properties:

  • Agreement, meaning all correct processes decide on the same value.
  • Validity, meaning that value was proposed by one of the processes.
  • Termination, meaning all correct processes eventually reach a decision.

A correct process is one that follows the algorithm and does not fail; termination depends on the algorithm’s assumptions about failures and communication.

Why Ordering Matters

Applying the same operations in a different order can produce a different result.

Add first or multiply first?

Replica A

SHARED ORDER
01X = 2
02X += 2
03X *= 2

FINAL STATEX = 8

Replica B

REORDERED
01X = 2
02X *= 2
03X += 2

FINAL STATEX = 6

The replicas end up with different values.

Total Order Broadcast

Total order broadcast, also called atomic broadcast, ensures every participating correct process delivers the same messages in the same order. Replicas can deliver messages at different times, but their delivered sequences agree wherever they overlap. Reliable delivery matters as well as ordering.

Comparing two log orders

Not totally ordered

Log 1

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6

Log 2

  1. 2
  2. 1
  3. 4
  4. 3
  5. 6
  6. 5

Same six messages, a different order.

Totally ordered

Log 1

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6

Log 2

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6

Both logs match at all six positions.

Both replicas have delivered all six messages here. A replica may lag, but the messages it has delivered follow the same order.

Atomic broadcast and consensus are equivalent under matching assumptions about the system and failures. To reach consensus, processes can broadcast proposals and decide on the first delivered value. In the other direction, repeated consensus decisions can choose successive batches of messages for ordered delivery.

Raft: Understandable Consensus

Raft is a consensus algorithm designed to be easy to understand. Its elected leader orders new log entries and coordinates copying them across servers, so the servers apply committed operations in the same order. The Raft paper, In Search of an Understandable Consensus Algorithm, explains how this works.

Each server runs a state machine: it applies commands from the log to its local state. Servers that start with the same state reach the same result when they apply the same deterministic commands in the same order. A deterministic command always produces the same result from the same input.

Raft assumes servers follow the protocol, even though they can crash and restart. Logs, term numbers, and votes must survive a restart. Delays can stop progress, but must never undo a committed decision. Making progress requires a communicating majority and enough time to elect and keep a leader.

Roles and Terms

Each server has one of three roles:

  • Follower: responds to the leader and votes in elections.
  • Candidate: asks for votes to become leader.
  • Leader: orders new log entries and sends them to followers.

A term is a numbered period that starts with an election and continues through the elected leader’s tenure. It has at most one leader; an election can also finish without choosing one. Servers learn about newer terms through messages, so they can temporarily disagree about the current term.

Role changes

Raft role transitions for one serverFive servers need three votes to elect a leader. Followers become candidates on election timeout. Candidates become leaders with three votes, retry in a new term on timeout, or follow an elected leader. Candidates and leaders become followers on discovering a higher term. Current role: Follower. Term: 4. No heartbeat arrives. The election timer fills.FollowerTerm 4Election timeout0%CandidateTerm —Cluster: 5Majority: 3Votes: 0 / 3·Self·B·C·D·ELeaderTerm —Sends heartbeatsElectiontimeoutMajorityvoteHighertermRetry

Role: Follower · Term: 4

No heartbeat arrives. The election timer fills.

Five-server cluster; three votes to win. Illustrative timing.

Leader Election

Followers expect regular heartbeats from the leader. When a follower waits too long without receiving one, it becomes a candidate and asks the other servers for votes. In this three-server example, it needs two votes to become leader.

Each server can vote for only one candidate per term. Followers wait for different, randomly chosen amounts of time before starting an election, reducing the chance that several candidates start together. If the vote splits, they try again in a new term.

Leader election

Term 4Election timers
Three servers choosing a leaderNo leader is sending heartbeats. The followers have different election timeouts. Election term: 4. A is a Follower in term 4 and has not voted. It has no known leader. Election timer: 0%. B is a Follower in term 4 and has not voted. It has no known leader. Election timer: 0%. C is a Follower in term 4 and has not voted. It has no known leader. Election timer: 0%. AFollowerTerm 4Vote → —TimeoutBFollowerTerm 4Vote → —TimeoutCFollowerTerm 4Vote → —TimeoutVotes received0 / 32 needed to win
1 / 4

Waiting for a heartbeat

No leader is sending heartbeats. The followers have different election timeouts.

Three servers with equal logs; two votes to win. Illustrative timing.

The next figure uses five servers. Any two majorities share at least one server. Since that server cannot vote for two candidates in the same term, two candidates cannot both win.

Majority overlap

Round 1 / 103 of 5 servers

Previous: A C D

Current: A B C

Previous majority: A, C, D. Current majority: A, B, C. Shared servers: A, C. Dashed bounds and dashed node rings mark the previous majority. Solid bounds mark the current majority. Green rings mark shared servers.ABCDE

Shared servers: A, C

Green rings identify servers in both groups.

Two groups of three in a five-server cluster.

Log Replication

The leader gives each new command a position in its log, then sends copies to the followers. Each entry records the command and the term in which the leader accepted it. Followers store the entries in the same order and confirm when they have been saved durably.

An entry passes through several steps:

  • Once a majority has stored an entry from the leader’s current term, the leader can commit it.
  • The leader tells followers how far the log is committed, through replication messages and heartbeats.
  • Each server applies the commands it knows are committed, in log order.

The commit index is the highest entry a server knows is committed. Last applied is the highest entry it has executed. A server can know an entry is committed before it has applied it.

This example uses three servers, so two stored copies form a majority. Each server’s Stored and Commit labels show its own progress. A message’s Commit field carries the leader’s known commit index.

Log replication

Entry #1 · A confirmed 0 · C confirmed 0

One leader copies its log to two followersB leads in term 5. All logs, commit indices, and follower confirmations start at zero. C's replication is delayed; retry traffic is omitted. B is a Leader in term 5, has stored through entry 0, and knows entries through 0 are committed. A is a Follower in term 5, has stored through entry 0, and knows entries through 0 are committed. C is a Follower in term 5, has stored through entry 0, and knows entries through 0 are committed.B has confirmation from A through 0 and from C through 0.ClientBLeaderTerm 5Commit 0Stored 0#1——#2——#3——AFollowerTerm 5Commit 0Stored 0#1——#2——#3——CFollowerTerm 5Commit 0Stored 0#1——#2——#3——
1 / 18

Empty logs

B leads in term 5. All logs, commit indices, and follower confirmations start at zero. C's replication is delayed; retry traffic is omitted.

Each server’s Commit label shows its local commitment knowledge; a packet’s Commit is the leader’s advertised index. Green entries are known committed by that server; orange entries are stored but not yet known committed there. Illustrative timing.

A lagging follower can receive several missing entries together and catch up.

Leader Failure and Recovery

A missed heartbeat does not prove that the leader crashed: a slow network can look the same. If the leader is lost, new writes wait until a suitable candidate wins a majority. An isolated follower timing out does not by itself stop a healthy majority from accepting writes.

A server rejects vote requests from older terms. For a request in its current or a newer term, it also checks:

  • The server has not voted for another candidate in that term.
  • The candidate’s log is at least as up to date as the server’s own log.

Raft compares the last entry’s term first. If the terms match, it compares the entry’s index. Starting a newer election does not make an outdated log eligible.

The next example starts at a later point in the same log. B leads in term 5. B and A know entry #4 is committed, while C still ends at #3.

Leader recovery

2 of 3 servers required

Three servers preserving a committed log across leader failureA later snapshot: B leads term 5. B and A know #4 is committed; C still ends at #3. B: Leader, current term 5, stored through 4, known commit index 4, vote B. Heartbeat interval: 0 of 1 illustrative seconds. A: Follower, current term 5, stored through 4, known commit index 4, vote B. Election timeout: 0 of 18 illustrative seconds. C: Follower, current term 5, stored through 3, known commit index 3, vote none. Election timeout: 0 of 6 illustrative seconds.BLeaderTerm 5Commit 4Stored 41–3T5x = 8✓4T5x += 1✓5——Last T5/#4 · Vote BHeartbeat interval0 / 1sAFollowerTerm 5Commit 4Stored 41–3T5x = 8✓4T5x += 1✓5——Last T5/#4 · Vote BElection timeout0 / 18sCFollowerTerm 5Commit 3Stored 31–3T5x = 8✓4——5——Last T5/#3 · Vote —Election timeout0 / 6s
1 / 10

Working majority

A later snapshot: B leads term 5. B and A know #4 is committed; C still ends at #3.

Three servers; two votes to win. Timers use illustrative seconds. Each server’s Commit label shows its local commitment knowledge; a packet’s Commit is the leader’s advertised index. Orange entries are stored but not yet known committed by that server.

The servers electing a new leader overlap with the servers that stored a committed entry. Together with the voting checks, this ensures that later leaders preserve committed entries.

A restarted server returns as a follower and catches up from the new leader. Without a reachable majority, new entries cannot commit. A returning server may also have uncommitted entries that disagree with the new leader.

Why the Current Term Matters

The commitment rule specifically counts copies of an entry from the leader’s current term. An inherited entry keeps its original term, even when a newer leader copies it to more servers.

The next demo follows stages (a)–(e) of Figure 8 in the Raft paper, adapted to three servers. Its boxes show entry terms, and its columns show log indexes. In (c), the term-2 entry reaches two servers, while the leader’s term-4 entry remains local. The older entry still cannot be declared committed by counting copies.

Stages (d) and (e) are alternative endings from (c): crashing first allows both uncommitted entries to be overwritten; replicating the term-4 entry to a majority commits it and the preceding log. With three servers, stage (a) starts with just one copy, because a second copy in term 2 would already commit that entry.

When a Majority Is Not Enough

(a) An entry from term 2

Term 2 · A leads

  1. (a)One copy
  2. (b)Conflict
  3. (c)Majority
  4. (d)Overwrite
  5. (e)Committed

One copy in term 2

ABC
ServerIndex 1Index 2Index 3
Aleader
1committed
2stored
Bfollower
1committed
Cfollower
1committed

Old entry: 1 / 3 copies

Numbers are entry terms. Stored does not mean committed. Dashed: uncommitted. Green / solid: committed.

Paused · 1 / 9

One copy in term 2

A leads term 2 and accepts an entry at index 2. Only A stores it. With three servers, a second copy would already form a majority, so this entry has not yet been replicated.

Three servers; two form a majority. A plays the paper’s S1, and C plays S5. Both alternative endings play once, then stop. Borders show whether an entry is committed, not whether each server knows it. Adapted from Figure 8 of the Raft paper.

Repairing Conflicting Logs

A leader can accept an entry and fail before a majority stores it. A later leader may accept a different command at the same position.

Each replication request includes the index and term of the entry immediately before the new entries. The follower checks that entry against its own log. If they disagree, it rejects the request without changing its log.

The leader moves nextIndex, the next position it will send to that follower, backward and retries until it finds a matching entry.

Log repair

A’s view of B: nextIndex 5 · confirmed 0

A matching prefix lets B replace an uncommitted conflicting suffixSeparate scenario: A and C have committed #4 in term 7. B knows commitment through #3 and still stores uncommitted #4–5 from term 5. B: Follower, current term 7, commit index 3. Log: 1 / term 5 / x = 1; 2 / term 5 / x += 2; 3 / term 5 / x = 8; 4 / term 5 / x = 99; 5 / term 5 / x += 1. A: Leader, current term 7, commit index 4. Log: 1 / term 5 / x = 1; 2 / term 5 / x += 2; 3 / term 5 / x = 8; 4 / term 7 / x *= 2. C: Follower, current term 7, commit index 4. Log: 1 / term 5 / x = 1; 2 / term 5 / x += 2; 3 / term 5 / x = 8; 4 / term 7 / x *= 2.BFollowerTerm 7Commit 3Stored 51–3T5x = 8✓#4T5x = 99#5T5x += 1ALeaderTerm 7Commit 4Stored 41–3T5x = 8✓#4T7x *= 2✓#5——CFollowerTerm 7Commit 4Stored 41–3T5x = 8✓#4T7x *= 2✓#5——
1 / 8

A returning server has a conflicting suffix

Separate scenario: A and C have committed #4 in term 7. B knows commitment through #3 and still stores uncommitted #4–5 from term 5.

A separate scenario. Only B’s uncommitted entries change. Each server’s Commit label shows its local commitment knowledge; a packet’s Commit is the leader’s advertised index.

Once that entry matches, the follower:

  1. Compares the incoming entries with its own.
  2. At the first conflicting term, deletes that entry and every entry after it.
  3. Stores the leader’s replacement entries durably.
  4. Updates its commit index using the leader’s information, then acknowledges the request.

A matching preceding entry alone does not cause deletion. An incoming entry must conflict with an existing one.

Only uncommitted entries can be replaced. The Raft paper describes these checks.

Conclusion

Raft gives servers a shared order for commands and preserves committed entries when leaders change. A majority lets the cluster make progress while slower servers catch up. If too few servers can communicate, new entries wait until a majority is reachable again.