# The Consensus Problem and State Machine Replication — Distributed Systems & Consensus (Raft / Paxos)

Source: https://www.skillbyai.com/en/distributed-consensus/dc-consensus-problem

> Define consensus by its safety and liveness properties and explain how a replicated log builds a fault-tolerant service.

## 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.

![Four stages: client command, consensus on a log position, replicated log on each node, and identical state machines.](assets/figures/distributed-consensus/section-4-map.svg) — Figure 4.1: client command -> consensus on log index -> replicated log -> identical state machines

## 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.

```python
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.

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

- [ ] Agreement
- [x] Validity
- [ ] Termination
- [ ] Linearizability

*Answer:* Validity. Validity requires the decided value to be one that some node proposed; a constant answer satisfies agreement and termination but not validity.