Lesson browser Distributed consensus, replication, and fault tolerance lessons Previous: What consistency promises to a client Next: Quorums and the information in an intersection

Distributed systems · Lesson 5

Replication and the meaning of success

Trace durable appends, acknowledgments, commitment, and application.

By the end: Separate an entry’s existence from an irrevocable decision and from the leader’s knowledge.

Choose an authoritative order

In leader-based replication, a leader assigns each command a log index. Followers receive that ordered log. An entry might contain index 7, term 3, and Reserve(12, Ada). The index is a position; the term is a leadership epoch, introduced fully in lesson 8. A follower applies commands in the agreed order rather than deciding its own order of arrivals.

A deterministic state machine must also agree on inputs that would otherwise vary. If applying a command reads local wall time or generates random identifiers independently, equal logs can produce different results. Decide such values once and record them as command inputs, or use a deterministic rule. External effects need a separate delivery protocol; replaying a log must not blindly charge a card again.

Replicate commands with enough information to replay them

A replicated log contains an ordered record of proposed state transitions. An application table is the result of executing a committed prefix of that record. These are different representations. If the table is lost but the complete required log and initial state survive, deterministic replay can reconstruct it. If only the table survives, it may not reveal the exact command sequence or the result returned to each client. A practical recovery design must identify which representation is authoritative and which metadata it needs. This lesson starts with a short complete log, before snapshots and long-term retention enter the course.

Take a paper example with inventory initially 5. Index 1 records Reserve 2 units for order K, and index 2 records Reserve 4 units for order L. Every replica applies index 1 first, checks that 5 is at least 2, reduces inventory to 3, and records success for K. At index 2, each sees only 3, rejects L, and leaves inventory unchanged. A rejected application command can still occupy a committed log position. Agreement concerns which command ran at which position, not a promise that every submitted reservation will pass its business checks.

The command must contain enough information to make this reasoning repeatable. If the reservation handler asks a changing price service during application, replicas can disagree about the price or stop at different times. One approach is to choose a price under a separately defined authority before proposing the command and record the selected price and version as inputs. Application then uses those recorded inputs. That does not prove the price was fair or current. It makes the replicated transition reproducible. Any rule about rejecting an expired quote needs its own precisely defined time and authority assumptions.

An entry's index and term answer different questions. Index 7 identifies its position in one log. Entry term 3 records the leadership epoch that created it. If a later leader retains this entry, it remains an entry from term 3. The later election does not relabel old entries with its new term. A term number is not a timestamp, an application revision chosen by a client, or a count of successful writes. The election lesson will explain how servers obtain and persist terms. Here the distinction prevents confusing the order of commands with the sequence of leadership attempts.

External actions need another boundary. Executing an agreed command can update a local record saying that an email should be sent. Sending the email during replay would repeat the effect whenever the server rebuilds state. A common design records the obligation as replicated application state, then uses a separate sender with an explicit retry contract. Replication of that obligation does not by itself make the external delivery exactly once. The retries lesson will explain why stable request identities and atomic durable deduplication matter. For now, keep deterministic state changes separate from irreversible actions outside the state machine.

Four distinct milestones

Appending creates a local entry. Persisting makes it survive the specified crash. Replicating creates additional stored copies. Committing makes the entry part of the prefix the protocol must preserve across future leaders. Applying executes committed commands against application state. These are different events, even if a fast implementation performs some close together.

An asynchronous replication policy may reply after only the leader stores the write. That favors short acknowledgment latency but can lose an acknowledged update if the leader’s storage is lost and a lagging follower is promoted. Waiting for every replica increases the set of protected copies but lets any unavailable replica block new successes. Waiting for a majority is useful only with election and log rules that preserve acknowledged decisions. A copy count alone is not such a protocol.

Connect each acknowledgment to a durability promise

An acknowledgment is useful evidence only when its meaning is specified. A follower might acknowledge receipt into memory, completion of a local durable write, or application to its state machine. Those responses protect against different failures. In this lesson's lab, delivery creates a durable follower copy and the separate acknowledgment reports that copy to A. Real storage durability depends on the storage stack's contract. A process restart with intact storage differs from losing the entire disk, and both differ from a software defect that deletes every copy. Saying persisted without naming the covered failures leaves the client's protection ambiguous.

Consider a paper system whose leader A receives a reservation, stores it locally, and immediately returns success. B and C have not received it. If A's process stops but its disk survives, A may later recover the entry. If an operator instead promotes empty B and discards A's history, the service can lose the acknowledged reservation. The difference is not a change in what the client saw. It is a recovery policy that failed to preserve what success promised. A durable local append can support a limited contract, but it does not automatically support continued service from another replica with no copy.

