advanced26 min studyLesson 407 in Engineering

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

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.

q=⌊n2⌋+1,P(no quorum)=∑k=n−q+1n(nk)pk(1−p)n−kq=\left\lfloor\frac n2\right\rfloor+1,\qquad P(\text{no quorum})=\sum_{k=n-q+1}^{n}\binom nk p^k(1-p)^{n-k}
This count-only model assumes n independent identical replica-unavailability events with probability p over one shared horizon. q and k are counts; the result is a dimensionless availability probability, not a proof of a working consensus protocol.↔ Scroll wide equations horizontally.

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.

P(no quorum)=c+(1−c)P(normal tail∣¬C)P(\text{no quorum})=c+(1-c)P(\text{normal tail}\mid\neg C)
The common event C has probability c and forces no quorum; the remaining term uses the explicitly modeled normal environment. This total-probability decomposition does not assume unconditional replica independence or explain the protocol's safety.↔ Scroll wide equations horizontally.

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.

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.

  1. The majority is floor(5/2)+1=3, so no quorum means at least three replicas unavailable.

  2. The tail is 10×0.1³×0.9² + 5×0.1⁴×0.9 + 0.1⁵ = 0.0081+0.00045+0.00001=0.00856.

  3. 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 result

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.

Explore the model

Interactive lab

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.

Estimate only the declared independent quorum tailThese are exact binomial probabilities for independent trials with one fixed success probability. Playback tours the distribution; it does not resample outcomes. Current readings: Mean · np: 5; Variance · np(1−p): 2.5; Total probability: 1. All parameters are adjustable with the labeled controls below.03581000.070.150.220.3Successes kP(X = k)k = 0 · P = 9.77e-4
Exact probabilityHighlighted outcomeMean np
Mean · np
5
Variance · np(1−p)
2.5
Total probability
1
t = 0 s

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.

Check your understanding

A five-replica diagram shows three up and a majority threshold of three. What has been established by that count alone?

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.

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.