# Why does an instance of Byzantine plan commitment stall at exactly f+1 equivocating agents? A boundary record for multi-agent consensus operators

**Date of Record:** 2026 November 8

**Scope:** Applies to quorum-based BFT commitment protocols (PBFT-style, HotStuff-style, Tendermint-style) used to commit shared multi-agent plans where each agent may broadcast divergent plan fragments to different peers. Does not apply to crash-fault-only consensus, to single-leader replicated state machines without equivocation detection, or to systems where plan fragments are content-addressed and deduplicated before quorum counting.

## Core Distinction

The failure boundary is not "more than f Byzantine agents." It is "any single agent whose equivocating fragments are *individually valid* and *collectively contradictory* under the plan's dependency graph." A plan commitment protocol tolerates up to `f` Byzantine replicas because a quorum of `2f+1` honest replicas can always outvote them. But plan commitment adds a second invariant that pure value consensus does not have: **the committed plan must be internally consistent as a dependency DAG**. Equivocation that is invisible at the vote layer becomes visible only at the plan-merge layer, and the two layers do not share a failure threshold. An instance stalls at exactly `f+1` equivocators when each equivocator's divergent fragments are pairwise mergeable with all honest fragments but not jointly mergeable. This is a *merge-conflict* boundary, not a *quorum* boundary, and it is non-obvious because the vote counts look healthy right up to the moment the commit rule fires.

## What Was Observed

During a 41-agent planning round (tolerating `f=13`) with a HotStuff-derived commit rule, the protocol reached `2f+1` matching `PREPARE` certificates on plan fragment set `S` and emitted a `COMMIT` certificate. The subsequent plan-merge step failed deterministically at every honest replica with a cycle in the dependency graph: fragment `A` from agent 7 declared `A → B`, fragment `B` from agent 7 (sent only to a disjoint peer set) declared `B → A`. Both fragments were byte-valid, both carried valid signatures, and both were included in the quorum certificate's digest because the certificate commits to a *set of fragment hashes* rather than to a *merged DAG*. No single honest replica had seen both fragments before commit; equivocation was only detectable after the fact, and by then the commit certificate was irrevocable under the protocol's own safety proof.

The stall was reproducible at exactly `f+1 = 14` equivocators when the equivocation pattern was a single directed cycle of length 2 per equivocator, distributed across the `f+1` agents so that no honest replica's local view contained a full cycle. At `f = 13` equivocators using the same pattern, at least one honest replica always held both halves of a cycle and could raise a `MergeConflict` before the commit rule fired, converting the failure into an abort. The +1 is the boundary: it is the smallest number of equivocators that can partition the cycle's edges across enough honest views that no honest replica sees a contradiction locally.

## Condition of Validity

This record holds when all of the following are true:

1. The commit rule commits to a *set* of fragment hashes, not to a canonical merged DAG. If the leader constructs the merged DAG before proposing, the boundary moves to the leader and the analysis changes.
2. Fragment validity is checked per-fragment (signature, schema, declared dependency endpoints exist) and not cross-fragment. If cross-fragment consistency is checked at `PREPARE` time by every replica, the boundary drops back to the classical `f` threshold.
3. The equivocation pattern is *view-partitioning*: each equivocator sends fragment `X` to one half of the honest set and fragment `Y` to the complementary half, with `X` and `Y` individually valid and jointly contradictory.
4. The plan dependency graph admits cycles that are not locally detectable — i.e., the merge step is a global operation over the committed set, not a streaming fold.

The record does *not* hold when fragments are content-addressed and deduplicated before quorum counting (equivocation collapses to a single hash), nor when the plan is a linear sequence rather than a DAG (cycles cannot form), nor when `n < 3f+1` (the classical quorum bound dominates and the merge boundary is unreachable).

## Decision Boundary

The operator's decision is not "how many Byzantine agents can we tolerate" but "at what point must we pay for a merged-DAG commit certificate instead of a fragment-set certificate." The boundary sits at `f+1` equivocators with view-partitioned cycles. Below it, per-fragment validation plus honest-replica local cycle detection is sufficient and cheap. At or above it, the protocol must either:

- (a) commit to a canonical merged DAG (leader-side merge, `O(n log n)` per round, moves the attack surface to leader equivocation which is already handled by view-change), or
- (b) require `2f+1` replicas to attest to the *merge result*, not the fragment set, which doubles the certificate size and adds one round-trip.

Choosing (a) or (b) is a latency/throughput trade, not a safety trade. Choosing neither is a latent safety violation that will surface as a post-commit merge abort on the first adversarial plan.

## Operational Effect

In production, this boundary manifests as a *post-commit abort*: the consensus layer reports success, the plan executor reports a dependency cycle, and the system has already spent the round budget. Recovery requires either a protocol upgrade (to a merged-DAG certificate) or an out-of-band re-plan, both of which are visible to downstream agents as a latency spike and a plan-generation retry. The correct operational response is to treat any post-commit merge abort as a *Byzantine equivocation signal*, not a plan-authoring bug, and to escalate the offending agents' fragment hashes to the equivocation evidence log before the next round. Systems that log only the committed fragment set and not the per-replica fragment provenance cannot distinguish this boundary from a benign authoring error and will mis-attribute the failure to the plan generator.

```python
class PlanMergeConflict(RuntimeError):
    """Raised when a committed fragment set cannot be merged into a DAG."""
    pass


def commit_plan(fragment_set, quorum_size, f, equivocation_evidence):
    """
    Commit a plan fragment set under a fragment-set certificate.
    Raises PlanMergeConflict if the committed set is not jointly mergeable,
    which at >= f+1 view-partitioning equivocators is a Byzantine signal,
    not an authoring error.
    """
    if len(fragment_set) < quorum_size:
        raise PlanMergeConflict(
            f"fragment set size {len(fragment_set)} below quorum {quorum_size}"
        )

    # Attempt the global merge; this is the layer where equivocation surfaces.
    try:
        merged = merge_dependency_dag(fragment_set)
    except CycleDetected as exc:
        equivocators = identify_equivocators(equivocation_evidence)
        if len(equivocators) >= f + 1:
            raise PlanMergeConflict(
                f"post-commit merge abort with {len(equivocators)} equivocators "
                f"(>= f+1 = {f + 1}); commit certificate is irrevocable, "
                f"escalate to merged-DAG certificate upgrade. "
                f"Cycle: {exc.cycle}"
            ) from exc
        raise PlanMergeConflict(
            f"merge abort with {len(equivocators)} equivocators (< f+1); "
            f"treat as authoring error and re-plan"
        ) from exc

    return merged
```