Waiting for all three durable copies changes the failure cases and the waiting conditions. With copies at A, B, and C, losing A's disk need not lose the entry, assuming recovery preserves a surviving copy. But C's unreachable network link now prevents new acknowledgments even when A and B are healthy. Waiting for two can permit progress without C. To make those two copies an irrevocable decision across leadership changes, the system also needs rules restricting future elections and log replacement. The quorum chapter derives the arithmetic; the later Raft chapters supply the protocol obligations. Neither follows merely from choosing the number two.

Application introduces a separate delay after commitment. Suppose committed index 9 transfers inventory, but the leader's state machine has applied only through index 8. A response that includes the exact remaining inventory must wait for the command's application result, not merely the copy count. A client API could instead return an explicitly documented accepted status and provide a later result. Those are different contracts. Likewise, a read that promises the committed state cannot read an application table still behind its required boundary. Later read rules require both current authority and application through an appropriate safe prefix.

A useful paper ledger has one column for durable entries, one for evidence received by the leader, one for the committed boundary, and one for applied progress. Advancing any column requires a particular event. Receiving a durable acknowledgment can advance evidence; it does not execute the command. Applying an entry changes the table; it does not deliver a client response. Losing that response leaves the client uncertain even if the decision and its application survive. The model below exposes some of these distinctions through separate delivery and acknowledgment controls, while leaving application as an explained obligation rather than an independently controlled simulation.

Work through the model

Schedule replication yourself

Fixed leader A, fixed term 1, three durable replicas. Commands set x to their command number. This isolates delivery, acknowledgment, and commitment; it does not simulate elections, disk corruption, or a full Raft implementation.

A · leader

Reachable

Empty durable log

Confirmed to A through index 0.

B · follower

Reachable

Empty durable log

Confirmed to A through index 0.

C · follower

Reachable

Empty durable log

Confirmed to A through index 0.

A is the fixed leader in term 1. All durable logs are empty.

Committed prefix: 0. Green plus the word Committed shows the global decision, not each follower's local knowledge. Try append, deliver to B, crash before Ack; compare with append, deliver, Ack, check commitment. Reset clears all writes and restores links.

Milestone	A	B	Client
Append	Entry stored locally	Empty	Waiting
Replicate	Entry stored	Entry stored	Waiting
Ack and commit	Majority known	Entry stored	May receive success after required application
Response lost	Decision remains	Entry remains	Outcome unknown

Stage 1 of 4. All stages remain visible for comparison.

Speed Step 0 / 3

Successful replication and delivery of the success response are separate events.

Schedule copies and evidence independently

Start the lab with Reset cluster, then choose Append write at A twice. A's durable log contains commands 1 and 2, which set x to 1 and then 2. B and C still have empty logs. Deliver to B copies A's entire current prefix to B, not a selected single entry. B now has both commands, but its Confirmed to A value remains unchanged. Check commitment before acknowledging B. A still has only its own reported durable prefix, so the committed boundary cannot advance. The global observer sees two copies, but the leader's available evidence does not yet justify counting both.

Choose Ack from B and then Check commitment. A can now count two durable reports through index 2, so the displayed committed prefix advances to 2. The model computes the second-largest confirmed index among three members. That index has at least two reports covering it. If the reports are 2, 2, and 0, the boundary is 2. If they are 2, 1, and 0, the boundary is 1. On paper, interpret this as agreement about a prefix. Reporting index 2 in this model covers index 1 as well because delivery copies an ordered prefix without gaps.

Reset and try a different schedule. Append one write, deliver to B, then crash A before receiving B's acknowledgment. The durable entry remains on A and B. A's crash clears its remembered follower confirmations in this bounded model, so restarting does not supply a fresh report from B. After Restart A, acknowledge B again and check commitment. This exercise shows the difference between storage surviving and the leader collecting evidence about it. It is not a simulation of electing B, competing terms, or a production recovery algorithm. The model deliberately resumes the same leader with no competing authority.

Partitioning B blocks subsequent delivery and acknowledgment actions on that link. It does not erase B's durable log or retract an acknowledgment already received by A. After an entry has reached the model's committed prefix, later partitions do not decrease that prefix. Try committing index 1 with B, partitioning B, appending index 2, and delivering and acknowledging C. A can establish index 2 with a different responding pair. B may still show only index 1. The committed label is a global classification of entries that exist in each displayed log, not proof that B has learned a new commit boundary.

The four-entry limit keeps every log visible. Reset removes the experiment's writes and restores the initial links; it is not a valid procedure for erasing a live service's durable obligations. There is no applied-index control, disk-loss action, client retry sender, or replacement election. The animated evidence table also keeps every stage visible, and its highlight does not determine network timing. Use the controls to explain exactly why A can or cannot advance the shown boundary. Use separate paper cases for protocol features the controls omit, rather than interpreting a missing button as evidence that the corresponding failure cannot happen.

