Two clients simultaneously send 'SET x=1' and 'SET x=2' to a replicated key-value store using state machine replication. What must happen to ensure all replicas end in the same state?
ABoth commands must be rejected — concurrent writes are not allowed in SMR
BEach replica independently processes whichever command arrives first, since they will eventually converge
CConsensus must assign a single ordering to the two commands (e.g., slot 5: SET x=1, slot 6: SET x=2), and all replicas execute them in that order
DThe system picks the command from the client with the lower ID and discards the other
The entire point of SMR is that replicas must execute the same commands in the same order. If different replicas process the commands in different orders — replica A applies SET x=1 then SET x=2; replica B applies SET x=2 then SET x=1 — they end in different states (x=2 vs x=1 respectively). Consensus solves this by assigning a global ordering: all replicas agree that slot 5 is SET x=1 and slot 6 is SET x=2 (or whichever order is chosen), then everyone executes in that order. The specific order chosen doesn't matter; what matters is that it is the same for every replica.
Question 2 Multiple Choice
A replica in an SMR system was offline for several hours due to a hardware failure. It has now recovered. How does it return to a consistent state with the other replicas?
AIt cannot recover — any replica that misses commands is permanently inconsistent and must be replaced
BIt requests the current state from a majority of replicas and takes the most recent snapshot
CIt replays the shared command log from its last executed slot, re-executing each command in order until it catches up
DIt waits for the next client request, which will trigger a full state synchronization
This is one of SMR's most elegant properties. Because the state machine is deterministic, replaying the same commands in the same order from any consistent starting state produces the same result. The recovered replica simply reads the log entries it missed and re-applies them in sequence. Because every command was already agreed upon by consensus before being written to the log, there is no ambiguity about what to execute or in what order. The determinism of the state machine guarantees that after replay, the recovered replica is in exactly the same state as the others. This is why the log is the single source of truth.
Question 3 True / False
In state machine replication, each replica independently executes client requests and consensus is primarily invoked when replicas disagree about the result.
TTrue
FFalse
Answer: False
False. This describes a reactive, after-the-fact consistency repair — not SMR. In state machine replication, consensus is used proactively and continuously to assign every command to a specific position in the shared log *before* any replica executes it. Replicas do not execute commands independently and then compare results. They first agree on what command occupies each log slot, then all execute commands in log order. This is how SMR guarantees that replicas never diverge in the first place, rather than detecting and repairing divergence after the fact.
Question 4 True / False
A non-deterministic state machine — one that uses the current wall-clock time or a random number generator as part of its operation — cannot be replicated correctly using standard state machine replication.
TTrue
FFalse
Answer: True
True. SMR's consistency guarantee rests entirely on determinism: given the same starting state and the same command sequence, every replica must produce the same ending state. A state machine that reads the wall-clock time or generates random numbers will produce different results on different replicas even if they execute the same commands in the same order — because the wall-clock time or random seed will differ. To replicate a non-deterministic service, you must either (a) externalize the non-determinism (agree on the random value or timestamp through consensus before executing) or (b) use a different replication strategy. Standard SMR assumes determinism as a hard prerequisite.
Question 5 Short Answer
Why must the state machine be deterministic for state machine replication to guarantee that all replicas remain consistent?
Think about your answer, then reveal below.
Model answer: State machine replication guarantees consistency by having all replicas execute the same sequence of commands, relying on determinism to ensure they reach the same state. If the state machine is deterministic, then identical inputs in identical order always produce identical outputs — no matter when or where execution happens. Consensus ensures all replicas agree on the same command sequence (the same log). Determinism then ensures that executing that sequence from the same starting state produces the same ending state on every replica. If the machine were non-deterministic, replicas could execute the same commands in the same order and still diverge — because non-deterministic choices (random values, timestamps) would differ between nodes. Consensus fixes the 'what' and 'when'; determinism fixes the 'outcome given what and when.'
The key insight is that SMR is a two-part guarantee: consensus handles ordering, determinism handles outcome. Both are required. Students who understand only the consensus part may think that agreement on the command log is sufficient — but a non-deterministic state machine can produce different outputs from the same log on different nodes. The determinism requirement is not a technicality; it is the mechanism by which the ordered log translates into consistent state.