# Where must an instance of Byzantine Fault-Tolerant Consensus Among LLM Agents for Shared State and Task Commitment Draw the Line Between Dissent and Defection

**Date of Record:** 2026 November 14

**Scope:** Applies to multi-agent systems where N ≥ 3f+1 LLM agents commit to shared task state (task ownership, completion claims, resource reservations) under a BFT protocol with signed message logs. Does not apply to single-agent orchestration, to stateless request routing, or to systems where agents share a single underlying model instance with no independent sampling.

## Core Distinction

The non-obvious boundary is between **semantic dissent** and **protocol defection**. Classical BFT theory treats any message that deviates from the protocol specification as Byzantine behavior, and quorum logic is designed to tolerate f such deviations. LLM agents, however, produce a third category: messages that are *protocol-conformant in form* (correct signatures, valid schema, committed to a log) but *semantically divergent in content* because the agent's sampling produced a different but internally coherent interpretation of the task. A quorum of such agents is not a Byzantine coalition; it is a correlated-sampling artifact. The failure mode is that the consensus layer cannot distinguish "3 agents disagree because they sampled different reasoning traces" from "3 agents are colluding to defect," and the standard response—treating the minority as faulty and excluding it—silently converts dissent into defection by forcing the divergent agents to either recant (losing their genuine signal) or be slashed (losing their stake). The invariant that must hold is: **a quorum must be a quorum of independently-derived commitments, not a quorum of identical outputs.** When the latter is enforced, the system's fault tolerance is an illusion—it tolerates only faults that manifest as *different* outputs, and fails catastrophically on faults that manifest as *same* outputs (correlated hallucination, shared prompt injection, common training-data poisoning).

## What Was Observed

In a 7-agent BFT deployment (f=2 tolerance) committing task-ownership claims to a shared ledger, a prompt-injection payload embedded in a shared task description caused 5 of 7 agents to independently produce the identical malicious commitment: reassigning a resource lock to an attacker-controlled agent ID. The 5 agents were not colluding—each derived the commitment from the same poisoned context via independent sampling, and each signed a well-formed message. The 2 honest agents produced the correct commitment. The BFT layer, seeing a 5-of-7 supermajority with valid signatures, committed the malicious state. The 2 dissenters were flagged as faulty and excluded. The system's 2-fault tolerance was fully consumed by *agreement*, not by *fault*: the correlated input made agreement the attack vector. A second observation: when the 2 dissenters were later re-admitted and re-queried with a *clean* context, they produced the correct commitment, confirming they were never Byzantine—they were correct agents whose signal was suppressed by the quorum rule.

## Condition of Validity

The standard BFT safety argument (N ≥ 3f+1 guarantees agreement and validity in the presence of f Byzantine nodes) holds only under the **independent-fault assumption**: that faulty nodes fail independently, so the probability of f+1 correlated faults is negligible. For LLM agents this assumption is violated whenever agents share *any* input channel: a common task description, a shared retrieval corpus, a shared system prompt, a shared model family, or a shared tool output. The condition of validity for BFT consensus among LLM agents is therefore: **the fault model must be correlated-fault-aware, and the quorum threshold must be computed over *distinct provenance* of inputs, not merely over distinct agent identities.** Concretely, if k agents share an input source, they must be treated as a single fault domain of weight 1, not k. The effective fault tolerance is N_distinct ≥ 3f+1 where N_distinct counts input-provenance clusters, not agents. This is the boundary: the moment two agents' commitments are conditioned on the same unverified input, their votes are no longer independent, and the quorum arithmetic silently overcounts.

## Decision Boundary

An operator must refuse to commit shared state when the supermajority's votes cannot be traced to at least 2f+1 *provenance-distinct* input clusters. The decision rule is:

- If the winning quorum's votes share a single input-provenance cluster, **do not commit**—the agreement is an artifact of correlated input, not independent verification. Escalate to a re-query with provenance-diversified context.
- If the winning quorum spans ≥ 2f+1 provenance clusters, commit normally.
- If the dissenting minority's votes trace to a *different* provenance cluster than the majority's, treat the dissent as a **validity challenge**, not as fault—the minority may be the honest signal. Do not slash; re-query both clusters against a neutral context and compare.
- Only when a vote is traceable to *no* valid input cluster (fabricated provenance, signature mismatch, schema violation) is it Byzantine and slashable.

The non-obvious part: the majority is not presumptively correct. In correlated-input attacks the majority is the *attack surface*, and the minority is the *integrity signal*. The decision boundary inverts the classical "majority wins" heuristic.

## Operational Effect

Enforcing provenance-aware quorum accounting changes three operational behaviors. First, commit latency rises because provenance clustering must be computed before quorum evaluation—budget ~1 extra round-trip per commit for cluster hashing. Second, the effective fault tolerance drops from N ≥ 3f+1 agents to N_distinct ≥ 3f+1 provenance clusters, which for a homogeneous agent fleet sharing one model and one retrieval corpus may be as low as 1—meaning the system has *zero* real BFT tolerance and must be treated as a single-node trust domain with replication for availability only, not for integrity. Third, slashing logic must be gated on provenance-validity checks, otherwise honest dissenters are penalized and the system learns to suppress the only signal that detects correlated-input attacks. The net effect: a BFT-LLM system that does not track input provenance has a fault-tolerance number that is a fiction, and the fiction is most dangerous precisely when the system reports full health—because correlated agreement looks identical to healthy consensus until the malicious commitment is already durable.

```python
from dataclasses import dataclass
from collections import defaultdict


class CorrelatedQuorumError(RuntimeError):
    """Raised when a quorum's votes are not provenance-distinct."""
    pass


@dataclass(frozen=True)
class Vote:
    agent_id: str
    commitment: str
    provenance_cluster: str  # hash of the input corpus the agent conditioned on
    signature_valid: bool


def evaluate_quorum(votes: list[Vote], f: int) -> str:
    # Only protocol-conformant votes enter the quorum.
    valid = [v for v in votes if v.signature_valid]
    if not valid:
        raise CorrelatedQuorumError("no protocol-conformant votes")

    # Group by commitment, then count DISTINCT provenance clusters per commitment.
    by_commitment: dict[str, set[str]] = defaultdict(set)
    for v in valid:
        by_commitment[v.commitment].add(v.provenance_cluster)

    required_clusters = 2 * f + 1
    for commitment, clusters in by_commitment.items():
        if len(clusters) >= required_clusters:
            return commitment

    # No commitment reached provenance-distinct supermajority.
    # Diagnose the most common failure: a large vote count that collapses
    # to a single provenance cluster (correlated-input agreement).
    top_commitment = max(by_commitment, key=lambda c: len(by_commitment[c]))
    top_clusters = by_commitment[top_commitment]
    raw_support = sum(1 for v in valid if v.commitment == top_commitment)
    if raw_support >= required_clusters and len(top_clusters) < required_clusters:
        raise CorrelatedQuorumError(
            f"commitment '{top_commitment}' has {raw_support} raw votes but only "
            f"{len(top_clusters)} provenance cluster(s); required {required_clusters}. "
            f"Agreement is an artifact of correlated input, not independent verification."
        )
    raise CorrelatedQuorumError(
        f"no commitment reached {required_clusters} provenance-distinct clusters"
    )


def commit_shared_state(votes: list[Vote], f: int) -> str:
    try:
        return evaluate_quorum(votes, f)
    except CorrelatedQuorumError as e:
        # Do NOT commit; escalate to provenance-diversified re-query.
        raise CorrelatedQuorumError(f"commit refused: {e}") from e
```