Every algorithm in Phases 4 through 7 of this series — Paxos, Raft, PBFT, all of it — is, underneath its specific mechanics, solving the exact same abstract problem: State Machine Replication (SMR). The core insight, formalized by Lamport and Schneider in the 1980s, is almost suspiciously simple: if every replica starts in the same state and applies the same sequence of deterministic commands in the same order, every replica ends up in the same state — guaranteed, by definition of "deterministic," with no additional coordination needed once that sequence is agreed on. This reframes the entire replication problem (article 1.2) from "how do replicas agree on data" into "how do replicas agree on an ordered sequence of commands" — a reframing that turns out to make the problem dramatically more tractable, and it's the reason every classical consensus algorithm you'll meet from here on is really an "agree on a log" algorithm, not a "agree on data" algorithm.
The core idea, precisely
A deterministic state machine is any system where the next state is a pure function of the current state and an input command: next_state = f(current_state, command), with no randomness, no wall-clock reads, no external side-effect dependence baked into f itself. Given that definition, a remarkably strong guarantee follows almost for free:
This is the single most important reframing in the entire series, so it's worth restating from a different angle: replicating a complex, mutable, ever-changing database is genuinely hard to reason about directly — what does it even mean for two copies of a live, growing dataset to "agree"? But replicating an ordered list of commands is a much simpler problem, because a list is just a sequence, and "do these two sequences match" is a comparison any two parties can check trivially. SMR's insight is that if you can solve the simpler problem (agree on a sequence of commands) you get the harder one (agree on the resulting state) for free, as a mathematical consequence rather than something you have to separately verify.
Fig 1 — Two replicas that never coordinate on the resulting state, only on the command sequence, still provably converge.
Why determinism is the load-bearing requirement
The entire guarantee collapses without determinism, and it's worth being concrete about the ways real code accidentally violates it — because this is a genuinely common source of production bugs in replicated systems, not a theoretical nitpick:
- Reading the wall clock inside command logic. A command handler that does
if timestamp() > deadline: reject()will evaluate differently on different replicas applying the "same" command at slightly different real moments — this directly reconnects to article 2.1's lesson that physical clocks can't be trusted for anything correctness-critical. - Iterating over an unordered collection. Many languages' hash maps/sets don't guarantee consistent iteration order across processes (or even across runs of the same process, depending on hash randomization settings) — a command handler that depends on iteration order to decide something (like "process the first matching entry") can diverge silently between replicas.
- Using true randomness without a shared, replicated seed.
random.random()called independently on each replica produces different sequences on each — any command logic depending on it directly breaks the guarantee. The fix, when randomness is genuinely needed in the state machine's logic, is to make the random value itself part of the command (generated once, by whoever proposes the command, then replicated as data) rather than regenerated independently by each replica. - Multi-threaded non-determinism inside a single replica's command application. If applying one command spins up concurrent threads whose interleaving affects the result, two runs of the exact same command on the exact same replica could even produce different results — this is why production SMR implementations (including the state-machine layer inside Raft/Paxos-based systems like etcd) apply commands strictly sequentially, one at a time, on a single logical thread, specifically to preserve determinism.
The SMR architecture: three components
Every SMR-based system, regardless of which specific consensus algorithm it uses to agree on the command sequence, has the same three-part shape:
- The consensus module — the machinery (Paxos, Raft, etc. — Phase 5 onward) that gets every replica to agree on the same sequence of commands, in the same order. This is where nearly all the algorithmic complexity in this entire series lives.
- The replicated log — the actual ordered, append-only record of agreed-upon commands, durably stored. Article 3.2 gives this its own full treatment, because the log itself — not just the abstract "sequence" — has real, important engineering properties (durability, compaction, snapshotting) that matter enormously in practice.
- The state machine — the application-specific logic that takes a command from the log and deterministically applies it to local state. This is usually the simplest part conceptually (it's often literally just your application's business logic, wrapped to be deterministic) but it's also where the determinism requirement above has to be enforced, usually by the application developer, not the consensus library.
Fig 2 — The consensus module's entire job is agreeing on log order; everything after that is deterministic and needs no further coordination.
Why this separation is the single biggest reason Paxos/Raft are reusable
This architectural separation is what makes it possible to build a general-purpose consensus library (like etcd's raft implementation, used far beyond etcd itself — by CockroachDB, TiKV, and others, all with completely different application logic) rather than needing a bespoke, from-scratch consensus protocol for every different application. The consensus module doesn't need to know or care what the commands mean — "SET x=5", "DEBIT account A $10", "CREATE lock L" are all just opaque byte blobs to the consensus layer. Its only job is agreeing on their order. The state machine layer is where the domain-specific meaning lives, and it's swappable independently of the consensus mechanism — which is precisely why the same Raft implementation can power a key-value store, a distributed lock service, and a SQL database's replication layer, just by plugging in different state machines on top of the same ordered log.
SMR under Byzantine failures — a brief preview
Worth a brief forward-reference here, because it's a genuinely important qualifier: the SMR guarantee as stated assumes correct replicas apply the agreed commands faithfully. Under Byzantine failures (Phase 6), a compromised or malicious replica might apply commands incorrectly, or claim to have applied a different sequence than it actually did, even after correctly agreeing on the sequence via a Byzantine-tolerant consensus protocol. Byzantine SMR (Castro & Liskov's PBFT, and its descendants) needs additional machinery beyond plain SMR — output voting, where clients or other replicas cross-check that enough independent replicas produced the same result after applying the same command, not just that they agreed on the command sequence going in. This is a meaningfully different and stronger guarantee than crash-fault SMR provides, and it's why Byzantine consensus systems (Phase 6) are structurally more complex than the crash-fault classical algorithms in Phase 5, even beyond the consensus protocol itself.
FAQ
Does SMR mean every replica has to process commands at the exact same real-world moment?
No — SMR says nothing about timing, only about order. Different replicas can apply the same command sequence at different real-world times (one replica might briefly lag behind, catching up later) and still converge to the identical final state, as long as they apply the exact same commands in the exact same order eventually. This is exactly why a temporarily lagging follower in a Raft cluster (Phase 5.6) isn't "wrong" — it's just behind, and will converge once it catches up on the log.
Can two different state machines built on the same replicated log diverge if the log itself is correct?
Only if determinism is violated somewhere in the state machine logic (the bullet list above) — if the log is genuinely identical and applied by genuinely deterministic logic, divergence is mathematically impossible. In practice, "unexplained state divergence between replicas that agree on their log" is one of the most common classes of real production bugs in SMR-based systems, and it almost always traces back to an accidental non-determinism, which is exactly why that section of this article is worth taking seriously.
Is SQL a good fit for the "deterministic command" model?
Mostly, with caveats that real systems handle carefully — a SQL statement like UPDATE accounts SET balance = balance - 10 WHERE id = 5 is deterministic given a starting state. But statements involving NOW(), RANDOM(), or auto-incrementing IDs generated independently per-replica are not, and SQL-based replicated systems built on SMR (several databases in Phase 9) specifically rewrite or intercept these non-deterministic constructs — for example, replacing NOW() with a fixed timestamp value chosen once by the proposer and replicated as part of the command, rather than re-evaluated independently by each replica.
Why not just replicate the raw database file/disk state directly instead of a command log?
That's a legitimate, different strategy (physical/disk-level replication, as opposed to logical command replication) with real trade-offs — it can be simpler in some ways but ties you much more tightly to a specific storage engine's on-disk format, and doesn't give you the same clean "log is the single source of truth, replay it anywhere" property that makes SMR-based systems easy to reason about, debug, and extend (e.g. adding a new replica by just replaying the log from scratch, covered more in Phase 3.2).
Takeaways
- State Machine Replication (SMR) reframes "replicas must agree on data" into "replicas must agree on an ordered sequence of deterministic commands" — a strictly easier problem with the same guaranteed outcome.
- The core guarantee is a pure consequence of determinism: same starting state + same commands + same order = same ending state, provably, with no further coordination needed during application.
- Determinism is easy to accidentally violate — wall-clock reads, unordered iteration, unshared randomness, and even floating-point differences across hardware are all real, documented sources of silent replica divergence.
- Every SMR system has the same three layers: a consensus module (agrees on order, doesn't care what commands mean), a replicated log (durable ordered record — full treatment next), and a state machine (application-specific, must be deterministic).
- This clean separation is exactly why general-purpose consensus libraries (etcd's raft package, for instance) can power wildly different applications just by swapping the state machine layer.
- Under Byzantine failures (Phase 6), plain SMR isn't enough — you additionally need output voting to detect a correctly-agreed command being incorrectly applied by a compromised replica.
References & further reading
- Schneider — Implementing Fault-Tolerant Services Using the State Machine Approach: A Tutorial (1990) — the canonical SMR reference, remarkably readable.
- Lamport — Time, Clocks, and the Ordering of Events (1978) — foundational context; also article 2.2's primary source.
- cvam.sight — Consensus 1.2: The Replication Problem — the informal replication problem this article's abstraction formally solves.
- cvam.sight — Consensus Algorithms series hub