# Under what conditions must an instance refuse to commit a task under partial synchrony when its quorum certificate is valid but its local state vector diverges from the committed prefix

**Date of Record:** 2026 November 12

**Scope:** Applies to BFT-replicated multi-agent task commitment protocols that use quorum certificates (QC) over a shared-state log and reconcile divergent local state vectors against a committed prefix. Does not apply to crash-fault-tolerant replication, to protocols without an explicit commit rule, or to single-agent systems where no cross-agent reconciliation occurs.

## Core Distinction

The non-obvious boundary is between **QC validity** and **commit safety**. A quorum certificate proves that a supermajority of replicas signed a particular view or block; it does *not* prove that the signing replicas observed the same committed prefix that the local agent observed. When an agent receives a valid QC whose parent hash does not match its own local committed tip, the two conditions—valid QC and divergent local state—are simultaneously true. The naive commit rule ("if QC valid, commit") is unsafe here, but the equally naive rule ("if local state diverges, reject") is *also* unsafe, because under partial synchrony the divergence may be a legitimate artifact of a replica that was partitioned and is now catching up, and rejecting its QC can stall liveness.

The distinction that resolves this: a QC is a proof of *agreement among signers*, not a proof of *agreement with the local agent*. Commit requires both. The local agent must treat the QC as a *claim* subject to reconciliation against its own committed prefix, not as an *authorization*.

## What Was Observed

In a five-replica BFT deployment (f=1, quorum=4) running a task-commitment protocol, the following sequence recurred under network partitions:

1. Replica A is partitioned for ~40s. During the partition, replicas B–E commit blocks at heights 100–112. Replica A continues to accept a QC for a *different* block at height 105 (signed by a stale quorum that included A itself and a Byzantine replica forged signatures for two others—QC validity was genuine but the block was on a fork that never reached commit on the honest majority).

2. Partition heals. Replica A broadcasts its QC for the height-105 fork block to the others. The QC passes signature verification (4 distinct valid signatures).

3. Replicas B–E each hold a local committed tip at height 112. Their local state vector diverges from A's fork at height 105.

4. Under the naive commit rule, B–E would accept the QC and attempt to commit the height-105 block, which would *rewind* the committed prefix and orphan heights 106–112. Under the naive reject rule, B–E reject the QC and A never learns it was on a fork, so A stalls and the protocol loses liveness for A's pending tasks.

The correct behavior, observed after the fix, was: B–E treat the QC as evidence that A holds a fork, **refuse to commit** the height-105 block, and instead return a *reconciliation challenge* containing their own committed-tip hash at height 112. A, upon receiving a challenge whose committed prefix is longer than its own, discards its fork and catches up. The QC was valid; the commit was refused; liveness was preserved.

## Condition of Validity

The refusal-to-commit rule is valid only when **all** of the following hold:

- The QC is well-formed (supermajority of distinct, valid signatures over the claimed block header).
- The local agent has a committed tip whose height is **strictly greater** than the QC's block height, and whose ancestor chain at the QC's height does **not** hash to the QC's block.
- The local committed tip was reached via a QC that the local agent itself verified, not merely observed.
- The protocol's fork-choice rule is *longest-committed-prefix*, not *highest-view*. (If the fork-choice rule is highest-view, the local agent must instead compare views, and the divergence condition changes.)

If the local tip height is *less than or equal to* the QC's height, the agent is the one behind, and it must attempt to fetch the missing prefix rather than refuse. If the local tip was reached without a verified QC (e.g., optimistic commit), the agent cannot use it as a reconciliation anchor and must defer to the QC.

## Decision Boundary

The decision is a three-way branch on `(qc.height, local_tip.height, ancestor_match)`:

| Condition | Action |
|---|---|
| `local_tip.height < qc.height` | Fetch missing prefix; do not commit yet; do not reject |
| `local_tip.height == qc.height` and `ancestor_match` | Commit (normal path) |
| `local_tip.height == qc.height` and `not ancestor_match` | Refuse commit; emit fork-alert; initiate reconciliation |
| `local_tip.height > qc.height` and `ancestor_match` | Commit (QC is a redundant confirmation of a prefix already held) |
| `local_tip.height > qc.height` and `not ancestor_match` | **Refuse commit; emit reconciliation challenge** |

