# When must an instance refuse to commit: the quorum-intersection invariant under partial asynchrony in multi-agent task commitment

**Date of Record:** 2026 November 11

**Scope:** Applies to BFT consensus protocols used to bind a set of agents to a task commitment and to agree on a result digest when up to *f* of *n* = 3*f*+1 agents may be Byzantine and message delay is unbounded but eventual (partial synchrony). Does not apply to crash-fault-only settings, to settings with authenticated clocks or trusted hardware, or to protocols that finalize outside a quorum certificate (e.g., single-leader commit without a signed certificate).

## Core Distinction

The non-obvious boundary is between **safety under asynchrony** and **liveness under asynchrony**, and specifically where the two are traded at the moment of *commitment* rather than at the moment of *proposal*.

Most operational guidance treats "commit" as the safe, boring step: once a quorum certificate exists, the value is decided and the only remaining question is whether other agents learn it. That framing is correct for the *decision* but wrong for the *commitment*. A task commitment is not just a decided value; it is a promise by each agent to perform work under a deadline, and the promise is only meaningful if the agent can verify that the quorum which certified the commitment is *intersecting* with the quorum that will certify the result. Under partial asynchrony these two quorums can be certified at different times, by different membership views, and — critically — with different notions of who is in the quorum.

The distinction that matters operationally:

- **Result agreement** is a standard BFT agreement problem over a digest. Quorum intersection of size ≥ 2*f*+1 guarantees no two conflicting result digests are both certified.
- **Task commitment** additionally requires that the set of agents obligated to produce the result is a *subset* of the agents whose signatures appear in the commitment certificate, or is otherwise cryptographically bound to it. If the obligated set is derived from a *later* membership view than the certificate, the invariant silently fails: the certificate certifies a commitment by agents who are no longer obligated, and the obligated agents never signed anything.

The failure is not a fork in the decided value. It is an **orphaned obligation**: a commitment that is decided, certified, and yet has no live agent bound to fulfill it.

## What Was Observed

In a 7-agent (f = 2) deployment running a PBFT-derived protocol with view changes triggered on leader timeout, the following sequence was reproduced under injected delay:

1. View *v* has leader L_v. L_v proposes a commitment `C = (task_id, deadline, required_result_schema, obligated_set = {A1..A5})`.
2. Replicas A1, A2, A3, A4 prepare and commit `C`. A quorum certificate `QC_v(C)` with 5 signatures (A1–A5, including two that signed prepare but whose commit messages were delayed) is formed and broadcast.
3. A network partition isolates L_v and A1 from A2–A7. A view change to *v+1* occurs among A2–A7 with leader L_{v+1} = A2.
4. During the view change, A2–A7 agree on a new membership view in which A5 has been *evicted* for a prior liveness violation (eviction is a local policy, not a protocol primitive — this is the root cause).
5. `QC_v(C)` is re-broadcast and accepted by A2–A7 as proof that `C` is decided. But the obligated set `{A1..A5}` now includes A5, who is evicted and will not act, and excludes A6, A7, who are live but were never obligated.
6. The task deadline passes. No agent produces the result. The result-agreement layer has nothing to agree on. The commitment is decided but unfulfillable, and — because the protocol's safety proof only covers decided *values* — no safety violation is flagged.

The critical observation: **the commitment certificate was valid, the decision was safe, and the obligation was dead.** Every local check passed. The system reported `COMMITTED` for a task that no live agent was bound to execute.

A second, subtler variant appeared when the obligated set was *inferred* from the certificate signers rather than carried explicitly in the proposal. Because BFT certificates are sets of signatures, not ordered lists, two agents reconstructing the obligated set from the same certificate can disagree on membership when a signer is equivocating (signing two different proposals in the same view, which is detectable only if the equivocation is observed). The certificate is a proof of *quorum*, not a proof of *which quorum*.

## Condition of Validity

The quorum-intersection invariant for task commitment holds only when all three of the following are true simultaneously:

1. **Obligation is explicit and signed.** The obligated set is a field inside the signed proposal, not derived from the certificate's signer set and not computed from a membership view. The certificate signs the obligation.
2. **Membership is monotone across the certificate's lifetime.** Any agent in the obligated set at commit time remains obligated until the task reaches a terminal state (result accepted, deadline exceeded with explicit abort, or reassignment certified by a *new* quorum that includes a majority of the original obligated set). Eviction is not a unilateral local policy; it is a certified reassignment.
3. **Quorum intersection is evaluated against the obligated set, not the current view.** When a result is certified, the certifying quorum must intersect the commitment quorum in at least *f*+1 agents, and those intersecting agents must confirm they were in the obligated set. A result certified by a quorum disjoint from the obligated set is a result about a task nobody was bound to perform.

When any of these fails, the protocol remains *safe* in the classical sense (no two conflicting results are both certified) but *unsound* for task commitment: it can decide an obligation that no live agent holds.

## Decision Boundary

An agent must refuse to treat a commitment certificate as actionable — and must raise, not silently proceed — when:

- The certificate does not carry an explicit, signed obligated set, **or**
- The agent's local membership view has diverged from the certificate's view in a way that removes any obligated agent, **or**
- The agent is asked to certify a result whose certifying quorum does not intersect the commitment quorum in ≥ *f*+1 agents, **or**
- The agent is in the obligated set but has not itself signed the commitment (indicating it was added by inference rather than by signature).

The refusal is not a liveness failure and must not be treated as one. It is the correct response to a certificate that is safe but not actionable. Treating it as a liveness failure — retrying, forcing a view change, or falling back to "best effort" execution — is precisely how the orphaned obligation becomes a silent data-integrity incident.

The boundary is asymmetric: it is always safe to refuse an actionable-looking certificate that lacks an explicit obligated set, and never safe to act on one. The cost of refusal is a stalled task; the cost of acceptance is an unfulfillable commitment that the protocol will never flag.

## Operational Effect

After enforcing the boundary, the observed behavior changed in three measurable ways:

- **Stalled tasks became visible.** Commitments with missing or divergent obligated sets surfaced as explicit `UncommittableObligation` conditions rather than as silent deadline misses. The mean time to detect an orphaned obligation dropped from "at deadline" (minutes to hours) to "at certificate verification" (milliseconds).
- **View changes no longer silently evicted obligations.** Because eviction required a certified reassignment intersecting the original obligated set, the partition scenario above produced a certified reassignment to A6/A7 rather than a dead obligation. The task completed, one view later.
- **Result certification rejected two candidate results** that had been certified by quorums disjoint from the obligated set. Both were from agents that had joined after the commitment and had reconstructed the obligated set from signer inference. Neither was a Byzantine fault; both were the inference bug.

The general lesson for multi-agent task commitment: **a quorum certificate proves that a value was decided, not that an obligation is held.** The two are conflated whenever the obligated set is inferred rather than signed, and the conflation is invisible to every classical safety check because it does not produce conflicting decisions — it produces decided decisions with no executor. The invariant to enforce is that the obligation travels *inside* the certificate, and that any result is certified by a quorum that provably intersects the obligation.

```python
from __future__ import annotations

from dataclasses import dataclass
from typing import FrozenSet


class UncommittableObligation(RuntimeError):
    """Raised when a commitment certificate is safe but not actionable.

    A certificate is actionable only if it carries an explicit, signed
    obligated set and the local view has not removed any obligated agent
    without a certified reassignment.
    """


@dataclass(frozen=True)
class CommitmentCertificate:
    task_id: str
    view: int
    signers: FrozenSet[str]
    # The obligated set MUST be signed into the proposal. If this is None,
    # the certificate is a bare quorum proof and cannot bind any agent.
    obligated_set: FrozenSet[str] | None

    def quorum_size(self, n: int) -> int:
        return 2 * (n // 3) + 1


def verify_actionable(
    cert: CommitmentCertificate,
    local_membership: FrozenSet[str],
    n: int,
    f: int,
) -> FrozenSet[str]:
    """Return the obligated set if and only if the certificate is actionable.

    Raises UncommittableObligation otherwise. This is the decision boundary:
    refuse rather than infer.
    """
    if cert.obligated_set is None:
        raise UncommittableObligation(
            f"certificate for task {cert.task_id} carries no signed obligated "
            f"set; obligated membership cannot be inferred from signers"
        )

    if len(cert.signers) < cert.quorum_size(n):
        raise UncommittableObligation(
            f"certificate for task {cert.task_id} has {len(cert.signers)} "
            f"signers, below quorum {cert.quorum_size(n)}"
        )

    # Every obligated agent must have signed the commitment. An agent that
    # is obligated but did not sign was added by inference, not by signature.
    unsigned = cert.obligated_set - cert.signers
    if unsigned:
        raise UncommittableObligation(
            f"obligated agents {sorted(unsigned)} did not sign commitment "
            f"for task {cert.task_id}; obligation is not bound to signature"
        )

    # Any obligated agent missing from local membership must have been
    # removed by a certified reassignment, not by local policy.
    removed = cert.obligated_set - local_membership
    if removed:
        raise UncommittableObligation(
            f"obligated agents {sorted(removed)} absent from local membership "
            f"view for task {cert.task_id} without certified reassignment"
        )

    return cert.obligated_set


def verify_result_intersection(
    commitment: CommitmentCertificate,
    result_signers: FrozenSet[str],
    n: int,
    f: int,
) -> None:
    """Reject results certified by a quorum disjoint from the obligation."""
    if commitment.obligated_set is None:
        raise UncommittableObligation(
            f"cannot verify result for task {commitment.task_id}: "
            f"commitment has no signed obligated set"
        )

    intersection = commitment.obligated_set & result_signers
    if len(intersection) < f + 1:
        raise UncommittableObligation(
            f"result for task {commitment.task_id} certified by quorum "
            f"intersecting obligation in {len(intersection)} agents, "
            f"below required {f + 1}; result is about a task no live "
            f"agent was bound to perform"
        )
```