The model
State machine replication treats each replica as a deterministic state machine. Start every replica from the same initial state, feed them the same sequence of commands in the same order, and they must end in the same state.
The system never replicates the state itself. It replicates the ordered log of commands, and each replica applies them to derive identical state independently.
Why determinism is essential
Because each replica computes its own state, any source of nondeterminism breaks the guarantee. Reading the wall clock, generating a random number, or depending on iteration order can make two replicas diverge even from the same log. Such inputs must be captured into the log rather than computed locally.
The hard part
The challenge reduces to agreeing on the order of commands in the log across nodes that can fail. This is exactly the consensus problem, solved by protocols like Paxos and Raft.
Key idea
State machine replication replicates an ordered command log to deterministic replicas, reducing fault tolerance to the problem of agreeing on log order.