A replicated state machine maintains identical system state by having nodes execute the same ordered sequence of commands. A client request is accepted by a replicated cluster, and acknowledgment means its effect remains persistent despite specified component failures. section 4.6
The model supports fault-tolerant systems and replication in data infrastructure, including distributed SQL databases and key–value stores. Once a request is acknowledged, later requests sent to any cluster node are guaranteed to observe its update, providing linearizability. section 4.6
Design reasoning centers on failure type and quorum size:
- Distinguish non-Byzantine failures, such as crashes, outages, partitions, and disk failures, from Byzantine failures involving arbitrary or conflicting behavior. section 4.6
- For non-Byzantine failures, tolerate f failures with 2f + 1 replicas; three replicas tolerate one failure, while five tolerate two. section 4.6
- Treat replication as a consistency, availability, and latency trade-off: stronger consistency generally requires more coordination and higher latency. section 4.0
