State Machine Replication (SMR)

Once consensus proposes a command for a specific log position, it undergoes a replication phase:

• A leader (or primary) replica broadcasts the command to followers (or backups).
• Followers acknowledge receipt, and once a quorum of acknowledgments is received, the leader commits the entry.
• The leader then informs all replicas of the commitment. This process ensures the log is durable and consistent across a majority of nodes before the command is executed, preventing state divergence.

To handle replica failures and recovery, SMR systems implement state transfer mechanisms:

• A new or recovering replica must synchronize its state with the operational group.
• This can be done via:
  • Log shipping: Transmitting the entire committed command log for replay.
  • Snapshot transfer: Sending a periodic, compacted snapshot of the application state, followed by replaying subsequent logs.
• This mechanism is critical for maintaining availability and allowing the system to tolerate the temporary loss of replicas.

Clients interact with an SMR system expecting linearizable semantics. The typical protocol is:

1. Client sends a request to the current leader.
2. The request is sequenced into the log via consensus.
3. All replicas execute the request deterministically, producing a result.
4. The leader (or any replica that executed it) sends the result back to the client.

• To ensure linearizability, clients often include a unique sequence number and may retry requests, relying on the system's idempotency or duplicate detection to prevent double-execution.

In leader-based consensus protocols (e.g., Paxos, Raft, PBFT), a view change or leader election sub-protocol is essential for liveness:

• If the current leader fails or becomes partitioned, replicas must democratically elect a new leader.
• The protocol must ensure safety is preserved during the transition; the new leader must possess all committed log entries.
• This mechanism transforms a collection of replicas into an active-passive or multi-primary system that can withstand coordinator failure.

Byzantine Fault Tolerance (BFT) is a property of a distributed system that allows it to reach consensus and continue operating correctly even when some components fail arbitrarily, including through malicious or adversarial behavior. Standard SMR assumes crash-fault tolerance (nodes stop). BFT protocols, like Practical Byzantine Fault Tolerance (PBFT), are required for SMR in adversarial environments (e.g., blockchains, military systems). They require more complex communication patterns (often three-phase) and can tolerate up to f faulty nodes out of 3f+1 total.

Atomic Broadcast is a communication primitive that guarantees all correct processes in a system deliver the same set of messages in the same total order. This is formally equivalent to solving consensus. In SMR, the sequence of commands to be executed by the state machine is disseminated via an atomic broadcast protocol. Once a command is atomically broadcast and delivered, every replica applies it deterministically, ensuring state consistency. It is the communication layer upon which SMR is built.

Linearizability is the strongest consistency model for concurrent systems. For a replicated service using SMR, linearizability guarantees that operations appear to take effect instantaneously at a single point in time between their invocation and response, and that this total order respects the real-time ordering of operations across all clients. A correctly implemented SMR service provides linearizable semantics to its clients, making the distributed system behave like a single, non-replicated machine. It is a key correctness criterion for systems like distributed databases.

Two-Phase Commit (2PC) is a distributed algorithm that coordinates all participants in a transaction to ensure atomicity—either all commit or all abort. While not a consensus algorithm for SMR itself, it is a critical related protocol for ensuring consistency across multiple, distinct state machines or resources (e.g., databases). It involves a coordinator that drives the process through a prepare/vote phase and a commit/abort phase. Its blocking nature under coordinator failure contrasts with the fault-tolerant, leader-failover mechanisms in consensus-driven SMR.