Replicated State Machines

A replicated state machine (RSM) is the common core beneath Raft databases, PBFT services, and blockchains. Each replica starts from the same state, applies the same deterministic commands in the same order, and therefore reaches the same result. Consensus does not replicate arbitrary memory: it establishes that order.

The contract #

Let state $S_i$ and command $c_i$ feed a deterministic transition function:

$$(S_{i+1}, r_i) = \delta(S_i, c_i).$$

If every correct replica starts with $S_0$ and applies the identical sequence $c_0,c_1,\ldots$, induction gives identical state and replies after every index. The architecture therefore separates two jobs:

flowchart LR
  C["Clients"] --> O["Ordering protocol<br/>consensus / atomic broadcast"]
  O --> L1["Replica A log"]
  O --> L2["Replica B log"]
  O --> L3["Replica C log"]
  L1 --> E1["deterministic δ"]
  L2 --> E2["deterministic δ"]
  L3 --> E3["deterministic δ"]

• The ordering layer agrees on one log prefix despite failures.
• The application layer validates and executes each decided command.

This is why consensus safety can hold while an application is still wrong. If all replicas deterministically debit the wrong account, replication faithfully reproduces the bug.

Safety, liveness, and validity #

Safety says correct replicas never decide conflicting commands for one log position. Liveness says submitted valid commands eventually become decided. A partitioned system can preserve safety by refusing progress; it cannot promise both properties without timing or failure assumptions.

Validity is separate again: the application decides whether a command is legal. In a blockchain, a block may have the necessary votes yet still be rejected because a transaction has an invalid signature, spends a missing UTXO, or produces an invalid state root. Nodes must validate before voting or committing.

Determinism is an engineering requirement #

Replicas diverge if application code reads local time, generates an unrecorded random number, depends on map iteration order, calls an external API, observes a different filesystem, or evaluates floating-point code differently. Safe designs either forbid such inputs or put their agreed values into the command log.

Replies also need deduplication. A client may retry after losing a response even though the command committed. Give each request a stable client ID and sequence number, and cache the result; otherwise an exactly-once-looking API executes a payment twice.

Snapshots and recovery #

The log grows forever unless replicas checkpoint a state plus the exact committed index it represents. A recovering replica installs a verified snapshot, then replays later committed entries. The snapshot is part of the safety boundary: pairing state from index 10,000 with metadata claiming 11,000 silently skips 1,000 transitions.