computer science//distributed systems//state machine replication

State machine replication is the technique of making several servers behave as one fault-tolerant server by having each start from the same state and apply the same deterministic commands in the same order, so that all of them compute the same result. It is how a fleet's database of orders, tasks and maps survives the loss of a machine: three replicas hold the same ordered log of commands, and any of them can take over.

State machine replication is the technique of making several servers behave as one fault-tolerant server by having each start from the same state and apply the same deterministic commands in the same order, so that all of them compute the same result. It is how a fleet's database of orders, tasks and maps survives the loss of a machine: three replicas hold the same ordered log of commands, and any of them can take over.

The idea rests on determinism. A state machine that receives the same sequence of inputs always ends in the same state, so the whole problem reduces to agreeing on the sequence. Each slot of the log is one instance of distributed consensus (entry 812: assign order 4512 to robot 17). Once a majority of replicas has accepted an entry it is committed, every replica applies it in order, and a replica that was down replays the entries it missed until it is current.

Replicate the commands, and make every command deterministic.

A command that reads the local clock, draws a random number or depends on a hash map's iteration order computes different states on different replicas, and the replicas drift apart silently while their logs stay identical.

Raft is state machine replication packaged: leader election, log replication and the rule that only committed entries are applied. etcd, ZooKeeper and the metadata layers of many databases are built this way.

The log grows forever unless it is compacted. Replicas periodically save a snapshot of the state and discard the entries before it, and a new replica starts from the latest snapshot.

Reads need care. Reading a follower's local copy is fast but may be stale; a read that must see the latest write goes through the leader or through the log, which is the consistency side of the CAP theorem showing up on every request.

It sits at the opposite end from the consensus protocol of a drone fleet, where agents converge gradually to an average and no exact shared history exists.