Skip to content
KEDBYTE
Site navigation
How Data Works
Chapter
37

Consensus: Agreeing Despite Failure

Part F · Data Across Machines|3,678 words|about 16 min read|Volume F

37.0 What this chapter gives you#

  1. Consensus helps participants agree on a decision despite specified failures. In a replicated-log system, the decisions determine which commands occupy the shared history and in what order they may be applied.
  2. You will follow a small Raft-style trace through terms, durable voting, log replication, commitment and a leader change. You will distinguish safety from progress and a protocol explanation from a complete implementation.
  3. The companion exercises check selected predicates and traces. They are not a new consensus library, a formal proof of Raft or evidence that a production cluster survived arbitrary failures.

37.1 The agreement problem#

37.1.1 PLAIN — in simple words#

  1. Copies are useful only if the system has rules for deciding which changes count. Two replicas independently accepting incompatible commands at the same position cannot both be treated as one coherent history.
  2. A replicated state machine applies the same agreed commands in the same order. If the starting state and command behaviour are suitably defined, the replicas can produce matching results.
  3. Agreement is not the same as judging whether the command reflects reality. A group can agree to store an incorrect price if the application supplied one.

37.1.2 PLAIN — a picture in your head#

  1. Three clerks maintain copies of an instruction ledger. Before an instruction becomes official, they follow rules determining that this exact instruction occupies this exact ledger position.
  2. Each clerk then carries out official instructions in order. A reservation after a replenishment can differ from the same reservation before it, so order matters.
  3. Where the comparison breaks: a consensus protocol depends on precise persistent state, messages and failure assumptions. Informal discussion among clerks is not an equivalent algorithm.

37.1.3 PLAIN — a worked example#

  1. Begin a separate fictional stock state at 5. Command A reserves 3 if enough stock remains. Command B reserves 4 under the same rule.
  2. Applying A then B accepts A, leaves 2 and rejects B. Applying B then A accepts B, leaves 1 and rejects A.
  3. Both orders can preserve non-negative stock, but they produce different accepted customers. Replicas must not silently choose different orders while claiming one shared result.
  4. Consensus can choose the order. The state machine must still implement the reservation rule correctly and retain request identities so a retry does not become a second reservation.

37.1.4 PLAIN — what is really happening inside#

  1. The log records commands, while the application state is the result of applying the committed prefix. A stored entry need not already be committed, and a committed entry need not already be applied on every follower.
  2. Commands should not independently consult uncontrolled local time, randomness or outside services and then expect identical results. Nondeterministic choices need to be controlled or represented in the agreed input under the system’s design.
  3. External actions remain separate. Agreeing that an email should be sent does not establish that the recipient received it once.

37.1.5 TECHNICAL — the engineer’s version#

  1. Replicated state machines require an agreed command sequence and deterministic or otherwise consistently specified application semantics. Raft decomposes replicated-log consensus into leader election, log replication and safety rules. [S154]
  2. Distinguish log agreement from domain validation, authorization and external-effect delivery. Consensus does not replace constraints, idempotency or an outbox protocol.
  3. The failure model here is crash and communication failure, not arbitrary malicious participants fabricating votes or violating the algorithm. Byzantine fault tolerance requires different assumptions and mechanisms.

37.1.6 WORDS — remember these#

  1. Consensus: agreeing under a specified failure model — a protocol problem requiring compatible decisions and defined progress conditions. Replicated state machine: copies execute one agreed command sequence — an architecture connecting log agreement to matching application state. Committed prefix: the log portion accepted as final under the protocol — entries eligible for ordered application rather than merely present on one disk.

37.2 Logs and terms#

37.2.1 PLAIN — in simple words#

  1. A log position says where an entry sits. A term identifies a period of attempted leadership. The two numbers answer different questions.
  2. Terms let participants recognize obsolete messages and authority. Log entries retain the term in which the leader originally accepted them.
  3. A participant must remember important voting and log information across restarts. Forgetting a previous vote can allow incompatible decisions that the protocol was designed to prevent.

