Crash-Fault Quorum Protocol¶
Protocol — instantiates Fault-Tolerant Distributed Consensus
Decides one safe value among participants that may crash and recover but never lie, using intersecting majority quorums and durable votes.
A Crash-Fault Quorum Protocol is the agreement family for the benign failure world: participants may become slow, unreachable, crash, and later recover, but while running they always follow the rules — they never send a message they know to be false. Under that assumption the protocol earns safety with two simple ingredients. First, intersecting quorums: any set of votes large enough to decide must share at least one voter with any other such set, so two conflicting decisions cannot both gather support. With a fixed membership a simple majority already guarantees that overlap. Second, durable votes: before a participant acknowledges a promise or an acceptance, it writes it to stable storage, so a crash-and-recover cannot make it "forget" a vote and support something incompatible. The protocol's defining discipline is that elapsed time and silence never authorize a decision — only a durable, intersecting quorum does.
Example¶
A container platform keeps a five-node metadata store holding the authoritative record of which node currently owns each storage shard. Nodes reboot for patching, occasionally crash, and sometimes fall behind the network, but none is compromised. To record "node 7 now owns shard 12," a coordinator runs the protocol: it advances to a fresh ballot, contacts a preparation quorum of three nodes, and asks what each has already accepted so it can carry forward any value that might already have been chosen rather than inventing a new one. Finding none in conflict, it proposes the ownership change and collects an acceptance quorum of three nodes — each of which writes the acceptance to disk before replying. Three durable acceptances out of five intersect any other three, so no rival coordinator can commit a different owner for shard 12. When two of the five nodes are down, the remaining three still form a quorum and writes proceed; when a third goes down, the store stops accepting writes rather than let a minority decide — it keeps serving the last certified state until a quorum returns. The reboot of any single node loses nothing, because its promises were on disk before it ever acknowledged them.
How it works¶
- Fix the model first. Declare the crash-recovery fault bound and the membership epoch before any vote is counted; the quorum sizes are derived from that bound.
- Preparation phase. A coordinator claims a monotonic ballot and gathers a quorum's prior-accepted evidence, so it must adopt the highest safe value already in play.
- Acceptance phase. It proposes the safe value and collects an acceptance quorum, each vote persisted to stable storage before acknowledgment.
- Persist, then commit. Only a durable, intersecting acceptance quorum authorizes the decision; the coordinator assembles the result and notifies learners.
- Retry under a higher ballot when progress stalls — never inferring from a timeout that a conflicting value cannot exist.
Tuning parameters¶
- Replica count — how many voters, hence how many simultaneous crashes tolerated. More replicas survive more outages but add a durable write and a round-trip to every decision.
- Quorum shape — simple majority versus flexible phase quorums (a smaller acceptance quorum paired with a larger preparation quorum). Flexible quorums optimize the common path but make the intersection argument harder to reason about.
- Durability point — exactly which records must hit stable storage before acknowledgment. Fsync-before-ack is safest; buffering is faster but risks the forgotten-vote failure.
- Ballot/retry timing — how aggressively a stalled coordinator escalates. Fast escalation reacts to failure quickly but invites dueling coordinators under load.
When it helps, and when it misleads¶
Its strength is deterministic safety within the crash model with well-understood majority geometry and an efficient steady state once a stable coordinator is in place — the reasoning made rigorous by the Paxos family of protocols.[n1] It is the right tool when failures are honest and you need a value that survives reboots.
Its defining limitation is that it tolerates no equivocation whatsoever: one participant that sends conflicting messages can break it, because the majority-intersection argument assumes the shared voter tells both sides the same thing. The classic misuse is advertising Byzantine tolerance it does not have, or acknowledging before persistence so a crash resurrects a forgotten vote. The guarding discipline is to fault-inject crashes precisely around the durability boundary and to state the fault model honestly; and because no purely asynchronous protocol can guarantee it always terminates[1], to pair it with an explicit progress assumption rather than promise unconditional availability.
How it implements the components¶
fault_and_network_model— it declares the crash-recovery bound and timing assumptions from which its quorum sizes are derived.quorum_and_intersection_policy— it realizes the majority intersection that guarantees any two decisive sets share a voter, so conflicting certificates cannot both form.durable_decision_evidence_log— it persists promises and acceptances to stable storage before acknowledgment, defeating the forgotten-vote failure.protocol_phase_and_message_state— it drives the monotonic prepare/accept ballot machine that constrains every future vote.
It does not implement cryptographic_identity_and_vote_proof or the proposal_validity_rule — those belong to Byzantine-Fault Quorum Protocol, its nearest twin. The one sentence that separates them: this protocol assumes participants may crash but never lie, so durable majority votes are enough, whereas the Byzantine twin assumes they may send conflicting signed messages and therefore must authenticate every vote and validate every proposal.
Related¶
- Instantiates: Fault-Tolerant Distributed Consensus — the crash-fault implementation family.
- Sibling mechanisms: Byzantine-Fault Quorum Protocol · Leader Election and Term Protocol · Replicated Log Consensus Engine · Authenticated Vote Certificate · Failure Detector and Heartbeat Service
Editorial Notes¶
Form Classification¶
Form family: Decision, Gate & Allocation
Rationale: Intersecting durable preparation and acceptance quorums select one safe value despite crash-recovery failures, so the mechanism's defining output is a bounded consensus decision.
Nearest alternative: Control, Automation & Runtime — Ballots, retries, and persistent votes execute automatically, but they exist to choose and commit one value rather than continuously regulate an operating variable.
Review outcome: Adjudicated after independent review; high confidence.
Origin Attribution¶
Primary origin: Computer Science & Software Engineering
Origin pattern: Single lineage
Present-day reach: Specialized
Rationale: Distributed-computing research cohered crash-fault consensus through intersecting quorums and durably recorded votes under benign process failure.
Related originating lineages:
- Mathematics — Set intersection and impossibility results supply the formal safety and liveness bounds of quorum protocols.
Review resolution: Crash-fault quorum protocols are a specialized distributed-computing lineage; quorum-intersection mathematics is foundational but not an independent applied origin.
Review outcome: Reconciled after independent review; high confidence.
Notes¶
[n1] The Paxos family (Leslie Lamport) is the canonical crash-fault agreement approach: a two-phase ballot in which a coordinator adopts the highest previously accepted value and commits only on an intersecting acceptance quorum — the reasoning this mechanism generalizes. ↩
References¶
[1] The FLP impossibility result (Fischer, Lynch & Paterson, 1985) proves that no deterministic protocol can guarantee both safety and termination in a fully asynchronous system with even one crash fault; this is why crash-fault consensus makes safety unconditional but termination conditional on a stated progress assumption. withdrawn registry ↩