Separate truth from knowledge

Suppose A and B have stored an entry but B’s acknowledgment to A is delayed. The stored copies exist, but A cannot count a response it has not received. If A crashes, later recovery may discover those entries. The client’s timeout does not determine whether the operation will survive or eventually succeed. Never equate “the old leader did not reply” with “the command can be safely repeated under a fresh identity.”

The lab fixes the leader and term so you can isolate these milestones. It counts durable responses, then explicitly checks a majority. It does not implement failover or the rules that make a majority safe across terms. In the full Raft protocol, current-term commitment, voting restrictions, and prefix matching supply that missing argument. Continue through the election and log lessons before treating this lab’s arithmetic as a complete replication design.

Preserve the committed prefix across changes in authority

The fixed leader makes prefix reasoning easy because only one log order can grow. A real failover introduces another possible source of entries. Imagine a separate paper case in which A has a command at index 5 and C has a different command at index 5. They cannot both become final parts of one replicated history. A recovery protocol must decide which uncommitted suffix may change while protecting every committed entry. It must not tell a client that a command is irrevocable and later treat that command as an expendable conflict. This preservation obligation gives commitment its meaning beyond local storage.

Raft couples the preservation rule to elections and log matching. A follower checks a preceding index and term before accepting an extension. Candidates must pass a log-freshness restriction to receive votes. A leader directly advances commitment by counting a majority for an entry from its current term; earlier entries become committed as part of that entry's prefix. Copying an old-term entry onto a majority is not by itself enough to apply the direct commitment rule. These constraints are introduced here to mark what the lab omits. The election and log-safety lessons develop their mechanisms and a counterexample in detail.

The response boundary also depends on command identity. Suppose order K commits, the leader applies it, and the success response disappears. A client retries K through a later leader. Repeating the business action under a fresh identity can reserve inventory twice even if every log position is safely replicated. A robust retry design records a stable operation identity together with the effect and stored result as one atomic durable application transition. Recording only the identity before the effect risks suppressing unfinished work; recording it afterward leaves a window for repetition. Replication preserves whatever transition the application defines, including an incorrectly split one.

Logs also create an order for failures that clients may not see directly. A reservation can commit before a cancellation even if the reservation's response arrives after the cancellation's response. Network response order is not automatically log order when requests overlap. To reason about the client contract, return to the previous lesson's invocation intervals and results. The internal committed sequence must provide a legal explanation for them. A log is a mechanism for establishing order, not permission to ignore completed-before-invoked relationships. A supposedly successful operation cannot disappear merely because the next leader finds it inconvenient.

For a final guided case, write a response policy for the inventory command used earlier. Specify which durable failures the log survives, what establishes commitment, when the inventory check runs, and whether success includes the reservation result. Then remove A after each milestone in turn. Ask which surviving evidence can reconstruct the command and which protocol rule would authorize continued service. Do not invent an election inside the lab to answer that question. The unresolved step is exactly why replication, quorum intersection, and safe leader selection need separate lessons. Copying data answers where information exists; preserving a decision requires rules about future behavior.

Exercises

A missing acknowledgment

A persists entry 1. B persists it too, but B’s reply is delayed. C has no entry. What can A safely count right now?

Hint

Use A’s received evidence, not the diagram’s global view.

Worked answer

Replica	Stored index	Known by A
A	1	1
B	1	0
C	0	0

Physical copies and leader knowledge differ.

A can count only its own durable entry until a valid acknowledgment arrives. An observer sees two copies, but A does not yet know that B stored the entry. The fixed-term lab therefore cannot advance its known committed prefix based on that missing reply.

Replay a nondeterministic command

All replicas apply “set expiry to local now plus one hour.” Is equal log order enough for equal state?

Hint

Different clocks can yield different command inputs.

Worked answer

Replica	Local now	Computed expiry
A	10:00	11:00
B	10:02	11:02
Replay next day	Next day 10:00	Next day 11:00

Log agreement cannot repair nondeterministic application rules.

No. Clock readings can differ across replicas and replay. Record the chosen expiry timestamp in the command, then make application deterministic. Whether that timestamp correctly implements real-world expiration is a separate clock/authority question.

Sources and further reading

The explanations and worked answers above stand alone. These references provide the original algorithms, assumptions, and deeper proofs; they are not required downloads.

Ongaro and Ousterhout: In Search of an Understandable Consensus Algorithm, extended version
Raft protocol, Figure 2, safety and Figure 8, membership, snapshots, and client interaction. Primary protocol reference.

Lesson browser Distributed consensus, replication, and fault tolerance lessons Previous: What consistency promises to a client Next: Quorums and the information in an intersection