37.2.2 PLAIN — a picture in your head#

  1. A ledger has page numbers and a separate appointment number for each supervisor. Page 8 might have been written during appointment 3.
  2. A new supervisor does not renumber every old page as though it were newly created. The old appointment numbers help compare histories.
  3. Where the comparison breaks: terms are protocol counters, not real-time dates or fixed-length time periods. Two machines can temporarily have different beliefs about the current term.

37.2.3 PLAIN — a worked example#

  1. A log might contain (index 1, term 1, set stock to 5) and (index 2, term 2, reserve 3). A later leader in term 3 can retain both entries without changing their term labels.
  2. Compare candidate X ending at (term 4, index 7) with voter Y ending at (term 3, index 100). Under Raft’s freshness comparison, X’s higher last term is more up-to-date despite its smaller index.
  3. If both end in term 4, the longer log is more up-to-date. A candidate ending at index 6 is then behind a voter ending at index 7.
  4. The lab checks this comparison as a predicate. It does not infer full log validity merely from two numbers supplied by an untrusted caller.

37.2.4 PLAIN — what is really happening inside#

  1. Raft participants keep persistent current-term, vote and log state. Their messages carry enough context to reject obsolete requests and test whether a proposed log continuation matches the preceding entry.
  2. A follower does not accept an arbitrary suffix at an arbitrary position. The leader supplies the previous index and term so the follower can check continuity.
  3. If a conflicting uncommitted suffix is replaced, the accepted prefix remains protected by the protocol’s election and commitment rules. An operator should not generalize that into permission to discard arbitrary business history.

37.2.5 TECHNICAL — the engineer’s version#

  1. Raft’s persistent state includes currentTerm, votedFor and log entries. Required state must be durably updated before the relevant successful response, according to the algorithm’s storage assumptions. [S154]
  2. Log matching uses index and term; election freshness compares last term first and last index second. Term counters are not wall-clock timestamps. [S154]
  3. These small predicates are necessary pieces, not an implementation. Message retries, durable ordering, crash recovery, membership and application integration remain part of a real protocol.

37.2.6 WORDS — remember these#

  1. Term: a protocol generation for leadership attempts — a monotonically advancing counter used to reject obsolete authority and compare log histories. Log index: a position in the command sequence — an ordinal distinct from the term in which an entry was created. Log matching: matching positions imply compatible preceding history under the protocol — a property enforced through entry terms and append checks.

37.3 Majorities#

37.3.1 PLAIN — in simple words#

  1. A majority is more than half of the configured participants. Two majorities of the same fixed group must overlap.
  2. Raft uses that overlap together with voting and log rules. A participant’s durable refusal to make incompatible promises gives the overlap its protective meaning.
  3. Counting machines without enforcing those rules is not consensus. The set calculation and the protocol must both be correct.

37.3.2 PLAIN — a picture in your head#

  1. In a group of three clerks, approval from two always includes at least one clerk from any other pair of two. In a group of five, groups of three also overlap.
  2. If the shared clerk obeys the required memory and eligibility rules, incompatible proposals cannot simply pass through unnoticed.
  3. Where the comparison breaks: the protocol does not ask a human to recognize semantic contradictions. It enforces specific rules about terms, votes and logs.

37.3.3 PLAIN — a worked example#

  1. A three-member group requires two participants for a majority. It can lose one participant and still potentially make progress; with only one reachable participant it cannot obtain a majority.
  2. A five-member group requires three. Two can be unavailable while a suitable connected majority remains, but a split of two, two and one has no majority component.
  3. Adding a fourth participant to a three-member group raises the majority to three. The simple maximum unavailable count remains one; adding one server does not necessarily add another tolerated failure.
  4. These arithmetic statements assume fixed membership and otherwise suitable communication and behaviour. Reachable head count alone does not guarantee immediate election or progress.

37.3.4 PLAIN — what is really happening inside#

  1. A candidate seeks votes for its term. A voter grants at most one vote per term and only when the candidate satisfies the log condition.
  2. A leader replicates entries and tracks the positions acknowledged by followers. Under the required rules, a current-term entry replicated to a majority can advance commitment.
  3. The phrase “current-term” matters. An older entry merely appearing on a majority is not, by that fact alone, sufficient for the ordinary Raft commitment rule.

