Consensus, elections, and committed log safety

Prerequisites: Replication, durable logs, majorities, and failure ambiguity.

Learning objectives

• Explain majority intersection in leader election.
• Trace a Raft election with log freshness restrictions.
• Distinguish safety from liveness under partitions.

Consensus lets participants agree on a value or an ordered sequence of commands despite specified failures. Replicated state machines use an agreed log so replicas apply the same deterministic operations in the same order. Merely electing a leader is insufficient: a new leader must preserve already committed history, and old leaders must not continue making conflicting decisions accepted as current.

Raft organizes time into numbered terms. Servers are followers, candidates, or leaders. A candidate increments its term and requests votes. Each server grants at most one vote per term, persisting relevant state across crashes. A majority of a fixed configuration elects a leader. Two majorities intersect, so at most one candidate can collect a majority in a term when voting rules are obeyed. This statement depends on durable voting state and the specified membership protocol.

Consider five servers A through E. A obtains votes from A,B,C and becomes leader in term 4. A network split then leaves A with B while C,D,E can communicate. The three-server side can elect a term 5 leader. A may temporarily believe it remains leader, but its two-server partition cannot commit new entries under the majority rule. When it learns of the higher term, it steps down. Local belief and authority to commit are different facts.

Log freshness restrictions prevent an elected leader from discarding committed entries. Raft compares candidates' last log terms, then indices when terms match. A follower grants a vote only to a sufficiently up-to-date candidate under the protocol. Log replication also checks the preceding entry's index and term before appending, repairing conflicting uncommitted suffixes. These rules work together; majority counts alone do not prove safety.

A subtle commitment rule matters: a leader uses majority replication to directly commit an entry from its current term. Earlier-term entries can become committed indirectly when such a current-term entry is committed. Treating any older entry found on a majority as immediately committed can be unsafe across leader changes. Study the paper's failure traces before simplifying this rule into an implementation.

Safety means incompatible decisions are not committed. Liveness means the system eventually makes progress under suitable timing and availability conditions. Delayed messages and split votes can postpone progress without violating safety. Randomized election timeouts help avoid repeated collisions, but do not make progress possible through every arbitrary network partition or indefinitely adversarial schedule.

Consensus normally assumes non-Byzantine crash failures in this discussion. Malicious or arbitrarily corrupted participants require a different model and protocol. Also, a committed request may be retried after its response is lost. The state machine still needs request deduplication when repeated commands would create duplicate business effects. Agreement about command order and exactly-once application intent are separate responsibilities.

Practice problem

A five-server cluster splits into groups of two and three. Explain which group can elect a leader and commit under a fixed majority configuration. Then a server has last log term 6,index 10. Compare candidates with term 5,index 20 and term 6,index 12 for the log-freshness voting check. Finally explain why a client retry after a lost successful response can still duplicate an application action despite a correct consensus log.

Worked solution

The three-server group can form a majority; the two-server group cannot independently commit new entries under the fixed configuration. A candidate ending in term 5,index 20 is less up to date than the follower ending in term 6,index 10 because the last term is compared first. A candidate ending in term 6,index 12 is sufficiently up to date by this comparison, although all other election rules still apply. If a client resends a command as a new request, both copies can legitimately enter the agreed log. Preventing two charges or two jobs requires a stable request identity and state-machine deduplication, not merely agreement that both commands occurred in a consistent order.

Check your understanding

In a five-server fixed configuration, an old leader is isolated with one follower while three servers elect a newer-term leader. What protects commitment safety?

• The two-server group cannot form a majority for new commitments, and term/log rules govern the new leader.
• A leader’s original election grants permanent authority.
• The old leader immediately knows every network partition.
• Both groups may commit independently and merge arbitrary histories later.

Explanation

A stale local belief does not supply the majority needed to commit. Election and log-preservation rules must still hold.

A voter’s last log entry is(term 6,index 10). Which candidate is fresher under Raft’s last-log comparison?

• The choice is determined solely by the candidate’s identifier.
• Both are equally fresh because each has an index at least 10.
• (term 5,index 20)
• (term 6,index 12)

Explanation

Compare last term first, then index. The lower-term longer log is not fresher, while the equal-term index 12 log is.

Primary reading

• In Search of an Understandable Consensus Algorithm, extended version: Diego Ongaro and John Ousterhout, Stanford University

Open the study and save your work →