A reachable majority is a probability event, not a correctness proof
Calculate independent quorum-availability tails, include shared failure scenarios, and separate replica count from communication, durability, and protocol safety.
On this page
The question for today
What you’ll understand
- Calculate a majority threshold and an independent unavailability tail.
- Explain why correlated replica failures invalidate a simple binomial product.
- Separate quorum reachability from consistency and durable protocol behavior.
A replicated service may require enough participating replicas before it can serve an operation. Counting that threshold is straightforward; proving the service behaves correctly is a separate task. A probability model can estimate how often a quorum is unavailable under stated failure assumptions, but it does not establish elections, durable logs, fencing, or client-visible consistency. Keep the availability event narrow enough that the arithmetic actually supports the claim.
Translate the threshold into a failure-count event
For n replicas with a strict-majority threshold q=floor(n/2)+1, a quorum exists when at least q are available and mutually usable for the operation. In a simple count model, if K are unavailable, failure occurs when K exceeds n−q. Define unavailable carefully: a running process isolated from the leader may be unusable, while two separately observed healthy counts may not represent one communicating quorum. The model's observation point matters. Count failures for the same request or time horizon rather than mixing long-run node availability with a different operation's communication requirement.
If each replica is independently unavailable with the same probability p, K has a binomial distribution. Sum its upper tail from n−q+1 through n. This uses mutual independence and identical marginal probabilities; neither follows from replicas being on different machines. Different probabilities require a different calculation even under independence. Shared networks, common deployments, correlated repair, and load redistribution can all change the tail. A small numerical result is meaningful only if the model captures the mechanisms that can remove several required participants together.
A common-cause floor survives larger replica counts
A conditional mixture can add an environment that disables every replica with probability c, while normal-condition failures follow a binomial model with probability p0. Total no-quorum probability is c plus the weighted normal tail. The shared scenario prevents the probability from falling below c no matter how small the normal independent tail becomes. A more realistic fault domain may remove only part of the set, requiring a conditional count distribution for that domain. Map replica placement and communication dependencies before arguing that a larger odd number automatically improves the user's service.
Even when a reachable majority exists, correctness requires a protocol whose quorum intersections, state transitions, durable storage, and failure model support its claims. Crash-fault majority counting does not establish Byzantine tolerance. A stale leader, unsafe membership change, lost durable state, or read path bypassing required barriers can return incorrect answers while most replicas are up. The reliability lab's green majority indicator is intentionally limited to counts. Treat that indicator as a necessary resource condition in the declared model, not a certificate of linearizability, persistence, or safe recovery.
Validate count and communication evidence separately
Record failures by domain, operation, and observation point. Exercise a partition with many processes still running, a restart after durable-state loss, and failover under realistic load. Compare the model's predicted no-quorum periods with actual failed operations rather than relying only on host uptime. A deployment can maintain the count while exhausting CPU on every survivor, making a nominal quorum too slow for the deadline. Include deadline and capacity conditions in the availability event when those are part of the objective, and keep causal diagnosis separate from a count correlation.
Use the binomial lab for the probability question. Reset, explicitly set BOTH unavailability p=0.1 and n=5, predict tail K≥3 equals 0.00856, then Play or Step. Edits retain elapsed t; playback highlights exact counts rather than sampling replica states. Separately, on paper, five replicas with two unavailable leave three up against threshold three; three unavailable leave only two. That arithmetic is a count condition, not a protocol. The instrument includes neither correlation nor communication, and its independent distribution must not be treated as evidence that real replicas can elect a safe leader or preserve acknowledged data.
Work it through
Five replicas under an independent toy model
Five replicas each have independent unavailability probability 0.1 for one fictional observation. A strict majority is required; assume count availability equals usable participation for this example.
The majority is floor(5/2)+1=3, so no quorum means at least three replicas unavailable.
The tail is 10×0.1³×0.9² + 5×0.1⁴×0.9 + 0.1⁵ = 0.0081+0.00045+0.00001=0.00856.
If a disjoint common scenario with probability 0.01 disables all replicas and the same independent tail applies otherwise, total becomes 0.01+0.99×0.00856=0.0184744.
The independent count model gives 0.856-percent no-quorum probability; the stated mixture raises it to about 1.84744 percent without changing replica count.
The living notebook
Explore the model
Interactive lab · probability
Estimate only the declared independent quorum tail
Reset, explicitly set BOTH p=0.1 and n=5, predict P(K≥3)=0.00856, then Play or Step. A success denotes an unavailable replica. Edits retain t. This exact binomial count assumes identical independent events and has no network topology, correlated domain, leader, log, membership protocol, or durability guarantee.
- Mean · np
- 5
- Variance · np(1−p)
- 2.5
- Total probability
- 1
These are exact binomial probabilities for independent trials with one fixed success probability. Playback tours the distribution; it does not resample outcomes. Parameter changes pause playback and recompute the model at the current elapsed time. Reset restores both parameters and returns time to zero. Playback starts paused. Adjust either parameter, then choose Play or Step.
Look forA quorum-availability tail is a narrow probability claim; majority count alone does not establish consistent or durable service.
Pause & reason
Check your understanding
Your turn
Try it yourself
Three replicas have independent unavailability p=0.2 and need a majority. Calculate no-quorum probability. Explain why placing all three behind one shared failed gateway requires a separate scenario.
Take a moment to make a prediction or work it out on paper. Open a hint when you need one.
Give me a hint
A majority of three is two, so sum exactly two and exactly three unavailable outcomes.
Compare with the solution
The tail is 3×0.2²×0.8+0.2³=0.096+0.008=0.104. A shared gateway can make replicas unusable together, violating unconditional independence. Model its probability and conditional impact rather than cubing or squaring only the local replica probabilities.
Keep the idea
Take it with you
- A quorum threshold maps to a precisely defined count-availability event.
- Independent binomial tails do not include shared causes or communication partitions.
- Consistency, durability, and failure tolerance need an actual protocol argument.
Read further
Original sources and deeper explanations to follow at your own pace.
Optional progress, saved in this browser when available. Revisit any lesson at any time.
Lesson not marked complete.