State Machine Replication and Deterministic Apply

By the end of this lesson, you will be able to...

• Trace a committed command from a replicated log into the same service state on several replicas.

• Identify nondeterministic inputs that would make replicas diverge during application.

• Place acknowledgement, recovery, and external side effects on the correct side of the apply boundary.

Idea in one sentence: Consensus chooses a durable order of commands; deterministic application turns that order into one shared service state.

Core Insight

Atlas has three replicas for a small metadata service. An operator asks to add node n4. The cluster can agree that add_member(n4) belongs at log index 57. That agreement matters, but it is not yet the visible configuration. Each replica must turn entry 57 into the same local state change.

The tempting model is: “matching logs mean matching service state.” That works only when every replica applies the same committed entries in the same order and computes the same result. A replica that applies a proposal too early, consults its local clock, or sends an email while replaying can create a different service even though the log looks correct.

State machine replication makes the missing contract explicit:

same starting state
+ same committed command sequence
+ deterministic apply
= same resulting state

The replicated log is the authoritative history. The state machine gives that history meaning: membership changes, keys update, leases advance, or a deployment generation becomes current. This lesson uses a simplified service model. Exact commit rules differ across protocols, but the boundary between proposed, committed, and applied state must remain visible.

The Situation

Atlas stores the set of voting members in a replicated state machine. Before the request, all replicas have applied through index 56:

applied_index = 56
members = [n1, n2, n3]

The operator submits add_member(n4). The operator wants a clear promise: once the service reports success, a recovering replica will rebuild a configuration that includes n4; a lagging replica must not invent a different membership change at index 57.

There are four moving parts:

Keeping these jobs separate makes failures easier to reason about. A log position answers “where does this command belong?” An applied result answers “what does the service state now say?”

The Initial Model: Apply When the Leader Sees a Request

The smallest implementation is attractive:

leader receives add_member(n4)
leader updates its local members list
leader sends success to the operator
leader replicates the entry later

It has low latency in the happy path. It is also unsafe. Suppose the leader updates its own state at index 57, replies success, and then crashes before enough replicas preserve the entry. A replacement leader can legitimately continue from the committed prefix ending at 56. The new leader does not have evidence that n4 belongs in the shared history.

The operator has now seen a service result that recovery can erase. A follower can also diverge if it applies an uncommitted entry that the eventual leader does not retain.

The correction is not “wait for every replica.” The exact protocol may allow progress while some replicas are down. The needed rule is narrower: apply only the prefix that the protocol has made committed, and acknowledge only after the service can give a stable result according to its stated guarantee.

The Better Model: A Deterministic Transition Function

In plain English, every replica runs the same small program over the same approved commands.

In Atlas, the program takes the previous member set and add_member(n4), then produces the new member set.

The technical name is a replicated state machine. Its apply function can be described as:

next_state, result = apply(previous_state, committed_command)

For this model to hold, apply must depend only on the command and replicated state. It may not quietly inspect a replica-local input that another replica can see differently.

Deterministic does not mean simultaneous. Replica n3 may be offline and apply later. It means that whenever n3 reaches the same committed prefix, n3 produces the same state and result as n1 and n2.

The Mechanism Step by Step

The following trace uses illustrative indices and assumes Atlas has already established its protocol-specific commit evidence for index 57.

The important intermediate state is step 3. “Committed” says the command belongs to the history that a valid future leader must preserve. “Applied” says a particular state machine has executed it. A healthy leader may have a committed index ahead of a follower's applied index for a short time. That gap is normal only if the service is careful about which replica answers which request.

Question: Why not return success immediately at step 3?

Answer: Some services can safely acknowledge after commit and apply asynchronously if the result is defined at the commit boundary. Others need the actual transition result, such as a compare-and-set outcome, so they wait until the leader has applied the entry. The design must state its boundary. It must not silently treat receipt, replication, commit, and apply as the same event.

So far, the log has done one job: preserve an order. Deterministic apply does the next job: make that order produce one inspectable service state.

A Second Trace: Why Local Time Breaks Replay

Now consider create_session(user=U). An early implementation hides the expiry calculation inside apply:

apply(create_session(U)):
    expiry = local_now() + 30 minutes
    store session(U, expiry)

At index 58, replica n1 reads 10:00:00; replica n2 reads 10:00:03. Both have the same command. They now store different expiry values. A snapshot from n1 and a replay on n2 no longer describe one service state.

Move the choice before agreement instead:

