State-machine replication
State-machine replication maintains a service across replicas that start from a common state and apply deterministic transitions to the same ordered inputs.
Agreement on inputs does not make arbitrary code deterministic. Local clock readings, random choices and external input must be coordinated or supplied as agreed input. Matching state is expected at the same applied prefix, not at every instant. [1]
A committed log entry can await local application. A log-free linearizable read needs current authority and sufficient application progress; a replicated log alone also does not suppress repeated client commands. [2]
The abbreviation SMR also denotes shingled magnetic recording; this record uses the full name to avoid confusing replication with disk recording.
Relations
Citations
- Schneider. Implementing Fault-Tolerant Services Using the State Machine Approach: A Tutorial (1990), sections 1, 3 and 7.2; DOI 10.1145/98163.98167.
- Ongaro and Ousterhout. In Search of an Understandable Consensus Algorithm, extended version (20 May 2014), sections 2 and 8.
Sources & caveats
- Synthesis of the deterministic state-machine approach and Raft's client protocol. No cluster benchmark, recovery test or universal fault threshold is claimed.