37.3.5 TECHNICAL — the engineer’s version#

  1. For N fixed members, a majority has floor(N/2)+1 members. The associated intersection supports, but does not replace, Raft’s durable-vote and log-freshness rules. [S154]
  2. A leader advances commitment by counting replicas only for an entry from its current term. Once such an entry is committed, preceding entries become committed through the log-prefix rules. [S154]
  3. Membership transitions cannot be treated as independent edits to local server lists. They must preserve safety across configurations; the paper’s joint-consensus method is one explicit design.

37.3.6 WORDS — remember these#

  1. Majority: more than half of the configured group — floor(N/2)+1 participants for a fixed N-member configuration. Voting restriction: a rule limiting acceptable leadership promises — eligibility and one-vote-per-term conditions that help preserve committed history. Current-term commitment: commit advancement based on a new-term entry — the Raft rule preventing unsafe conclusions from replica counts of older entries alone.

37.4 Leader changes#

37.4.1 PLAIN — in simple words#

  1. A leader can fail after some followers received an entry and before others did. The next leader must preserve already committed work while resolving incompatible uncommitted endings.
  2. Being elected is not permission to replace the past with whatever the new machine happens to prefer. Election eligibility and log repair work together to preserve the accepted history.
  3. Clients can still be uncertain about a request whose reply was lost. The new leader needs the application’s retained request outcome to answer that question safely.

37.4.2 PLAIN — a picture in your head#

  1. One clerk disappears while distributing an instruction. Two clerks have the accepted instruction; the third has an older notebook.
  2. The replacement procedure must not let the older notebook erase an instruction already made official. Nor should an unapproved private note automatically become official merely because someone finds it later.
  3. Where the comparison breaks: terms and voting rules—not a majority’s informal recollection—determine which history a candidate may lead.

37.4.3 PLAIN — a worked example#

  1. A, B and C share committed entry 1 from term 1, setting stock to 5. A leads term 2 and appends entry 2, reserving three units under request R-CONS-1.
  2. A and B durably store entry 2. Under the stated current-term rule and otherwise valid protocol, A commits it and applies the reservation, leaving 2. Its success reply is lost.
  3. A becomes unreachable. C still ends at entry 1 and cannot obtain B’s vote for a candidate log that is behind B’s. B can seek a later term with the more up-to-date log.
  4. After B becomes the legitimate term-3 leader, it replicates its prefix and a term-3 no-op entry to a majority. C can then learn and apply the committed reservation in order. The retry of R-CONS-1 returns the retained result instead of reserving three again.

37.4.4 PLAIN — what is really happening inside#

  1. The new leader may contain an entry whose commitment status is not yet known locally. Committing a current-term entry helps establish the preceding prefix under the protocol.
  2. Followers compare previous index and term when accepting appends. The leader can step back to a matching prefix and send the correct continuation.
  3. State-machine application follows commitment in order. A follower must not apply a speculative command merely because it appeared in its local log.

37.4.5 TECHNICAL — the engineer’s version#

  1. Raft’s Leader Completeness property connects election restrictions with preservation of committed entries. Its log-repair mechanism can overwrite conflicting uncommitted follower suffixes, not already applied committed history in a correct execution. [S154]
  2. A new leader’s read-only path needs safeguards against stale authority and incomplete commitment knowledge. Serving a local read simply because a process still believes it is leader is insufficient. [S154]
  3. The trace is an educational schedule under stated assumptions. It omits message serialization, durable storage implementation and complete membership management and must not be used as deployable protocol code.

37.4.6 WORDS — remember these#

  1. Leader completeness: later valid leaders retain committed history — a safety property established by the full consensus protocol. No-op entry: an agreed command with no domain change — an entry useful for establishing protocol progress without altering the business state. Speculative suffix: entries not yet accepted as committed — a local log continuation that may be replaced under valid recovery rules.

37.5 Safety and progress#

37.5.1 PLAIN — in simple words#

  1. Safety means the forbidden thing does not happen, such as two replicas applying different commands at the same committed position. Progress means useful work eventually gets decided under the required conditions.
  2. A system can remain safe while temporarily unable to make progress. Stopping without a majority can preserve the accepted-history rule.
  3. A system that always returns something may be responsive but unsafe if it invents incompatible decisions. Neither property should be inferred from the other.

