Consensus lets distributed processes agree on a value or ordered sequence of operations, allowing redundant components to act as one despite failures. section 10.0 section 10.1
The system model contains processes that propose values and may crash while communicating through a network that can delay, lose, duplicate, or reorder messages. section 10.1 section 10.2
A consensus algorithm must provide four properties:
- Validity: every decided value was proposed by some process. section 10.2
- Integrity: a process does not change its decision. section 10.2
- Agreement: correct processes do not decide different values. section 10.2
- Termination: every nonfailed process eventually decides. section 10.2
Replicated key-value store
Consensus orders commands in a replicated log. Identical deterministic replicas receiving the same commands in the same order reach the same state, so the store can compensate for a crashed node. section 10.3
A single leader works only in an ideal failure-free system. Practical protocols combine leadership with quorums; Raft uses a leader to sequence entries and a quorum to commit them. section 10.5.1 section 10.5 section 10.6
Safety can be guaranteed while liveness remains conditional. FLP shows that asynchronous systems without clocks cannot guarantee consensus under every circumstance when even one node may fail. section 10.1
Table 10.1 Symbols in set theory
| Symbol |
Meaning |
| ∀ |
For all |
| ∃ |
There exists |
Formal symbols clarify the quantifiers used in consensus properties. section 10.2
