Consensus is the problem of getting several machines to agree on one value, or one sequence of values, even when some crash and messages go astray. It sits under replicated databases, lock services and configuration stores: whenever many nodes must act as one, something runs a consensus protocol.
Key concepts
- Safety and liveness: nothing wrong is ever decided, and something is eventually decided; protocols guarantee the first always and the second only under good conditions.
- FLP impossibility: in a fully asynchronous system, no deterministic protocol can guarantee agreement if even one node may crash.
- Leader election and terms: Paxos and Raft pick a leader for a numbered term, and a higher term replaces a stale leader.
- Replicated log: the nodes agree on an ordered log of commands and apply it in the same order, forming a replicated state machine.
- Failure models: crash faults need a majority of nodes; Byzantine faults, where nodes lie, need more than two thirds honest.
Vocabulary
- Quorum: a majority whose overlap guarantees two decisions cannot conflict.
- Term or ballot: a number that orders leaders in time.
- Commit: the point after which an entry can never be lost.
- Replicated state machine: identical copies of a deterministic program fed the same log.
- Byzantine fault: a node that behaves arbitrarily, including maliciously.
What to study, in order
- Distributed-systems basics: asynchrony, crash faults, quorums.
- Read the Raft paper, which was written to be understood, and follow its figures with a pencil.
- Implement leader election, then log replication, then test with a simulator that drops and delays messages.
- Read about Paxos and compare it with Raft: where do they differ, and why?
- Learn what Byzantine fault tolerance costs, and when it is worth it.
Related tags
#distributed-systems #blockchain #formal-methods #concurrency