Consensus
Consensus is a distributed agreement problem in which processes decide an admissible value without conflicting decisions under stated failure and progress assumptions.
Agreement constrains conflicting decisions, validity constrains the chosen value, and termination requires progress under the model's assumptions. For basic Paxos, only a proposed value may be chosen; choice requires the specified acceptance quorum. Individual acceptance must not be confused with quorum choice. [1]
One instance chooses one value. Repeated instances can order a log for state-machine replication; crash-recovery implementations must retain the required protocol state before acknowledging it. [1]
FLP rules out guaranteed deterministic termination in every admissible fully asynchronous execution with one possible crash. It does not say practical consensus never finishes. [2]
Relations
- related
- State-machine replication, Raft, Paxos, FLP impossibility, Crash-recovery model, Safety property, Liveness property, Byzantine failure
Citations
- Leslie Lamport. Paxos Made Simple (2001), sections 2.1, 2.5 and 3.
- Fischer, Lynch and Paterson. Impossibility of Distributed Consensus with One Faulty Process. JACM 32(2), 374-382 (1985), sections 2-3; DOI 10.1145/3149.214121.
Sources & caveats
- Primary-source synthesis, not a new proof or an executed cluster experiment. The exact validity, agreement and progress requirements depend on the specified consensus model.