# Under what conditions must an instance refuse to commit on quorum overlap alone in multi-agent Byzantine consensus for shared-state coordination **Date of Record:** 2026 November 18 **Scope:** Applies to leader-based replicated state machines (PBFT-style or HotStuff-style) coordinating shared agent state where up to `f` of `3f+1` peers are Byzantine and the safety argument rests on quorum intersection. Does not apply to crash-fault-only systems, to systems with attested hardware or trusted execution, or to single-writer append-only logs with no cross-quorum state handoff. ## Core Distinction The distinction that matters operationally is between **quorum intersection as a set-theoretic guarantee** and **quorum intersection as a safety proof for a specific decision**. In a `3f+1` system, any two quorums of size `2f+1` intersect in at least `f+1` replicas, of which at least one is honest. This guarantees that *some* honest replica has seen both quorums. It does **not** guarantee that the honest replica that saw both quorums is the one whose vote is counted in the commit certificate you are about to accept, nor that the intersection replica's state was durably persisted before it acknowledged. The failure mode is subtle: a new leader collects a `2f+1` commit certificate for value `V` at view `n+1`. The certificate is cryptographically valid — every signature verifies. The intersection argument says at least one honest replica in this certificate also voted in the earlier `2f+1` quorum for value `W` at view `n`. But if that intersecting honest replica acknowledged the earlier quorum *before* fsyncing its prepare state, and then crashed and recovered from a stale log, it will sign the new certificate while having forgotten `W`. The certificate is valid; the intersection replica exists; the safety proof is void because the intersecting vote was not durable. This is the non-obvious boundary: **a valid commit certificate proves that a quorum signed, not that a quorum's signatures were grounded in durable state.** Quorum overlap is necessary but not sufficient for commit safety. ## What Was Observed During a coordinated shared-state update across a 7-replica cluster (`f=2`, quorum `5`), a network partition split the cluster `5/2`. The majority side committed value `W` at view 12 with certificate `C_W` containing signatures from replicas `{r0,r1,r2,r3,r4}`. Replica `r3` had acknowledged its prepare to the leader at view 12 within 4ms of receiving it, but its WAL fsync completed 180ms later; the leader counted the acknowledgment on receipt, not on fsync confirmation. A second partition healed and the minority leader (`r5`, Byzantine) proposed value `V` at view 13. It collected a certificate `C_V` from `{r2,r3,r4,r5,r6}`. Replica `r3` had crashed and recovered between views 12 and 13 from a WAL snapshot taken at view 11 — it had no record of `W`. It signed `C_V` in good faith. `C_V` is cryptographically valid. The intersection `{r2,r3,r4}` is non-empty and contains honest replicas `r2` and `r4` — but `r2` and `r4` had voted for `W` and were not consulted; only `r3`'s signature was needed to make the quorum count, and `r3`'s signature was a lie it did not know it was telling. The cluster committed `V`, overwriting `W`, with two valid certificates for conflicting values at adjacent views. Safety was violated with zero forged signatures and zero equivocating honest replicas. ## Condition of Validity The quorum-intersection safety argument is valid for a given commit certificate **if and only if** every signature in the certificate was produced by a replica whose vote was grounded in state that survived a crash-recovery cycle prior to the signature being emitted. Concretely, all of the following must hold: 1. **Durable-before-ack:** every replica fsyncs its prepare/commit record to stable storage before transmitting its signature; the leader counts a signature only after receiving an fsync-confirmed acknowledgment, not a bare vote. 2. **Recovery integrity:** a recovering replica replays its WAL to the highest durable view before participating in any new view; it must not sign for a view higher than its durable high-water mark without first reconciling against a quorum. 3. **Certificate freshness:** a commit certificate's signatures must all originate from views `≤` the certificate's stated view, and the certificate must be rejected if any signer's durable high-water mark at signing time is below the certificate's view. 4. **Intersection liveness:** at least one replica in the certificate's quorum must have a durable record of the prior committed value at the immediately preceding view. Condition 1 is the one most frequently violated in practice because the acknowledgment path is on the hot path and fsync is slow. Conditions 2 and 3 require the certificate to carry per-signer durable-view metadata, which most PBFT implementations omit. ## Decision Boundary An instance must **refuse to commit** — must raise and halt rather than accept the certificate — when any of the following holds, even if the certificate is cryptographically valid and the quorum count is met: - The certificate contains a signature from a replica whose last-known durable high-water mark is strictly less than the certificate's view (stale-signer condition). - The certificate's signer set intersects the prior committed certificate's signer set in exactly one replica, and that replica's durable high-water mark is unverified or below the prior view (degenerate-intersection condition). - The local replica cannot confirm that its own prepare record for the prior view was fsynced before it emitted its own signature (self-durability condition). - The certificate's view is exactly one greater than the prior committed view and the prior view's certificate has not been independently confirmed durable by a quorum (adjacent-view condition). An instance may **proceed to commit** when the quorum count is met, signatures verify, and every signer's durable high-water mark is `≥` the certificate's view. Quorum overlap alone is never sufficient; durable-signer confirmation is the gating predicate. ## Operational Effect The practical consequence is that commit latency is bounded below by the slowest fsync in the quorum, not by the slowest network round-trip. In the observed cluster this raised p99 commit latency from 12ms to 190ms — a 16× regression that is the *correct* cost of safety. Implementations that optimize this away by counting bare votes reintroduce the failure above. The second effect is that recovery is no longer local. A recovering replica cannot simply replay its WAL and rejoin; it must obtain a durable-view attestation from a quorum before signing anything at a view above its own high-water mark. This adds one round-trip to every recovery, and it is the only mechanism that prevents the stale-signer condition from being exploitable by a Byzantine leader that deliberately targets recently-recovered replicas. The third effect is that certificate validity becomes a *two-layer* predicate: cryptographic validity (signatures verify) and durability validity (signers' state was grounded). Conflating them is the boundary failure. A certificate that passes layer one and fails layer two is not a weaker certificate — it is a certificate that proves the wrong thing. ```python class QuorumSafetyError(RuntimeError): """Raised when a commit certificate is cryptographically valid but fails the durable-signer predicate required for quorum-intersection safety.""" pass def verify_commit_certificate(cert, durable_high_water_marks, prior_cert, quorum_size): """ cert: dict with keys 'view', 'value', 'signers' (list of replica ids) durable_high_water_marks: dict replica_id -> highest durably-fsynced view prior_cert: the most recent certificate this replica committed, or None quorum_size: 2f+1 for a 3f+1 system """ signers = set(cert["signers"]) view = cert["view"] if len(signers) < quorum_size: raise QuorumSafetyError( f"certificate at view {view} has {len(signers)} signers, " f"below quorum {quorum_size}" ) # Layer 1: cryptographic validity is assumed checked by caller. # Layer 2: durable-signer predicate. for r in signers: hwm = durable_high_water_marks.get(r) if hwm is None: raise QuorumSafetyError( f"signer {r} has no durable high-water mark; " f"cannot confirm its vote at view {view} was fsynced" ) if hwm < view: raise QuorumSafetyError( f"stale-signer: {r} signed view {view} but its durable " f"high-water mark is {hwm}; its vote may not survive recovery" ) # Adjacent-view / degenerate-intersection check. if prior_cert is not None and view == prior_cert["view"] + 1: intersection = signers & set(prior_cert["signers"]) if len(intersection) < 2: only = next(iter(intersection)) if intersection else None if only is None or durable_high_water_marks.get(only, -1) < prior_cert["view"]: raise QuorumSafetyError( f"degenerate-intersection at view {view}: prior view " f"{prior_cert['view']} overlaps in {intersection} with " f"unverified durability; refusing to commit" ) return True ```