Consensus asks non-faulty processes to decide one value despite failures and delay. The properties are easy to state: agreement, validity, and termination. Achieving all three depends on the system model.
In a fully asynchronous system, delay and crash are indistinguishable. FLP shows that deterministic consensus cannot guarantee termination with even one possible crash, although safety can still hold and practical systems can make progress under favorable timing.
Paxos roles and two phases
- Proposer: suggests a value with a numbered ballot.
- Acceptor: promises and votes.
- Learner: discovers the chosen value.
Phase 1 asks a majority of acceptors to promise not to accept lower ballots and report prior accepted values. Phase 2 proposes the highest-ballot value already reported, or a new value if none exists, then asks a majority to accept.
prepare(n) ──> majority promises
accept(n, v) ──> majority accepts
v is chosenWhy majority intersection matters
Any two majorities overlap. If a value was chosen by one majority, a later proposer contacting another majority must encounter at least one acceptor carrying evidence of it. Choosing the highest accepted ballot preserves that value.
In plain terms: a new committee cannot avoid every member who witnessed the old decision.
Multiple competing proposers can prevent progress even while safety holds. Stable-leader Multi-Paxos amortizes the prepare phase for a sequence of log entries.
Review card
- Consensus separates agreement/validity from termination.
- Asynchrony makes failure indistinguishable from delay.
- Paxos ballots order competing rounds.
- A majority acceptance chooses a value.
- Quorum intersection carries prior decisions forward.
- Stable leadership improves liveness and performance, not safety fundamentals.