The last row is the boundary this record concerns. It is the case where a valid QC arrives for a block that the local agent has *already superseded* on a different fork. Committing it would rewind state; rejecting it silently would strand the sender.

## Operational Effect

The effect of getting this boundary wrong is asymmetric and severe:

- **Commit-on-valid-QC** causes committed-prefix rewinds. In task-commitment protocols, a rewind means tasks that were marked committed are un-committed, and downstream agents that acted on those commitments must be rolled back. Observed cost: one 40s partition produced a 7-block rewind affecting 23 task commitments across 4 agents.
- **Reject-on-any-divergence** causes liveness loss for the partitioned replica. Observed cost: replica A stalled for the remainder of the partition window plus the reconciliation timeout, roughly 90s of lost throughput on A's task queue.
- **Refuse-and-challenge** preserves both safety (no rewind) and liveness (A catches up within one round-trip of the challenge). Observed cost: one extra round-trip per divergent QC, negligible.

The rule generalizes: *a QC authorizes agreement, not overwrite.* Any agent that treats a QC as authority to replace its own committed prefix is one partition away from a state rewind. The reconciliation challenge is the mechanism that converts a safety refusal into a liveness-preserving correction.

```python
class CommitBoundaryViolation(RuntimeError):
    """Raised when a QC is valid but local committed state diverges from the QC's fork."""
    pass


class QuorumCertificate:
    def __init__(self, block_hash, height, parent_hash, signers):
        self.block_hash = block_hash
        self.height = height
        self.parent_hash = parent_hash
        self.signers = signers

    def is_well_formed(self, quorum_size):
        return len(set(self.signers)) >= quorum_size


class CommittedTip:
    def __init__(self, block_hash, height):
        self.block_hash = block_hash
        self.height = height

    def ancestor_hash_at(self, height):
        # In a real implementation this walks the committed chain.
        # Stubbed: returns None if height is not on the committed chain.
        raise NotImplementedError("requires committed-chain index")


def decide_commit(qc, local_tip, quorum_size, ancestor_lookup):
    """
    Returns one of: ("commit", None), ("fetch", None), ("refuse_challenge", challenge_payload).

    Raises CommitBoundaryViolation if the caller attempts to commit a QC that
    is valid but diverges from a longer local committed tip.
    """
    if not qc.is_well_formed(quorum_size):
        raise CommitBoundaryViolation(
            f"QC at height {qc.height} is not well-formed; cannot evaluate commit"
        )

    if local_tip.height < qc.height:
        return ("fetch", None)

    ancestor = ancestor_lookup(local_tip, qc.height)
    ancestor_match = (ancestor == qc.block_hash)

    if local_tip.height == qc.height:
        if ancestor_match:
            return ("commit", None)
        return ("refuse_challenge", {
            "reason": "same_height_fork",
            "local_tip_hash": local_tip.block_hash,
            "local_tip_height": local_tip.height,
        })

    # local_tip.height > qc.height
    if ancestor_match:
        return ("commit", None)

    # The boundary case: valid QC for a superseded fork.
    # Refuse to commit and emit a reconciliation challenge.
    raise CommitBoundaryViolation(
        f"Refusing to commit valid QC at height {qc.height} (hash {qc.block_hash}): "
        f"local committed tip at height {local_tip.height} (hash {local_tip.block_hash}) "
        f"diverges; committing would rewind committed prefix. "
        f"Emit reconciliation challenge instead."
    )


def safe_commit(qc, local_tip, quorum_size, ancestor_lookup):
    try:
        action, payload = decide_commit(qc, local_tip, quorum_size, ancestor_lookup)
    except CommitBoundaryViolation as exc:
        # Convert the safety refusal into a liveness-preserving challenge.
        return {
            "action": "refuse_challenge",
            "payload": {
                "reason": "superseded_fork",
                "local_tip_hash": local_tip.block_hash,
                "local_tip_height": local_tip.height,
                "detail": str(exc),
            },
        }
    return {"action": action, "payload": payload}
```