37.5.2 PLAIN — a picture in your head#

  1. A shop can pause reservations when it cannot establish who owns the remaining allocation. Customers wait, but the shop avoids promising the same item twice.
  2. Letting every disconnected clerk approve reservations may keep counters busy while breaking the shared-stock rule.
  3. Where the comparison breaks: the acceptable availability cost is an application decision. Consensus provides mechanisms and limits; it does not decide which service policy users should accept.

37.5.3 PLAIN — a worked example#

  1. A five-node group splits into {A,B} and {C,D,E}. The three-node side may form a valid majority if the protocol’s other conditions hold. The two-node side cannot independently commit new entries by the same fixed-membership majority rule.
  2. If all communication becomes arbitrarily delayed, even a live group may repeatedly fail to settle on a leader in a timely way. Safety need not disappear merely because progress is poor.
  3. If an operator changes both sides’ membership independently to make each side a local majority, the original intersection argument no longer applies.
  4. The lesson is not to force a green availability light by removing the rule that protected the data.

37.5.4 PLAIN — what is really happening inside#

  1. Progress depends on enough suitable participants communicating for long enough and on operational resources such as storage and processing being available.
  2. Timer choices affect election stability and latency. They do not repair an implementation that forgets votes or acknowledges entries before meeting its persistence assumptions.
  3. A production consensus library also needs log compaction, snapshot installation, membership changes, authentication, resource bounds and careful crash testing. The short core algorithm is not the whole service.

37.5.5 TECHNICAL — the engineer’s version#

  1. State safety and liveness assumptions separately. Raft’s intended safety does not require accurate wall-clock timing, while practical progress depends on suitable timing and communication conditions. [S154]
  2. The general impossibility discussion around asynchronous agreement explains why unrestricted failure and timing assumptions cannot be hidden behind a promise of guaranteed immediate progress. [S153]
  3. Crash-fault consensus does not tolerate participants arbitrarily forging state or violating the protocol. Secure transport and membership authentication are necessary operational protections but do not transform the algorithm into Byzantine consensus.

37.5.6 WORDS — remember these#

  1. Safety: prohibited outcomes never occur under the model — a property such as preserving a single committed command at each log position. Liveness: required progress eventually occurs under the assumptions — a property distinct from avoiding incorrect outcomes. Byzantine behaviour: a participant acts arbitrarily or maliciously — a failure model stronger than ordinary crash and omission failures.

37.6 Reading a consensus trace#

37.6.1 PLAIN — in simple words#

  1. A useful trace records enough state to explain why a decision was allowed: configuration, term, log positions, acknowledgements and commitment progress.
  2. A line saying “majority reached” is weak evidence without naming which participants counted and what they had actually confirmed.
  3. Read the trace as a sequence of justified transitions. Ask what each observer knew at that point rather than using facts discovered only later.

37.6.2 PLAIN — a picture in your head#

  1. A meeting record should show who was eligible, what proposal was considered and which approvals were valid. A final sentence saying “everyone agreed” hides the evidence.
  2. A later replacement must be able to follow the same decision trail without relying on the original coordinator’s memory.
  3. Where the comparison breaks: consensus traces can be incomplete or sampled. Logs alone may not expose the precise persistence point or every message that influenced execution.

37.6.3 PLAIN — a worked example#

  1. For the Chapter 37 fixture, write a table with columns: step, current configuration, term, leader, each node’s last entry, committed index and applied state.
  2. At the term-2 majority acknowledgement, record A and B’s durable entry-2 confirmations—not merely that their processes are alive. At C’s failed candidacy, record the last-term/index comparison that causes B to refuse.
  3. At the term-3 no-op commitment, show that the required majority contains the new entry and that application proceeds through the earlier reservation first.
  4. The companion checks cover majority arithmetic, freshness comparison and current-term commit eligibility. They do not replay an actual network cluster or certify a full consensus implementation.

