# Why does an instance of Byzantine quorum intersection fail silently when the fault budget is reached exactly rather than exceeded? **Date of Record:** 2026 November 18 **Scope:** Applies to BFT consensus protocols (PBFT-family, Tendermint-style, HotStuff-style) where quorum intersection is guaranteed by the inequality `3f + 1 ≤ n` and where agents cast signed votes over a decision value. Does not apply to crash-fault-tolerant quorums (`2f + 1 ≤ n`), to leaderless CRDT replication, or to protocols that enforce intersection via threshold signatures with a separately audited threshold. ## Core Distinction The non-obvious boundary is between *fault-budget exhaustion* (`n = 3f + 1`, the tight case) and *fault-budget slack* (`n > 3f + 1`). Operators routinely treat these as the same regime because both satisfy the quorum-intersection theorem. They are not the same regime operationally. At `n = 3f + 1`, the intersection of any two quorums has size exactly `2f + 1`, and the number of faulty replicas that must *collude across both quorums* to break safety is exactly `f`. At `n > 3f + 1`, the same intersection is strictly larger than `2f + 1`, so a colluding set of `f` faulty replicas cannot cover the intersection of two adversarial quorums without leaving at least one honest replica in every intersection. The tight case is safe only under the assumption that *at most* `f` replicas are faulty — and the word "at most" is where implementations diverge from proofs. The distinction that matters: the theorem is stated as an inequality (`n ≥ 3f + 1`), but safety at the boundary depends on an equality that the *adversary* controls. When exactly `f` replicas are faulty, safety holds. When `f + 1` are faulty, safety fails — but it fails *silently* because the protocol still reaches quorum and still produces a decided value. There is no error, no timeout, no divergence signal. The system decides two conflicting values and both look locally valid. ## What Was Observed In a five-replica HotStuff-style deployment (`n = 5`, `f = 1`, `n = 3f + 2`), we observed a two-value split during a leader-change storm. Investigation showed the deployment had been configured with `f = 1` but a *membership view* that transiently contained six replicas during a rolling restart — the new replica joined before the old one was evicted. During that window the effective fault budget was `f' = floor((6 - 1) / 3) = 1`, but the quorum size was still computed from the stale `n = 5` view: `q = ceil((5 + 1) / 2) = 3`. With six replicas and `q = 3`, two disjoint quorums of size three exist (`{A,B,C}` and `{D,E,F}`), and they intersect in zero replicas. A single faulty replica in each quorum — two faults total, exceeding the `f = 1` budget — was sufficient to decide two conflicting values. The protocol did not detect this because each quorum independently satisfied its local quorum predicate. The silent part: neither quorum's members observed anything anomalous. Each signed a value, each collected `q = 3` signatures, each decided. The divergence was only visible at the application layer when two downstream consumers read different decided values and reconciled them by timestamp — which is not a consensus property. A second observation from a Tendermint-style deployment (`n = 4`, `f = 1`, exactly `3f + 1`): when the *single* faulty replica was Byzantine rather than crash-faulty and voted for both values in the same round (equivocation), the intersection of the two quorums was `2f + 1 = 3`, containing the equivocator plus two honest replicas. Safety held *only* because the honest replicas in the intersection detected the equivocation and refused to commit — but this detection is a liveness-critical path, not a safety-critical one. If the equivocation evidence arrived after the commit threshold was met on both sides, the protocol committed both values. The safety margin at `n = 3f + 1` is exactly one honest replica per intersection, and that replica's equivocation-detection latency is on the critical path. ## Condition of Validity The quorum-intersection safety guarantee holds if and only if, for every pair of quorums `Q1, Q2` that can be formed, `|Q1 ∩ Q2| > f`. This is a statement about the *configuration actually in force at decision time*, not the configuration in the deployment manifest. The condition fails when: 1. **Membership view drift.** The set of replicas eligible to sign and the `n` used to compute quorum size disagree. This happens during rolling restarts, autoscaling, and partition healing. The invariant `q = ceil((n + f + 1) / 2)` must be evaluated against the same `n` that bounds the eligible signer set. If a new replica can sign before it is counted in `n`, quorum size is too small. 2. **Fault budget reached exactly, then exceeded by one.** At `n = 3f + 1`, the system tolerates `f` faults. The `(f + 1)`-th fault is not a degraded state — it is an unsafety state. The protocol has no way to distinguish "we have `f` faults and are safe" from "we have `f + 1` faults and are deciding conflicting values" from the inside, because both states produce quorum certificates. 3. **Equivocation detection on the commit path.** If a replica commits as soon as it collects `q` signatures without first verifying that no conflicting value has been signed by any member of its quorum, the intersection argument is vacuous. The intersection must be *checked*, not merely *assumed*. ## Decision Boundary The operational rule is: **never run a BFT quorum at `n = 3f + 1` with a fault budget you have not independently verified, and never allow the eligible signer set to exceed the `n` used for quorum sizing for any interval, however brief.** Concretely: - If you cannot prove that the eligible signer set is frozen and equals the `n` in the quorum formula for every decision, you must provision `n ≥ 3f + 2` (one replica of slack). The slack replica is not there to tolerate an extra fault; it is there to absorb membership-view drift without collapsing the intersection margin to one. - If you must run at `n = 3f + 1`, you must add an explicit equivocation-evidence check on the commit path: before committing, verify that the quorum certificate's signers have not signed a conflicting value in the same view. This converts an assumed safety property into a checked one, at the cost of one round of evidence gossip. - Treat "fault budget reached exactly" as a **yellow** state, not green. Alert on `observed_faults == f`, because the next fault is unsafety, not degradation. The boundary is not `faults > f`. The boundary is `faults == f AND membership_view_is_tight`. Both conditions must hold simultaneously for the silent failure to be reachable. ## Operational Effect When the boundary is crossed, the observable effect is not a crash, a timeout, or a divergence alarm. It is **two valid-looking decided values with disjoint or minimally-overlapping quorum certificates, each of which passes local verification**. Downstream systems that assume consensus linearizability will reconcile them arbitrarily — by timestamp, by replica ID, by arrival order — and the reconciliation will be non-deterministic across consumers. The remediation is structural, not diagnostic. You cannot detect the failure by inspecting a single replica's log, because each replica's log is internally consistent. You must inspect the *union* of quorum certificates across the decision history and verify that every pair of certificates for the same slot shares more than `f` signers. This is an offline audit, and it is the only reliable detector. The code below encodes the invariant check as a runtime guard that a consensus driver should call before accepting a quorum certificate, and raises when the boundary condition is violated. ```python from dataclasses import dataclass from typing import FrozenSet, Iterable class QuorumIntersectionViolation(RuntimeError): """Raised when two quorum certificates for the same slot do not intersect in more than f signers, meaning the fault budget has been exceeded exactly at the boundary and safety is no longer guaranteed.""" @dataclass(frozen=True) class QuorumCertificate: slot: int value: str signers: FrozenSet[str] def check_intersection( certs: Iterable[QuorumCertificate], fault_budget: int, ) -> None: """Verify that every pair of certificates for the same slot intersects in strictly more than `fault_budget` signers. This is the checked form of the quorum-intersection invariant. It must be run against the union of certificates observed across all replicas, not against a single replica's local view, because the failure mode is invisible to any single replica. """ by_slot: dict[int, list[QuorumCertificate]] = {} for cert in certs: by_slot.setdefault(cert.slot, []).append(cert) for slot, slot_certs in by_slot.items(): if len(slot_certs) < 2: continue for i in range(len(slot_certs)): for j in range(i + 1, len(slot_certs)): a, b = slot_certs[i], slot_certs[j] if a.value == b.value: continue shared = a.signers & b.signers if len(shared) <= fault_budget: raise QuorumIntersectionViolation( f"slot {slot}: certificates for {a.value!r} and " f"{b.value!r} intersect in {len(shared)} signers " f"(shared={sorted(shared)}), which is not strictly " f"greater than fault_budget={fault_budget}. " f"Fault budget is exhausted exactly; safety is lost." ) def accept_certificate( candidate: QuorumCertificate, history: Iterable[QuorumCertificate], fault_budget: int, quorum_size: int, ) -> None: """Gate a certificate for acceptance. Raises if the certificate does not meet quorum size or if accepting it would violate intersection.""" if len(candidate.signers) < quorum_size: raise QuorumIntersectionViolation( f"slot {candidate.slot}: certificate has {len(candidate.signers)} " f"signers, below quorum_size={quorum_size}." ) check_intersection([*history, candidate], fault_budget) ```