# When must an instance refuse to commit: the Quorum-Intersection Blind Spot in BFT task commitment under partial synchrony **Date of Record:** 2026 November 17 **Scope:** Applies to leader-based BFT consensus protocols (PBFT/Tendermint/HotStuff lineage) where a replica must decide whether a prepared value is safe to commit after a view change, given an `f`-tolerance assumption and a network that is merely partially synchronous. Does not apply to crash-fault-tolerant protocols, to protocols with trusted hardware attestation on every message, or to the case where the client itself is part of the quorum. ## Core Distinction The distinction that matters operationally is between **quorum intersection** (a set-theoretic property: any two quorums of size `2f+1` out of `3f+1` share at least one correct replica) and **quorum *observability*** (an epistemic property: the new leader can actually *learn* what the intersecting replica knew). These are routinely conflated. Intersection guarantees that a correct replica existed in both the old and new quorum; it does **not** guarantee that this replica's vote is discoverable by the new leader within the view-change timeout. The failure mode is this: a replica holds a `prepared` certificate for value `v` at sequence `n`, but the new leader collects `2f+1` `VIEW-CHANGE` messages that *omit* this replica — not because it is faulty, but because its `VIEW-CHANGE` message was delayed past the leader's collection deadline. The leader then forms a quorum that is set-theoretically valid (`2f+1` signatures) yet *epistemically incomplete*: the prepared certificate for `v` is invisible. The leader proposes `v' ≠ v`, and the new quorum commits it. Safety is violated even though no assumption about `f` was broken. ## What Was Observed In a five-replica deployment (`f = 1`, quorum `3`), a leader change was triggered by a slow primary. The new leader gathered three `VIEW-CHANGE` messages within 800 ms and — seeing no `prepared` certificate at sequence 412 — proposed a fresh block `B'`. Replicas `R2` and `R4` accepted and committed `B'`. Replica `R3` had, in the prior view, received `PREPARE` messages from `R1` and `R2` for block `B` at sequence 412 and had multicast its own `PREPARE`. Its `VIEW-CHANGE` message, carrying the prepared certificate, was delayed by 1.4 s due to a transient queueing stall on its egress path. When it arrived, the leader had already committed `B'`. `R3` was forced to roll back a value it had legitimately prepared. The invariant that broke is subtle: **`2f+1` signed `VIEW-CHANGE` messages are a necessary but not sufficient condition for a safe leader proposal.** Sufficiency requires that the set of `VIEW-CHANGE` senders *intersect every possible prepared quorum*, which is only true if the leader waits for the full `3f+1` set *or* proves that no prepared certificate can exist. The standard `2f+1` shortcut silently assumes the omitted `f` replicas are faulty; here one omitted replica was merely slow. ## Condition of Validity The `2f+1` `VIEW-CHANGE` rule is valid only under the conjunction: 1. **Strong synchrony during view change.** Every correct replica's `VIEW-CHANGE` arrives within the leader's collection window `Δ_collect`. This is *not* implied by partial synchrony; partial synchrony only guarantees eventual delivery, not bounded delivery during a specific window. 2. **Or: no prepared value exists at the sequence.** If the leader can show that no replica could have prepared (e.g., the prior view never reached the `PREPARE` phase), the shortcut is safe. 3. **Or: the leader waits for `3f+1` `VIEW-CHANGE` (or `2f+1` plus an explicit `f+1`-sized "no prepared" attestation set).** In the observed incident, condition 1 was assumed but not enforced: the leader used a fixed 800 ms timeout as a proxy for synchrony. When the actual delivery latency exceeded that timeout for a correct replica, the proxy failed and the shortcut became unsound. ## Decision Boundary A replica (or the leader on its behalf) must **refuse to treat a `2f+1` `VIEW-CHANGE` quorum as sufficient** whenever any of the following hold: - The collection window `Δ_collect` was chosen by timeout rather than by an observed lower bound on delivery latency. - The set of `VIEW-CHANGE` senders is not known to intersect every quorum that could have prepared a value at the target sequence. - The leader has no `f+1` "no prepared" attestations covering the complement of its received set. - The protocol's safety proof relies on `f` faulty replicas being the *only* explanation for missing messages — an assumption that is false under partial synchrony. Conversely, the shortcut is safe to take when the leader has either (a) received `3f+1` `VIEW-CHANGE` messages, (b) received `2f+1` plus `f+1` explicit no-prepared attestations, or (c) proven the target sequence was never prepared. The boundary is therefore not "how many messages did I get?" but "**can I prove that the messages I did not get could not have carried a prepared certificate?**" Absent that proof, `2f+1` is a *liveness* quorum, not a *safety* quorum. ## Operational Effect The practical consequence is that view-change timeouts must be treated as **safety parameters, not performance parameters**. Tuning `Δ_collect` downward to reduce failover latency directly shrinks the margin by which the `2f+1` shortcut is sound. In the observed deployment, reducing `Δ_collect` from 2 s to 800 ms to meet an SLO was the proximate cause of the rollback. The correct operational posture is to make the leader's commit decision conditional on an explicit safety predicate — a proof of quorum observability — and to fail closed (abort the view change, retry with a longer window) rather than fail open (commit on `2f+1` alone). This converts a silent safety violation into a visible liveness stall, which is the correct trade for any system where committed state must be irreversible. The following guard encodes the predicate and raises when the leader attempts to commit without observability proof. ```python class QuorumObservabilityError(RuntimeError): """Raised when a leader attempts to commit on a quorum that is set-theoretically valid but epistemically incomplete.""" pass def assert_commit_safe( received_view_change: set[int], total_replicas: int, f: int, prepared_certificates: dict[int, object], target_sequence: int, no_prepared_attestations: set[int], ) -> None: """Enforce the quorum-observability predicate before committing. A 2f+1 VIEW-CHANGE set is only sufficient if it provably intersects every quorum that could have prepared a value at target_sequence. """ quorum = 2 * f + 1 n = len(received_view_change) if n < quorum: raise QuorumObservabilityError( f"insufficient VIEW-CHANGE messages: {n} < {quorum}" ) # If the full replica set responded, observability is trivially complete. if n == total_replicas: return # A prepared certificate at the target sequence must be visible. if target_sequence in prepared_certificates: holder = prepared_certificates[target_sequence] if holder not in received_view_change: raise QuorumObservabilityError( f"prepared certificate for seq {target_sequence} held by " f"replica {holder}, absent from VIEW-CHANGE set " f"{sorted(received_view_change)}" ) return # No prepared certificate observed: require f+1 explicit "no prepared" # attestations covering the complement of the received set. complement = set(range(total_replicas)) - received_view_change covered = complement & no_prepared_attestations if len(covered) < len(complement): raise QuorumObservabilityError( f"cannot prove absence of prepared value at seq {target_sequence}: " f"uncovered replicas {sorted(complement - covered)}" ) def leader_commit( received_view_change: set[int], total_replicas: int, f: int, prepared_certificates: dict[int, object], target_sequence: int, no_prepared_attestations: set[int], value: object, ) -> str: assert_commit_safe( received_view_change, total_replicas, f, prepared_certificates, target_sequence, no_prepared_attestations, ) return f"committed {value!r} at seq {target_sequence}" ```