37.6.4 PLAIN — what is really happening inside#

  1. A trace should distinguish observed, inferred and assumed state. “Disk flushed” requires a relevant acknowledgement or instrumentation; it cannot be inferred from a request being sent.
  2. Counterexamples are valuable. Try a stale candidate, an obsolete term, too few acknowledgements, an older-term entry and a repeated client request.
  3. Any claimed result should identify the software version and failure injection used. A pure predicate test has a different evidentiary scope from a crash-restart experiment on a real cluster.

37.6.5 TECHNICAL — the engineer’s version#

  1. Review invariant checks alongside traces: monotonic terms, one valid vote per term, matching committed prefixes, ordered application and correct membership-aware commit rules. [S154]
  2. Independent formal specifications, model checking and implementation fault tests address different risks. None can be replaced by a diagram that simply assumes every desired property.
  3. Use established, maintained consensus implementations for real systems and verify their integration boundaries. The code accompanying this book is explicitly bounded educational material, not a recommendation to deploy a hand-built consensus service.

37.6.6 WORDS — remember these#

  1. Consensus trace: a record of protocol-relevant transitions — evidence connecting terms, votes, log positions and application state. Invariant check: testing a condition that should always hold — a verification step distinct from testing only one successful output. Commit eligibility: evidence satisfying a commitment rule — the conditions permitting a particular log position to become committed.

37.97 Practice and worked answers#

  1. Why can two valid reservation orders produce different winners? The first accepted reservation changes the state seen by the second. Replicas need one agreed command order.
  2. Which Raft log is more up-to-date: last term 4/index 7 or term 3/index 100? The term-4 log, because last term is compared before index.
  3. How large are majorities for three, four and five members? Two, three and three respectively.
  4. Can an older-term entry be declared committed merely because a new leader sees it on a majority? Not under Raft’s ordinary replica-counting commitment rule. A current-term entry is needed to advance commitment by that rule.
  5. Why may C fail to win B’s vote in the worked trace? C’s log is behind the committed-history-bearing log B already has.
  6. Does an unavailable minority necessarily make the system unsafe? No. Correctly refusing to commit without the required quorum can preserve safety while reducing progress.
  7. Does consensus alone stop a retried reservation from executing twice? No. The state machine needs request identity and retained result handling.
  8. What do the companion predicates establish? Their documented arithmetic and eligibility behaviours for supplied cases. They do not establish a complete networked Raft implementation.

37.98 Common wrong ideas#

  1. Wrong: consensus proves the business data is true. Right: it agrees on commands; domain validation remains necessary.
  2. Wrong: stored, committed and applied are the same state. Right: they are different protocol milestones.
  3. Wrong: a term is a wall-clock interval. Right: it is a protocol generation counter.
  4. Wrong: the longest log always wins. Right: Raft compares last term before last index.
  5. Wrong: any majority copy count proves commitment. Right: current-term, membership and protocol rules matter.
  6. Wrong: a leader can safely answer all local reads indefinitely. Right: stale-authority and commitment-knowledge safeguards are required.
  7. Wrong: crash-fault consensus covers malicious arbitrary participants. Right: that is a different failure model.
  8. Wrong: a short toy algorithm is production consensus. Right: persistence, recovery, membership and integration add substantial obligations.

37.99 Chapter summary in 20 lines#

  1. Consensus helps participants agree under a specified failure model.
  2. Replicated state machines apply an agreed command sequence.
  3. Agreement does not replace business validation or authorization.
  4. Log storage, commitment and application are separate stages.
  5. Terms distinguish successive leadership attempts.
  6. Log indexes identify positions rather than authority generations.
  7. Votes and required log state must survive relevant crashes.
  8. Raft compares last term before last index for election freshness.
  9. Fixed-group majorities overlap.
  10. Durable voting and log rules give that overlap its safety meaning.
  11. Current-term entries govern replica-counting commitment advancement.
  12. Later valid leaders preserve committed history under the full protocol.
  13. Uncommitted follower suffixes may require repair.
  14. Client retries still require idempotency state.
  15. Read-only paths need protection against stale leadership.
  16. Safety and progress are different properties.
  17. Progress requires suitable communication, participants and resources.
  18. Membership changes need their own safety-preserving procedure.
  19. Trace evidence must distinguish observations from assumptions.
  20. Educational predicates are not a production consensus implementation.

Return to contents