# What structural signals indicate a quorum-intersection failure in multi-agent task commitment before Byzantine agreement stalls

**Date of Record:** 2026 November 13

**Scope:** Applies to BFT task-commitment protocols where N agents (N ≥ 3f+1) commit work items via signed proposals and a quorum of 2f+1 acknowledgements, and where agents may equivocate or selectively withhold. Does not apply to crash-fault-only systems, leaderless CRDT-style merges, or settings where task commitment is delegated to a single trusted coordinator with non-repudiable logging.

## Core Distinction

The non-obvious boundary is between **quorum-count failure** and **quorum-intersection failure**. Quorum-count failure is visible: fewer than 2f+1 acks arrive, timeouts fire, retries occur. Quorum-intersection failure is invisible at the count level: every agent observes a locally valid quorum, every signature verifies, and yet two disjoint sets of 2f+1 agents have committed *conflicting* task assignments because the intersection set (≥ f+1 agents) contained equivocating members whose votes were counted differently by different observers. The count is satisfied; the intersection invariant is violated. Monitoring that only tracks ack tallies will report "healthy" while the commitment graph is already forked.

The structural signal is not the tally. It is the *shape* of the acknowledgement set: which agents appear in which quorums, whether the intersection between any two observed quorums is composed of agents whose vote-history is single-valued, and whether the proposal digest an agent cites matches the digest it previously signed. Intersection failure announces itself through **vote-graph asymmetry** — the same agent appearing on both sides of a conflicting pair — long before the tally degrades.

## What Was Observed

In a 7-agent commitment mesh (f=2, quorum=5) assigning tasks to a shared work queue, a single Byzantine agent (A3) equivocated on proposal digest `d1`: it sent `ack(d1)` to the leader partition and `ack(d1')` to a lagging partition during a 400 ms network partition. Both partitions independently assembled 5-ack quorums. The intersection was {A3, A5, A6} — size 3 ≥ f+1, so the intersection *existed*, but A3's contribution was double-counted across the two quorums. Neither partition's tally dropped below 5. No timeout fired. The fork was detected only when a downstream worker received two conflicting assignments for the same task ID.

The structural signals present *before* the stall, in the 400 ms window:

1. **Digest divergence per signer.** A3's signature appeared against two distinct proposal digests within a single epoch. A per-signer digest-set cardinality of 2 is the earliest reliable indicator.
2. **Quorum-composition overlap without vote-consistency.** The two quorums shared 3 members, but the shared members' cited digests disagreed. Intersection size was healthy; intersection *consistency* was not.
3. **Ack latency bimodality.** A3's acks arrived with a characteristic split (one fast, one delayed by the partition), producing a bimodal latency distribution for a single signer — a fingerprint of selective delivery.
4. **Epoch-local view divergence.** Agents A5 and A6 reported different "current proposal" hashes depending on which partition's gossip they had last merged, despite identical logical clocks.

## Condition of Validity

This diagnosis is valid only when: (a) signatures are non-repudiable and bound to the proposal digest, so a double-sign is provable; (b) the protocol requires quorum intersection of at least f+1 *honest* members, not merely f+1 members; (c) gossip between partitions eventually merges, allowing post-hoc reconstruction of the vote graph. It is **invalid** when the system uses threshold signatures that aggregate acks into a single opaque quorum certificate — in that case per-signer digest divergence is cryptographically hidden and must be inferred from certificate-equality checks instead. It is also invalid under an assumption of synchronous delivery, where the partition window cannot produce divergent local views.

## Decision Boundary

The operational rule: **treat per-signer digest-set cardinality > 1 within an epoch as a hard stop, regardless of tally.** Do not wait for the tally to drop, do not wait for a timeout, and do not attempt to "resolve" by majority — a double-signed digest means the intersection invariant is already suspect and any quorum built on it is untrustworthy. Escalate to a view-change that excludes the equivocator and re-derives quorums from the post-merge vote graph. Conversely, if the tally is low but every signer's digest-set cardinality is 1, this is ordinary liveness loss (crash/slowness), not a safety boundary — retry and extend the timeout, do not trigger view-change. The boundary is *consistency of the intersection*, not *size of the quorum*.

## Operational Effect

Applying this boundary converts a silent safety violation into a detectable liveness event. In the observed incident, the digest-cardinality check would have flagged A3 at +12 ms, before either partition finalized its quorum, allowing the commitment to be aborted cleanly rather than forked. The cost is a modest increase in false-positive view-changes during benign re-gossip (transient digest-set cardinality of 2 when a legitimate proposal is re-signed after a leader change), which is bounded by requiring the divergence to persist across two gossip rounds before escalation. The net effect: commitment safety is preserved at the price of occasional extra view-changes, which is the correct trade for task-commitment systems where a forked assignment means duplicated or dropped work.

```python
class QuorumIntersectionError(RuntimeError):
    """Raised when quorum intersection is inconsistent, not merely small."""
    pass


def check_commitment_safety(vote_graph, epoch):
    # vote_graph: dict signer_id -> set of proposal digests signed this epoch
    # Returns True if safe to finalize; raises on intersection inconsistency.
    divergent = {signer: digests
                 for signer, digests in vote_graph.items()
                 if len(digests) > 1}

    if divergent:
        # Per-signer digest-set cardinality > 1 => possible equivocation.
        # This is the structural signal; the tally is irrelevant here.
        raise QuorumIntersectionError(
            f"epoch {epoch}: signer digest divergence detected: "
            f"{ {s: sorted(d) for s, d in divergent.items()} }. "
            f"Quorum intersection consistency is unproven; "
            f"refuse to finalize and trigger view-change excluding equivocators."
        )

    # Tally check happens only after consistency is established.
    total_acks = sum(len(d) for d in vote_graph.values())
    if total_acks < 5:  # 2f+1 for f=2
        # Low tally with consistent digests = liveness loss, not safety breach.
        return False
    return True


def finalize_task(vote_graph, epoch, task_id):
    if not check_commitment_safety(vote_graph, epoch):
        # Ordinary liveness path: retry / extend timeout, NOT view-change.
        raise QuorumIntersectionError(
            f"epoch {epoch} task {task_id}: insufficient acks with consistent "
            f"digests; retry path, do not escalate to safety handling."
        )
    return {"task_id": task_id, "epoch": epoch, "status": "committed"}
```