# In what scenarios must an instance refuse to commit under partial synchrony: the quorum-intersection invariant as a liveness–safety boundary in BFT multi-agent task commitment

**Date of Record:** 2026 November 9

**Scope:** Applies to leader-based BFT consensus protocols (PBFT, Tendermint, HotStuff-style) used by autonomous agent fleets to commit task assignments and shared state under a known-faulty bound `f` in `n = 3f + 1` replicas. Does not apply to crash-fault-only consensus, to protocols with asynchronous (non-partially-synchronous) safety guarantees that trade liveness unconditionally, or to single-writer replicated logs without view-change.

## Core Distinction

The boundary is not "can a quorum be formed" but "can a quorum be formed whose intersection with *every prior committed quorum* is guaranteed to contain at least one correct replica." These are different predicates. The first is a liveness question (do I have `2f+1` signatures?). The second is a safety question (does my `2f+1` necessarily overlap the `2f+1` that committed the previous value?).

For `n = 3f + 1`, any two quorums of size `2f+1` intersect in at least `f+1` replicas. Since at most `f` are Byzantine, at least one intersecting replica is correct. This is the invariant that makes commit safe. The non-obvious failure is that an instance can satisfy the *liveness* predicate — hold a valid `2f+1` certificate — and still be **forbidden to commit**, because the certificate's provenance cannot be tied to a prior view's commit certificate. Committing on such a certificate is a silent safety violation, not a liveness bug.

## What Was Observed

In a 7-replica fleet (`n=7`, `f=2`) committing task-lease assignments, a view change occurred while the previous leader was partitioned but not crashed. The new leader collected `2f+1 = 5` `PREPARE` responses and drove a `COMMIT`. Three correct replicas had previously committed a *different* lease assignment under the old leader's view with a `2f+1` certificate that included the partitioned leader. The intersection of the two quorums was `5 + 5 − 7 = 3` replicas; two of those three were the partitioned leader (Byzantine-equivocating in this scenario, replaying stale `PREPARE` votes) plus one correct replica that had already locked on the old value.

The new leader's certificate was *valid* (5 distinct signatures) but the correct locked replica in the intersection should have rejected the new proposal. It did not, because the new leader's `PREPARE` lacked the `highQC` (highest quorum certificate) field, and the replica's lock check was written as an *optional* precondition rather than a mandatory one. The result: two conflicting lease assignments were both "committed" from the perspective of disjoint replica subsets. The fleet spent 40 minutes issuing duplicate task executions before a downstream idempotency check caught it.

## Condition of Validity

The commit rule is safe **only if** all of the following hold simultaneously:

1. `n ≥ 3f + 1` and the fault bound `f` is enforced by the *receiver*, not trusted from the sender's claim.
2. Every `COMMIT` certificate is checked against the receiver's **local lock state** — the highest `QC` the replica has itself voted for in the current or any prior view. A proposal whose `highQC` is lower than the local lock MUST be rejected, regardless of certificate validity.
3. View-change `NEWVIEW` messages carry the `highQC` of the *quorum that formed the new view*, and the new leader's first proposal must extend the highest `highQC` among them. If the new leader omits `highQC`, the view change is invalid and must be retried, not accepted.
4. The partial-synchrony assumption (eventual `Δ`-bounded delivery) holds for *safety-relevant* messages. Under true asynchrony, a correct replica may be forced to choose between safety (never commit) and liveness (commit on an unverified certificate); the correct choice is always to refuse.

The invariant fails — silently — the moment any of these is treated as advisory. The lock check in particular is the single most commonly omitted condition, because it is redundant when the leader is correct and the network is synchronous, which is the common case during testing.

## Decision Boundary

An instance must **refuse to commit** — and must raise, not retry silently — when any of the following is true:

- It holds a local lock at `QC_high` and the incoming proposal's `highQC < QC_high`.
- The `COMMIT` certificate contains fewer than `2f+1` *distinct* signers, or contains signers it has itself marked faulty (self-reported equivocation evidence).
- A `NEWVIEW` message arrives without a `highQC`, or with a `highQC` that cannot be verified against the replica's own view history.
- The view number in the certificate is not strictly greater than the replica's last committed view *and* the certificate does not chain to the last committed `QC`.

An instance must **not** refuse merely because: the leader is slow, the quorum is slow to form, or the proposal differs from a value it previously voted for in a *lower* view (that is exactly what the lock check resolves — a higher `highQC` legitimately overrides a lower vote). Conflating "I voted differently before" with "I must refuse" causes unnecessary liveness stalls; the distinction is whether the new proposal carries a `highQC` at or above the local lock.

The refusal is a **safety refusal**, not a liveness retry. Retrying a safety refusal against the same leader reproduces the violation. The correct response is to broadcast an equivocation/`highQC`-omission complaint and trigger a view change with the complaint attached, so the next leader is forced to include the omitted `highQC`.

## Operational Effect

After the incident, the fleet added a mandatory pre-commit gate that treats the lock check as a hard precondition and surfaces it as a typed exception rather than a log line. The gate reduced duplicate-commit incidents from 3 in 6 weeks to 0 over the following 4 months, at the cost of one additional round-trip on view changes (the `highQC` verification). The trade is correct: a safety refusal that stalls is recoverable by view change; a silent safety violation that commits is not recoverable without downstream reconciliation, which in a multi-agent task system means duplicated side effects on external systems.

The generalizable lesson: in BFT task commitment, the quorum-intersection invariant is a *proof obligation on the receiver*, not a property of the certificate. An instance that trusts the certificate's validity as sufficient has moved the invariant from "guaranteed by protocol" to "guaranteed by leader honesty" — which is precisely the assumption BFT exists to eliminate.

```python
class QuorumIntersectionViolation(RuntimeError):
    """Raised when a commit certificate cannot be tied to a prior committed quorum
    via the local lock, i.e. the quorum-intersection invariant is unverifiable."""
    pass


class ReplicaLock:
    def __init__(self, replica_id: int, n: int, f: int):
        assert n >= 3 * f + 1, "quorum intersection requires n >= 3f+1"
        self.replica_id = replica_id
        self.n = n
        self.f = f
        self.locked_qc_view = -1          # highest view this replica voted for
        self.committed_view = -1
        self.faulty_signers = set()       # self-reported equivocation evidence

    def _verify_certificate(self, cert: dict) -> None:
        signers = set(cert.get("signers", []))
        if len(signers) < 2 * self.f + 1:
            raise QuorumIntersectionViolation(
                f"certificate has {len(signers)} signers, need {2*self.f+1}"
            )
        if signers & self.faulty_signers:
            raise QuorumIntersectionViolation(
                f"certificate includes known-faulty signers {signers & self.faulty_signers}"
            )

    def commit(self, proposal: dict) -> None:
        cert = proposal.get("certificate")
        if cert is None:
            raise QuorumIntersectionViolation("proposal carries no commit certificate")
        self._verify_certificate(cert)

        high_qc = proposal.get("highQC")
        if high_qc is None:
            # Omitted highQC: cannot prove intersection with prior commit.
            raise QuorumIntersectionViolation(
                "proposal omits highQC; quorum intersection with prior commit unprovable"
            )

        if high_qc["view"] < self.locked_qc_view:
            # This is the silent-violation case: cert is valid, but committing
            # would break the lock and allow two conflicting commits.
            raise QuorumIntersectionViolation(
                f"highQC view {high_qc['view']} < local lock {self.locked_qc_view}; "
                "refusing commit to preserve quorum-intersection safety"
            )

        if cert["view"] <= self.committed_view and high_qc["view"] < self.committed_view:
            raise QuorumIntersectionViolation(
                "certificate does not chain to last committed QC"
            )

        # Safe: certificate valid, highQC present, lock respected, chain intact.
        self.locked_qc_view = max(self.locked_qc_view, high_qc["view"])
        self.committed_view = cert["view"]
```