Replicated state machines under FLP

When several servers must agree on the same answer despite crashes and unreliable networks, the network itself forbids any deterministic program from being both always-correct AND always-making-progress — so Raft, like every real protocol, treats correctness as non-negotiable and treats progress as something the network has to earn.

Scene 01

Replicated state machines under FLP

Watch
Try it
Predict
Capture

What to watch for

Suppose you run a service that has to stay up even if one or two of its servers crash. You can't trust a single machine — machines die, disks fail, networks drop packets — so you keep several copies (servers) and you need all the surviving copies to give the client the same answer. The tricky part is that the network between them is not reliable: messages get delayed, reordered, or lost, and a server that has gone silent could be either crashed or just slow. The systems-design name for the picture you're about to watch is a replicated state machine — three identical copies of a deterministic program (one whose output depends only on its inputs, never on a clock or a random number), each fed the SAME list of commands in the SAME order. That list is called a log in the systems sense: an append-only, totally ordered sequence of commands. When the same deterministic program processes the same log, every copy must end up in the same state. Watch the three commands [SET x=1, SET x=2, INC x] apply on all three servers — they converge to x = 3.

Implementation

Highlighted lines are the ones running in the diagram right now.

Replica.applyLoop() — the replicated state machine model

every replica runs THIS loop; determinism + same log ⇒ same state

1# Each replica holds:
2#   log         — append-only, totally ordered commands
3#   stateMachine — DETERMINISTIC: (state, cmd) -> state'
4#   lastApplied — index of the last command fed to stateMachine
5 
6def applyLoop():
7    while True:
8        # block until log[lastApplied + 1] is committed
9        entry = waitForCommitted(log, lastApplied + 1)
10        stateMachine.apply(entry.command)
11        lastApplied += 1
12        # invariant: same log prefix, same lastApplied,
13        # same stateMachine state — on every replica.

Replica.onTimeout() — why FLP forbids a deterministic decision

a slow replica is indistinguishable from a crashed one

1# FLP (Fischer, Lynch, Paterson 1985):
2# no deterministic protocol can guarantee BOTH safety AND
3# liveness in a fully asynchronous network, even with one
4# crash failure. Below is the shape of WHY.
5 
6on receive heartbeat from leader:
7    reset election_timeout
8 
9on election_timeout fires:
10    # The protocol cannot distinguish:
11    #   leader is SLOW    (timeout was too aggressive — wait)
12    #   leader is CRASHED (timeout was correct — elect new)
13    # Any deterministic resolution in finite time can be
14    # made WRONG by an adversarial scheduler.
15    start_election()

Sources

Where this sits in Build Raft — consensus you can defend

Scene 01 of 12. Consensus on a replicated log lets N deterministic state machines converge — but FLP forbids any deterministic protocol from being both safe and live in a fully asynchronous network. Raft fixes safety as a theorem, concedes liveness to partial synchrony.

Up next. Now that you know correctness (safety) is the part Raft must guarantee no matter what the network does, the next scene asks: how can the servers even agree on the ORDER of commands when nobody trusts wall-clock time?

All 12 scenes in Build Raft — consensus you can defend · Every curriculum

Built with Arqly

Every scene in Build Raft — consensus you can defend builds on the one before it.All 12 Build Raft — consensus you can defend scenes