State Machine Replication — Fundamentals

Corresponds to the State Machine Replication section. See replicated-data-management-and-consistency for linearizability itself (the consistency guarantee SMR is meant to provide); this note covers how to actually build a linearizable replicated service out of a consensus protocol. Defines SMR and the levels of fault tolerance a particular construction can offer, the ideal SMR model as the specification every real protocol is trying to match, and the generic transformation from a single-shot consensus primitive (agree once) to full SMR (agree on an ever-growing, ordered log). Works through a simple crash-fault-tolerant SMR first, then omission failures — single-shot, and then the full multi-shot case via the lock-commit paradigm (locking in a decision before committing it, to survive omitted messages mid-protocol). Closes with the practical point that an SMR system’s real-world throughput and latency depend as much on its data layer and execution layer as on the consensus core itself, illustrated with a simple payment system.

Outline (TODO — flesh out each)

• Defining state machine replication (SMR)
• Levels of SMR fault tolerance
• The ideal state machine model (and linearizability, recap)
• From single-shot consensus to SMR
• A simple SMR for crash failures
• Extending SMR to omission failures — single-shot
• The lock-commit paradigm for multi-shot omission-tolerant SMR
• Beyond consensus: data and execution layer performance
• A simple payment system