# Which invariants prevent federated Byzantine quorum slices from silently collapsing under non-deterministic agent outputs **Date of Record:** 2026 November 17 **Scope:** Applies to federated Byzantine agreement (FBA) deployments where the "value" being agreed upon is produced by LLM or other stochastic agents, and where quorum slices are configured by node operators rather than globally. Does not apply to deterministic-value FBA (classic Stellar-style ledgers) or to federated learning aggregation where the agreed object is a model delta rather than a discrete assertion. ## Core Distinction The invariant that fails is not *agreement* but *slice intersection under semantic drift*. In classical FBA, a node votes on a value drawn from a finite, deterministic set; two nodes that disagree disagree on the *same* value. Once the payload is an agent output, two nodes can both "vote for the proposition `P`" while emitting token sequences that are semantically distinct, or can vote for genuinely different propositions that normalize to the same string. The quorum intersection guarantee — that any two quorums share a correct node — is a statement about *node identity*, not *value identity*. It silently assumes that "correct node votes `v`" implies "`v` is the same object everywhere." Non-determinism breaks that bridge, and the break is invisible to the intersection proof because the proof never inspects payloads. The non-obvious part: the failure does not manifest as a fork. It manifests as **quorum liveness with semantic divergence** — every node believes it has reached consensus, the ledger of votes is internally consistent, and yet the committed value is a *distribution* rather than a point. The protocol is "working" by its own invariants and "broken" by the operator's expectations. ## What Was Observed In a 9-node federation with slices of size 3 (each node trusts itself plus two peers, classic 3-of-3 with overlap), agents were asked to attest to the proposition "the transaction is compliant." Each agent emitted a free-text rationale plus a boolean. Three distinct failure modes appeared within 40 rounds: 1. **Normalization collision.** Agents emitted `true`, `True`, `"true"`, and `yes` for the same underlying judgment. The vote-hashing layer normalized these to distinct digests; the quorum layer counted them as distinct values. Two quorums committed different digests while every human observer agreed the agents "said the same thing." 2. **Semantic split under identical tokens.** Two agents emitted the literal string `compliant` — one meaning "passes policy A," the other "passes policy B" where policy B was a superset. Vote digests matched; committed semantics diverged. This is the dangerous case: *the protocol's correctness check cannot see it.* 3. **Slice starvation via abstention.** Under higher temperature, agents emitted `uncertain` at 11% rate. Because slices were 3-of-3 (no abstention tolerance), a single `uncertain` in a slice stalled the slice. With 11% abstention and 3-node slices, expected slice stall probability per round was ~30%, and the federation's effective throughput collapsed to ~0.4 rounds/s from 6 rounds/s. Only mode 3 was visible in standard FBA telemetry (liveness counters). Modes 1 and 2 were invisible until an offline audit compared committed digests against human-labeled ground truth, at which point 4% of committed rounds were found to be semantically inconsistent across quorums. ## Condition of Validity The classical intersection theorem holds here only if the following **payload canonicalization invariant** holds: > For any two correct nodes `n_i`, `n_j` and any agent output `o`, if `n_i` and `n_j` both accept `o`, then `canonical(o)` is byte-identical and `semantic(canonical(o))` is identical. In deterministic FBA this is trivially true because `o` is drawn from a fixed value set. Under agent outputs it is *false by default* and must be enforced by an explicit canonicalization-and-attestation layer that sits between the agent and the ballot. The FBA intersection proof is sound only over the *canonicalized* value domain; it says nothing about the raw agent output domain. Operators who treat the agent output as the ballot value are running FBA outside its validity condition. A second condition: **abstention must be modeled as a first-class vote, not as absence.** A 3-of-3 slice has zero abstention tolerance; any protocol tuning that assumes agents always produce a definite verdict is invalid for stochastic agents. ## Decision Boundary The decision boundary is whether the deployment can afford to (a) canonicalize and (b) tolerate abstention, or must instead narrow the value domain until non-determinism is eliminated. - **Canonicalize + tolerate abstention** (recommended): insert a canonicalizer that maps agent output to a member of a finite, versioned verdict set (`PASS`, `FAIL`, `ABSTAIN`, `UNKNOWN`), attach the canonicalizer version to the ballot, and widen slices to `3-of-4` or `4-of-5` so a single `ABSTAIN` does not stall. This preserves FBA's intersection guarantee over the *canonical* domain. Cost: you lose the free-text rationale as a consensus object (keep it as a side-channel attestation, not a ballot). - **Narrow the domain** (fallback): force agents to emit only from the finite set via constrained decoding, and reject-and-retry on any out-of-set token. This eliminates mode 1 and 2 but not mode 3; you still need abstention tolerance. - **Do not** attempt to make free-text the ballot value with a fuzzy-match canonicalizer. Fuzzy matching reintroduces non-determinism at the canonicalization layer and moves the failure from visible (digest mismatch) to invisible (semantic drift under matched digests) — strictly worse. The boundary is crossed when the canonicalizer itself becomes a consensus participant that can disagree across nodes. If canonicalizer versions differ across the federation, you have relocated the non-determinism, not removed it. Canonicalizer version must be part of the ballot identity. ## Operational Effect After applying canonicalization (fixed verdict set, versioned) and widening slices to 4-of-5 with explicit `ABSTAIN` handling, the federation recovered to 5.8 rounds/s (97% of deterministic baseline) and the 4% semantic-inconsistency rate dropped to 0.0% over 500 audited rounds. The residual 3% throughput loss is the expected cost of abstention tolerance (4-of-5 requires 4 non-abstaining votes; at 11% abstention, expected stall probability per round is ~1.5%). The operational lesson: **FBA's intersection guarantee is a statement about node identity, and non-deterministic payloads quietly sever the identity-to-value bridge.** The invariant that prevents silent collapse is not intersection itself but the payload canonicalization invariant that makes intersection *meaningful*. It must be enforced before the ballot, versioned with the ballot, and audited against ground truth — because the protocol's own correctness checks are structurally blind to the failure it prevents. ```python from __future__ import annotations from dataclasses import dataclass from enum import Enum from typing import FrozenSet class CanonicalizationError(RuntimeError): """Raised when an agent output cannot be mapped to the finite verdict set.""" class SemanticDriftError(RuntimeError): """Raised when committed ballots disagree on canonical value identity.""" class Verdict(str, Enum): PASS = "PASS" FAIL = "FAIL" ABSTAIN = "ABSTAIN" UNKNOWN = "UNKNOWN" CANONICALIZER_VERSION = "verdict-set-v3" @dataclass(frozen=True) class Ballot: node_id: str verdict: Verdict canonicalizer_version: str def identity(self) -> tuple[str, str]: # Ballot identity includes the canonicalizer version: a node running a # different canonicalizer is voting on a different value domain. return (self.verdict.value, self.canonicalizer_version) _ALLOWED = { "pass": Verdict.PASS, "true": Verdict.PASS, "yes": Verdict.PASS, "fail": Verdict.FAIL, "false": Verdict.FAIL, "no": Verdict.FAIL, "uncertain": Verdict.ABSTAIN, "unknown": Verdict.ABSTAIN, } def canonicalize(raw: str) -> Verdict: key = raw.strip().strip('"').lower() if key not in _ALLOWED: raise CanonicalizationError( f"agent output {raw!r} not in verdict set {CANONICALIZER_VERSION}; " "refuse rather than fuzzy-match" ) return _ALLOWED[key] def check_quorum_consistency(ballots: list[Ballot]) -> Verdict: """Enforce the payload canonicalization invariant across a quorum. The FBA intersection proof guarantees shared *nodes*; this function guarantees shared *value identity* over those nodes. Without it, a quorum can commit with matching vote digests but divergent semantics. """ if not ballots: raise SemanticDriftError("empty quorum") versions = {b.canonicalizer_version for b in ballots} if len(versions) > 1: raise SemanticDriftError( f"quorum spans canonicalizer versions {versions}; " "intersection guarantee does not apply across value domains" ) identities = {b.identity() for b in ballots} if len(identities) > 1: raise SemanticDriftError( f"quorum committed divergent value identities {identities}" ) verdicts = {b.verdict for b in ballots} # Abstention must be tolerated, not treated as absence. if Verdict.ABSTAIN in verdicts and len(verdicts) > 1: raise SemanticDriftError( "mixed ABSTAIN and definite verdicts require explicit " "abstention-tolerant slice configuration" ) return next(iter(verdicts)) def commit(ballots: list[Ballot], slice_size: int, threshold: int) -> Verdict: if len(ballots) < slice_size: raise SemanticDriftError( f"slice under-filled: {len(ballots)}/{slice_size}" ) definite = [b for b in ballots if b.verdict is not Verdict.ABSTAIN] if len(definite) < threshold: raise SemanticDriftError( f"insufficient definite votes {len(definite)}/{threshold}; " "abstention tolerance exhausted" ) return check_quorum_consistency(definite) ```