# Where must an instance reject a quorum certificate before applying it to a shared-state task graph

**Date of Record:** 2026 November 14

**Scope:** Applies to Byzantine fault-tolerant (BFT) multi-agent systems where agents commit mutations to a shared task graph via quorum certificates (QCs) over a partially synchronous network with a known, static validator set. Does not apply to leaderless CRDT-based replication, to systems with dynamic membership where the validator set itself is the object of consensus, or to single-writer append-only logs without graph-merge semantics.

## Core Distinction

The non-obvious boundary is between *validity of a certificate* and *applicability of the certified transition*. A QC proves that a quorum of validators signed off on a specific `(view, node_id, parent_hash, payload_hash)` tuple. It does **not** prove that the transition is applicable to the local task graph at the moment of application. Two distinct predicates must be evaluated:

1. **Certificate validity** — signature threshold met, view monotonic, no equivocation against a higher view. This is a pure function of the certificate and the validator set.
2. **Applicability** — the certified transition's precondition (`parent_hash`) is present in the local materialized graph, and no conflicting transition with an equal-or-higher view has already been applied to the same `node_id`.

The failure mode is that a correct BFT implementation will accept (1) and then *block* — or worse, *speculatively apply* — on (2), because the local graph has not yet caught up to the certified parent. Agents that conflate these two predicates either deadlock (waiting on a parent that a lagging peer will never deliver) or fork (applying a child before its parent, then reconciling by overwrite). The subtle invariant: **a QC is a proof of agreement, not a proof of readiness.**

## What Was Observed

In a 7-validator deployment (f=2, quorum=5) running a task-graph workload with fan-out dependencies, we observed a reproducible deadlock under a specific interleaving. Agent A proposed transition `T` on node `n` with parent `p`. Quorum signed `T`. Agent B, which had fallen behind on the branch containing `p`, received the QC for `T` before the block containing `p`. B correctly refused to apply `T` (parent absent) and buffered the QC. B then requested `p` from its peers. Its peers, seeing that `T` was already certified and that B held the QC, responded with "you already have the successor; fetch forward." B never received `p`. After the liveness timeout, B participated in a view change, but the new leader — also holding `T`'s QC — re-proposed `T` rather than `p`, since `T` was the highest certified leaf. The system cycled through three view changes before an operator intervened.

A second observation: under a different interleaving where `p` *was* present but a conflicting transition `T'` on the same `n` had been applied at an equal view (a Byzantine proposer equivocation that the local node had not yet detected), the agent applied `T` on top of `T'`, producing a graph node with two parents and a violated single-parent invariant. This was caught only at the next checkpoint by a cross-agent state hash mismatch — three views later.

## Condition of Validity

The applicability predicate is sound only under the conjunction:

- `parent_hash ∈ local_graph.nodes`, **and**
- `local_graph.nodes[parent_hash].height == certified.height - 1`, **and**
- no applied transition exists on `node_id` with `view >= certified.view` and `payload_hash != certified.payload_hash`.

The third clause is the one routinely omitted. It is not implied by certificate validity because two valid QCs at the same view can exist for different payloads only if a quorum signed both — which requires ≥ `quorum - f` Byzantine validators, i.e., it is impossible under the fault model *if* validators are honest. But the local agent cannot assume the local *view of the validator set* is current. If the agent's validator set is stale (a reconfiguration occurred and the agent missed it), the threshold it checks against is wrong, and a QC it accepts may be signed by a minority of the *current* set. Applicability must therefore be gated on `local_validator_epoch == certified.validator_epoch`, checked *before* the parent check, because a stale epoch invalidates the parent check's premise.

## Decision Boundary

The decision boundary is: **buffer, do not block, and never speculatively apply.** On receipt of a QC whose applicability predicate fails:

- If the failure is `parent_absent` and `certified.view <= local_highest_view`: buffer the QC keyed by `parent_hash`, emit a targeted fetch for `parent_hash`, and continue processing other QCs. Do not enter a wait state on the parent.
- If the failure is `parent_absent` and `certified.view > local_highest_view`: the local node is behind on view, not just on data. Escalate to view-sync before buffering; buffering without view-sync is what produced the observed deadlock, because peers believed the node was current.
- If the failure is `conflicting_applied_at_equal_or_higher_view`: do not apply. This is an equivocation signal. Emit the conflicting pair `(applied_payload_hash, certified_payload_hash)` to the equivocation detector and halt application on `node_id` until the detector resolves. Applying here is the fork.
- If the failure is `validator_epoch_mismatch`: reject the QC entirely and trigger reconfiguration catch-up. A QC from a stale epoch is not a certificate; it is a message.

The boundary is sharp: `parent_absent` is a *data* condition (buffer + fetch), `conflict` is a *safety* condition (halt + detect), `epoch_mismatch` is a *configuration* condition (reject + resync). Treating all three as "wait" is the common error.

## Operational Effect

Agents that implement the three-way split above eliminate the view-change livelock (the buffered-QC-plus-targeted-fetch path makes `p` retrievable from any peer holding `T`, because the fetch is keyed on `p`, not on `T`) and convert the equivocation fork into a deterministic halt that the detector can adjudicate within one view. The cost is bounded buffer growth: QCs are held until their parents arrive, and under sustained partition the buffer grows at the proposal rate. We cap the buffer at `2 * quorum` entries per `node_id` and drop oldest-by-view on overflow, since a dropped QC will be re-delivered by the next view's leader. The invariant to encode in the agent's state machine: **apply only when `epoch_match ∧ parent_present ∧ no_conflict`; on any failure, the agent's state is `BUFFERED`, `HALTED`, or `RESYNCING` — never `APPLIED` and never `BLOCKED`.**

```python
from dataclasses import dataclass
from enum import Enum


class ApplicabilityError(RuntimeError):
    """Raised when a QC cannot be applied to the local task graph."""


class Disposition(Enum):
    APPLY = "apply"
    BUFFER = "buffer"
    HALT = "halt"
    RESYNC = "resync"


@dataclass(frozen=True)
class QC:
    node_id: str
    parent_hash: str
    payload_hash: str
    view: int
    validator_epoch: int


@dataclass
class LocalGraph:
    nodes: dict          # hash -> node
    applied: dict        # node_id -> (view, payload_hash)
    highest_view: int
    validator_epoch: int


def classify(qc: QC, g: LocalGraph) -> Disposition:
    if qc.validator_epoch != g.validator_epoch:
        return Disposition.RESYNC
    prior = g.applied.get(qc.node_id)
    if prior is not None:
        prior_view, prior_payload = prior
        if prior_view >= qc.view and prior_payload != qc.payload_hash:
            return Disposition.HALT
    if qc.parent_hash not in g.nodes:
        if qc.view > g.highest_view:
            return Disposition.RESYNC
        return Disposition.BUFFER
    return Disposition.APPLY


def apply_qc(qc: QC, g: LocalGraph) -> None:
    disp = classify(qc, g)
    if disp is Disposition.APPLY:
        g.nodes[qc.payload_hash] = qc
        g.applied[qc.node_id] = (qc.view, qc.payload_hash)
        g.highest_view = max(g.highest_view, qc.view)
        return
    if disp is Disposition.HALT:
        raise ApplicabilityError(
            f"equivocation on {qc.node_id}: applied "
            f"{g.applied[qc.node_id]} vs certified "
            f"{(qc.view, qc.payload_hash)}"
        )
    if disp is Disposition.RESYNC:
        raise ApplicabilityError(
            f"epoch/view mismatch on {qc.node_id}: "
            f"local_epoch={g.validator_epoch} qc_epoch={qc.validator_epoch} "
            f"local_view={g.highest_view} qc_view={qc.view}"
        )
    # BUFFER: caller is responsible for targeted fetch of qc.parent_hash
```