command = create_session(user=U, session_id=S17, expires_at=10:30:00Z)
apply(command):
    store session(U, S17, 10:30:00Z)

The timestamp and identifier are illustrative command fields, not measurements from a real Atlas system. The command now contains the information every replica needs. Clock quality can still matter when the leader chooses the value, but clock disagreement no longer makes replay compute different state.

Where It Breaks: External Effects and Duplicate Work

Deterministic internal state does not make an external effect deterministic. This apply function is dangerous:

apply(invoice_ready(I)):
    send invoice email for I
    mark I as sent

If a replica crashes after sending the email but before recording sent, recovery may replay the command and send a second email. If several replicas apply the same committed command, sending from each apply loop is worse.

Use two boundaries instead:

apply(invoice_ready(I)) -> durable state says "I is ready"
worker observes ready(I) -> calls email provider with idempotency key I
worker records a durable outcome or an explicit unknown/in-progress state

The state machine decides that an invoice is ready. A separate worker performs the side effect. The worker needs its own retry contract because a lost provider response can still leave the outcome unknown. This is the same boundary introduced in the previous capstone: agreement about a decision does not automatically make an outside system execute exactly once.

Cost, Limits, and Signals

State machine replication buys a clear recovery story and a strong basis for one service state. The trade-off is discipline and latency at explicit boundaries: commands must include relevant nondeterministic choices, apply must wait for commit, snapshots must match an applied prefix, and external work needs a separate idempotency boundary.

It does not solve every consistency question. A read from a lagging follower may observe an older applied prefix. A deterministic apply function cannot repair a wrong command chosen by the client. Membership changes require additional protocol rules; this lesson uses add_member only as a simple state transition, not as a complete reconfiguration procedure.

Useful operational signals are concrete:

• commit_index - applied_index: a growing gap shows that a replica is not applying committed work fast enough;
• snapshot index and restored applied index: they must describe the same state boundary;
• apply errors or panics: they can stop a replica from reaching the committed prefix;
• repeated external operation IDs: they show whether retries converge or duplicate effects;
• different state hashes for the same applied index in a test environment: they reveal a determinism failure.

These signals do not replace a proof or a protocol-specific checker. They tell an operator where the state-machine contract may be breaking in a running service.

Trace It Yourself

Check: A follower has applied through index 70. The leader has committed through 72, but has applied only through 71. May the leader claim that the result of command 72 is available?

Think first, then reveal.

Answer: Not if the service defines that result at the applied boundary. Index 72 is part of committed history, so followers should eventually preserve it. But no state machine in this trace has executed it yet. The leader may describe it as committed only if its API explicitly exposes that distinction; it should not fabricate the transition result.

Practice: Review a Deterministic Apply Function

A lock service proposes this command:

apply(acquire(resource=R, client=C)):
    token = random()
    if local_clock() < lease_deadline(R): reject
    else store owner=C, token=token
    notify an external webhook

Rewrite the design at the level of boundaries, not implementation syntax.

A good answer should mention:

• a command carries the chosen token and any authoritative expiry/epoch data, or those values are derived only from replicated state;
• the apply function records one deterministic owner/result for the committed command;
• the webhook is triggered by a separate, idempotent worker with a stable operation identity;
• a client result is tied to the service's declared commit-and-apply boundary;
• a test replays the same committed log on several replicas and compares their state and results.

Connections

The previous capstone established why a control plane keeps its authoritative decisions small and makes external work fenced and idempotent. This lesson explains how the authoritative command history becomes shared internal state.

The next lesson explains the evidence that makes a committed history survive later leaders: quorum intersection, ballots, and commit evidence.

Resources

• [PAPER] In Search of an Understandable Consensus Algorithm — Focus: The separation between replicated log, commit index, and applied state machine.
• [PAPER] Viewstamped Replication Revisited — Focus: Replicated state-machine execution and recovery across view changes.
• [PAPER] Paxos Made Simple — Focus: Chosen values and why a later attempt must preserve earlier evidence.
• [BOOK] Designing Data-Intensive Applications — Focus: The service-level model and the boundaries around external effects.

Key Takeaways

• A replicated log becomes a service only when replicas deterministically apply its committed prefix.
• Proposed, replicated, committed, and applied are different boundaries; an API must say which one its response represents.
• Time, randomness, local caches, and remote calls must not silently change replayed state.
• External effects need their own idempotent workflow because replaying internal state cannot make an outside system exactly once.
• Applied-index gaps, snapshot boundaries, operation identities, and same-index state comparisons make the contract observable.