State Machine Replication

The core assumption of SMR is that the service is modeled as a deterministic state machine. This means that given an identical starting state and an identical sequence of inputs (commands), every correct replica will transition through the same sequence of states and produce the same outputs. Non-determinism, such as reliance on local timestamps or random numbers, must be eliminated or carefully managed to ensure replica consistency.

The primary technical challenge SMR solves is ensuring all replicas process commands in the same total order. This is achieved using an Atomic Broadcast or Total Order Broadcast protocol. These protocols guarantee two properties:

• Agreement: If a correct replica delivers a message, all correct replicas eventually deliver that message.
• Total Order: All correct replicas deliver messages in the same sequential order. Protocols like Paxos and Raft implement this to sequence client requests into a replicated log.

SMR implementations maintain a replicated log as the single source of truth. Each log entry contains a client command. The consensus protocol (e.g., Raft) is responsible for appending commands to this log across a majority of nodes. Once a command is committed to the log (i.e., durable on a quorum), it is applied in log order to the local state machine of each replica. This log provides durability and is used for recovery after a crash.

SMR achieves fault tolerance by replicating the state machine across multiple nodes (typically an odd number, like 3 or 5). Operations require a quorum (usually a majority) of nodes to agree. This allows the system to tolerate f failures out of 2f + 1 total nodes. For example, a 5-node cluster can tolerate 2 simultaneous failures. The system remains available and consistent as long as a majority of replicas are operational and can communicate.

A correct SMR service typically provides linearizable semantics to clients. This strong consistency guarantee means each operation appears to take effect instantaneously at a single point between its invocation and response. Clients send commands to the current leader replica (in leader-based protocols like Raft). The leader sequences the command, replicates it, and upon commitment, applies it and returns the result to the client. Clients may retry with unique identifiers to handle leader failover.

To manage long-running logs and integrate new replicas, SMR systems use snapshotting and state transfer. Periodically, a replica will capture a complete snapshot of its application state (e.g., a database checkpoint) and truncate its log up to that point. A new or lagging replica can then fetch a recent snapshot from another node and apply only the log entries that occurred after the snapshot was taken, catching up efficiently without replaying the entire history.

A distributed algorithm that enables a group of processes or agents to agree on a single data value or sequence of actions despite the possibility of failures. State Machine Replication fundamentally depends on a consensus algorithm to establish the total order of commands that all replicas must execute. Popular algorithms include:

• Paxos: A family of protocols providing fault-tolerant consensus.
• Raft: Designed for understandability, it manages a replicated log and leader election.
• Practical Byzantine Fault Tolerance (PBFT): Tolerates arbitrary (Byzantine) failures.

A communication primitive that guarantees all correct processes in a distributed system deliver the same set of messages in the same total order. This is the communication layer abstraction directly implemented by SMR. Once a consensus algorithm orders commands, atomic broadcast ensures every replica receives them identically. It provides two guarantees:

• Total Order: If two replicas deliver messages A and B, they do so in the same order.
• Agreement: If a correct replica delivers a message, all correct replicas eventually deliver that message.

A strong consistency model that guarantees operations appear to take effect instantaneously at some point between their invocation and response, preserving the real-time ordering of operations. A correctly implemented State Machine Replication service provides linearizability to its clients. When a client receives a response, it is guaranteed that all subsequent reads (from any replica) will reflect that write and that the order of operations respects their real-time precedence. This is stronger than eventual consistency and is the gold standard for distributed system semantics.

The property of a distributed system to resist Byzantine faults, where components may fail in arbitrary ways, including sending conflicting or malicious information to different parts of the system. SMR can be extended to be Byzantine Fault Tolerant (BFT-SMR). This requires more sophisticated protocols (like PBFT) that can tolerate replicas that are not just crashed but actively adversarial. BFT-SMR is critical for blockchain networks and high-security environments where any node could be compromised.

A simpler replication model where a single primary replica processes all client requests and synchronously or asynchronously propagates state updates to one or more backup replicas. Contrast with SMR: In Primary-Backup, only the primary executes the state machine; backups are passive. SMR is active replication where all replicas execute commands. Primary-Backup has a single point of execution (the primary) and requires failover protocols, while SMR replicas are symmetric and process commands concurrently.

A durability mechanism where any modification to data is first recorded in a persistent log before the actual data structures are updated. WAL is the standard persistence layer for SMR replicas. The sequence of agreed-upon commands from the consensus layer is appended to a local WAL. The replica then applies these logged commands to its local state machine. This ensures recoverability after a crash, as the replica can replay the log to reconstruct its last known state.