State Machine Replication

The most critical prerequisite for SMR. Each replica must be a deterministic state machine, meaning that given the same initial state and the same sequence of inputs (commands), it will always produce the exact same outputs and undergo the same state transitions. This property enables identical replay across all replicas, guaranteeing consistency. Non-deterministic operations (e.g., using system time or random numbers) must be carefully managed or eliminated.

The mechanism that ensures all non-faulty replicas agree on the total order of commands before execution. This solves the problem of coordinating multiple independent processes in an unreliable network. Key protocols include:

• Paxos: The seminal algorithm for achieving consensus.
• Raft: Designed for understandability, it manages leader election and log replication.
• Practical Byzantine Fault Tolerance (PBFT): Tolerates arbitrary (Byzantine) failures. These protocols ensure that even if some replicas fail or messages are delayed, the system maintains a single, agreed-upon command sequence.

The source of truth in an SMR system. It is an append-only, totally ordered sequence of commands that all replicas agree upon via the consensus protocol. Each replica maintains its own local copy of this log. The execution process is straightforward: replicate the log, then execute it. Once a command is committed to the log (i.e., agreed upon by a quorum), it is applied to the local state machine in log order. This decouples agreement from execution, simplifying recovery.

SMR systems are designed to tolerate specific types of failures, defined by a fault model. The two primary models are:

• Crash Fault Tolerance (CFT): Assumes replicas fail only by stopping (crashing). Protocols like Raft and Paxos are CFT. They typically require a majority (quorum) of replicas to be alive to make progress.
• Byzantine Fault Tolerance (BFT): Assumes replicas can fail arbitrarily, including acting maliciously. Protocols like PBFT are more complex and require more replicas (e.g., 3f+1 to tolerate f faulty nodes) to ensure safety. The choice of model dictates the protocol, overhead, and number of required replicas.

Clients interact with the replicated service by sending commands. To provide a linearizable (strongly consistent) interface, the system must ensure each command appears to take effect atomically at a single point in time between its invocation and response. Typically, a client sends a command to the current leader replica. The leader sequences it into the log, replicates it, and upon commitment, executes it and returns the result. If the leader fails, a new leader is elected, and clients may need to retry requests, often using idempotent command identifiers.

Mechanisms for bringing a new or failed replica up to date with the current system state. Two primary methods are:

• Log-Based Recovery: The new replica replays the entire committed command log from the beginning or from a recent snapshot. This is simple but can be slow for long-running systems.
• Snapshot-Based Recovery: Periodically, a replica takes a checkpoint (snapshot) of its application state. A new replica first installs the latest snapshot and then only replays the log entries that occurred after that snapshot was taken. This dramatically speeds up recovery time and is essential for production systems.

A property of a system or function where, given the same initial state and sequence of inputs, it will always produce the exact same outputs and state transitions. This is the absolute prerequisite for State Machine Replication. If replicas are non-deterministic (e.g., using random numbers or system timestamps differently), applying the same log of commands will lead to divergent states, breaking the replication guarantee. SMR requires all business logic to be purely deterministic.

A distributed algorithm by which nodes in a cluster select a single node to act as the coordinator or leader. In most SMR implementations (like those using Raft), a leader is elected to be the sole authority for accepting client commands and appending them to the replicated log. This simplifies the consensus process. Other replicas (followers) simply accept and apply the leader's log entries. If the leader fails, a new election is held.

The characteristic of a distributed system that can reach consensus correctly even when some components fail arbitrarily (maliciously or randomly). Standard SMR typically assumes Crash Fault Tolerance (CFT), where nodes fail by stopping. BFT SMR is a more robust variant designed to withstand Byzantine (arbitrary) failures, where nodes may send conflicting or incorrect messages. This requires more complex protocols (like PBFT) but is essential for adversarial environments like some blockchains.

An architectural pattern where the state of an application is determined by a sequence of immutable events, which are stored as the system of record. SMR and Event Sourcing are highly synergistic patterns. The replicated, totally-ordered command log in SMR is effectively an event store. The state machine is the event-sourced aggregate that applies these events. This combination provides a fault-tolerant, replayable audit trail of all state changes, enabling temporal debugging and state reconstruction.

The process of periodically saving the complete state of a system or application to stable storage. In long-running SMR systems, the log of commands can grow indefinitely. Checkpointing is used to take a snapshot of the state machine's current state at a specific log index. This allows older log entries to be safely garbage-collected. During recovery, a replica can load the latest checkpoint and then replay only the log entries that occurred after it, significantly speeding up recovery times.