State machine replication

State machine replication is the foundational principle that makes distributed consensus useful. The idea is simple: if multiple deterministic state machines begin in the same initial state, and if they process the same sequence of commands in the same order, then they will reach the same final state. A consensus protocol such as Raft or Paxos is merely the mechanism that guarantees the shared command sequence — the replicated log.

The determinism requirement is the hidden constraint. A state machine that depends on local clocks, random number generators, or unobservable side effects cannot be replicated this way. This is why distributed databases typically separate the consensus layer — which replicates the log — from the execution layer, which applies log entries to a deterministic state machine. The separation is not architectural elegance; it is a requirement imposed by the mathematics of replication.

The deeper insight is that state machine replication transforms a distributed system into a single logical entity. The nodes are many, but the machine is one. This is not a metaphor. It is the operational definition of what it means for a distributed system to be correct.