State Machine Replication

The core requirement for SMR is that each replica must be a deterministic state machine. This means that given an identical starting state and an identical sequence of inputs, every replica will produce the same sequence of state transitions and outputs. Non-deterministic operations (e.g., random number generation, system time calls) must be carefully controlled or made deterministic via the replicated log.

All client requests (commands) are appended to a replicated log, which serves as the single, authoritative sequence of inputs. A consensus protocol (like Raft or Paxos) is used to ensure all correct replicas agree on the exact order of entries in this log before they are applied. This log is the mechanism that coordinates the replicas, making the system appear as a single, highly available state machine.

Replicas do not execute commands as they are received. Instead, they wait for the consensus protocol to order the command within the replicated log. Once a command is committed at a specific log index, every replica must execute it in that exact position in the sequence. This total order broadcast guarantee is what prevents state divergence, even under concurrent client requests and network delays.

SMR typically assumes a crash-fault or Byzantine-fault model. To tolerate f faulty replicas, the system requires a minimum number of total replicas N.

• Crash Fault Tolerance: Requires N = 2f + 1. The system can progress as long as a majority (f + 1) are alive.
• Byzantine Fault Tolerance (BFT): Requires N = 3f + 1 to tolerate f malicious replicas, as consensus must be reached despite arbitrary (including malicious) behavior from faulty nodes.

A correct SMR implementation provides linearizable semantics to clients. From the client's perspective, the system behaves like a single, highly available server. Clients send commands to any replica (often a leader). The system ensures that once a response is received for a write operation, all subsequent reads (from any replica) will reflect that write. This strong consistency is a key guarantee of classical SMR.

Since the replicated log grows indefinitely, practical SMR systems implement log compaction. Periodically, a replica takes a full snapshot (checkpoint) of its current state. Log entries prior to the snapshot can be safely discarded, as the snapshot plus the tail of the log is sufficient for recovery. This is critical for long-running systems to manage storage overhead. New replicas can bootstrap by loading a recent snapshot and then replaying the subsequent log entries.

A consensus protocol is the underlying distributed algorithm that enables a group of independent nodes to agree on the total order of client requests, which is the fundamental prerequisite for State Machine Replication. Without consensus, replicas could process commands in different sequences, leading to divergent states.

• Purpose: Guarantees all non-faulty replicas execute the same commands in the same order.
• Examples: Paxos, Raft, and Viewstamped Replication are classic protocols used in SMR systems.
• Relation to SMR: The consensus protocol manages the replicated log; SMR defines how each replica deterministically applies the log entries to its local state machine.

Byzantine Fault Tolerance is a stronger resilience property where a system must reach consensus and operate correctly even when some components fail in arbitrary, malicious ways (e.g., sending conflicting messages). Standard SMR typically assumes crash-fault tolerance, where nodes fail by stopping.

• Key Difference: BFT-SMR protocols must withstand active adversaries within the replica set, not just silent crashes.
• Requirement: Requires more replicas (e.g., 3f+1 to tolerate f Byzantine faults vs. 2f+1 for crash faults).
• Use Case: Critical for blockchain networks (e.g., Tendermint Core) and high-security financial or defense systems where hardware or software may be compromised.

Active-Passive Replication (or Primary-Backup) is a high-availability pattern where a single primary (active) replica handles all client requests and synchronizes its state to one or more secondary (passive) replicas. If the primary fails, a secondary is promoted.

• Contrast with SMR: In SMR, all replicas are typically active, processing the same command sequence concurrently. Active-Passive uses a state transfer model rather than a log replication model.
• Advantage: Simpler client interaction (talk only to primary).
• Disadvantage: Resource inefficiency (backups idle) and a failover delay during primary promotion.

The Saga pattern is a failure management pattern for long-lived, distributed transactions spanning multiple services or agents. Instead of a blocking atomic commit (like 2PC), it uses a sequence of local transactions, each with a compensating transaction to undo its effects if the saga fails.

• Relation to SMR: While SMR ensures each individual replica is consistent, the Saga pattern ensures business process consistency across different state machines (agents).
• Mechanism: If a step in a saga fails, previously completed steps are rolled back by executing their defined compensating actions in reverse order.
• Use Case: Essential in microservices and multi-agent systems for managing bookings, orders, or workflows where locking resources for long periods is impractical.

Conflict-Free Replicated Data Types are data structures (like counters, sets, maps) designed for coordination-free eventual consistency. Multiple replicas can apply updates concurrently, and the data type's merge function guarantees convergence to the same state.

• Contrast with SMR: SMR requires strong consistency via total order broadcast. CRDTs embrace eventual consistency and are AP in the CAP theorem.
• Advantage: Enables high availability and low latency for collaborative applications (e.g., real-time document editing, shopping cart counters) even during network partitions.
• Trade-off: Requires data types to be designed with commutative, associative, and idempotent operations, which is not possible for all state machines.

A quorum is the minimum number of replicas in a distributed system that must participate in an operation (like a read or write) for it to be considered valid. It is a fundamental mechanism for ensuring fault tolerance and consistency in systems like SMR.

• In SMR/Consensus: A write quorum is needed to agree on and commit a log entry (e.g., a majority of nodes). A read quorum may be used to ensure a client reads the most recent committed value.
• Rule of Thumb: For a system of N replicas tolerating f crash failures, a majority quorum is (N/2 + 1). This ensures any two quorums intersect, preventing split-brain scenarios.
• Variations: Read-write quorums can be tuned (e.g., in Dynamo-style systems) to trade off consistency for latency or availability.