The Consensus Problem and State Machine Replication

Agreeing on one value

In the consensus problem, each node may propose a value and all correct nodes must decide one. Three properties define it. Agreement: no two correct nodes decide different values. Validity: the decided value was actually proposed by someone, so a trivial 'always decide 0' algorithm is ruled out. Termination: every correct node eventually decides. Agreement and validity are safety properties; termination is liveness. Deciding one value is not very useful by itself, so practical systems run consensus repeatedly to agree on a sequence of commands: a replicated log. This is state machine replication (SMR): if every replica starts in the same state and applies the same deterministic commands in the same order, every replica ends in the same state. Raft and Multi-Paxos are both SMR engines. The service on top (a key-value store, a lock service, a scheduler) just applies committed log entries.

State machine replication

A client command is proposed to the leader, consensus places it at a log index, every replica appends it, and each replica applies it to an identical state machine.

Same log, same state

Three replicas apply the same log and agree; applying the same commands in a different order gives a different state. Ordering is the whole game.

def apply(log):
    state = {}
    for op, key, val in log:
        if op == "set":
            state[key] = val
        elif op == "incr":
            state[key] = state.get(key, 0) + val
    return state

log = [("set", "x", 5), ("incr", "x", 2), ("set", "y", 1)]
replicas = [apply(log) for _ in range(3)]
print(replicas)
print("same order, same state:", all(r == replicas[0] for r in replicas))
print("different order       :", apply([log[1], log[0], log[2]]))

Output:

[{'x': 7, 'y': 1}, {'x': 7, 'y': 1}, {'x': 7, 'y': 1}]
same order, same state: True
different order       : {'x': 5, 'y': 1}

Determinism is your job

SMR only works if applying an entry is deterministic. Reading the local clock, a random number or iterating an unordered map inside apply makes replicas diverge. Generate such values on the leader and put them in the log entry.

Quick check: Which property rules out an algorithm that always decides the value 0 regardless of what was proposed?

• Agreement
• Validity
• Termination
• Linearizability