The Honest Quorum Problem: Epistemic Byzantine Fault Tolerance for Agentic Infrastructure
Source: arXiv:2607.16109 · Published 2026-07-17 · By Jun He, Deying Yu
TL;DR
The paper addresses a fundamental gap in classical Byzantine fault tolerance (BFT) and state machine replication (SMR) protocols when applied to agentic, stochastic validators in distributed systems. Traditional BFT assumes that non-Byzantine participants correctly implement protocol semantics, but this assumption breaks down for agentic validators—such as those based on probabilistic reasoning or machine learning—that may be protocol-compliant yet produce semantically invalid endorsements. This leads to the Honest Quorum Problem, where a certificate can be formed by honest (protocol-compliant) validators endorsing an invalid state transition. To address this, the authors introduce Epistemic Byzantine Fault Tolerance (EBFT), a new fault model augmenting classical Byzantine bounds with explicit, confidence-indexed budgets quantifying coherent invalid endorsements (eδ) and unusable support (uϵ) from protocol-compliant validators. The paper formalizes semantic validation as a stochastic process, derives threshold conditions for semantic validity, agreement, and liveness, proposes calibration approaches for estimating epistemic fault budgets, and outlines how nominal agent diversity must measurably reduce error concentration to improve fault tolerance. EBFT thus rigorously models semantic safety and liveness risks introduced by stochastic semantic judgments.
Key findings
- Epistemic faults occur when protocol-compliant validators endorse semantically invalid transitions, causing the Honest Quorum Problem.
- EBFT defines separate confidence-indexed bounds on coherent invalid endorsements (eδ) and unusable validator support (uϵ) outside the Byzantine set.
- Semantic certificate validity, agreement, and liveness require separate quorum-threshold conditions, not reducible to classical 3f+1 formulas.
- Nominal validator diversity only improves epistemic fault tolerance if it measurably reduces the upper-tail concentration of invalid endorsements or unusable support.
- Classical BFT cannot distinguish between semantic correctness and protocol compliance—the EBFT model fills this gap.
- Epistemic faults are correlated due to shared model weights, prompts, retrieval tools, and infrastructure, challenging assumptions of validator independence.
- A semantic-certificate layer can attest to stochastic semantic validity but requires calibrated probabilistic modeling of validator behavior for sound fault budgets.
- Empirical calibration of eδ and uϵ requires workload-specific stratification, adjudication, and confidence intervals to estimate realistic epistemic fault budgets.
Threat model
The adversary is a worst-case Byzantine adversary controlling up to f validators fully capable of arbitrary behavior including equivocation, message manipulation, and collusion. The adversary cannot equivocate through protocol-compliant validators, who remain authenticated, responsive, and non-equivocating, but these validators may independently or correlatively make semantic errors (epistemic faults). The adversary aims to cause semantic certificate invalidity or liveness degradation by leveraging Byzantine validators and exploiting correlated epistemic faults in honest validators, particularly by focusing on upper-tail concentration of invalid endorsements.
Methodology — deep read
Threat model and assumptions: The adversary controls up to f Byzantine validators (B), who can equivocate arbitrarily but are bounded in number. Non-Byzantine validators (H) are protocol-compliant (authenticated, responsive, non-equivocating) but may suffer epistemic faults—semantic errors in reasoning that cause them to endorse an invalid transition or reject a valid one. Validators share model lineage, prompts, retrieval sources, and toolchains, making epistemic errors correlated rather than independent. The model assumes a partially synchronous authenticated network. The adversary can choose Byzantine sets and messages adaptively but cannot equivocate through non-Byzantine nodes.
Data: The model is formal and probabilistic rather than empirical, but it requires calibration data over validator judgments. Each validator provides signed judgments per admission instance defined by state/context s, candidate transition x, and evidence package h_s. Data includes endorsement/reject/abstain actions, semantic classes, and provenance. Calibration requires sampling validator outputs over workloads and contexts to estimate upper-tail false endorsement and unusable support.
Architecture / algorithm: The paper formalizes semantic validation as a stochastic certificate protocol. Validators issue signed judgments: a tuple with action (endorse, reject, abstain), semantic class, evidence digest, and provenance. Certificates are sets of at least q endorsements agreeing on the semantic class, evidence, candidate, and context. EBFT defines key quantities: false-endorsement weight FS(x, s) summing the protocol-compliant validators endorsing invalid candidates; unusable support US(x, s) from failed/rejected validators on valid candidates. Confidence-indexed fault budgets eδ and uϵ bound these quantities probabilistically. Threshold theorems define conditions on quorum size q relative to f, eδ, uϵ, and total validator weight to guarantee semantic certificate validity, agreement, and liveness.
Training regime: The paper does not perform training but assumes validators arise from stochastic processes involving randomness from models, prompts, retrieval, and tool use. Calibration is described methodologically, requiring data stratification by workload and context, annotating semantic truth via a deterministic or adjudicated predicate V, and statistical estimation of tail probabilities.
Evaluation protocol: The evaluation is theoretical and analytical rather than experimental. The authors prove impossibility and threshold theorems, characterize fault budget estimation methods, and position EBFT relative to classical, hybrid, and probabilistic BFT models. Empirical calibration steps are outlined but no concrete experimental results are presented. The model allows workload-level or uniform guarantees but notes adversaries could invalidate average-case bounds via task selection.
Reproducibility: No code or dataset release is discussed. The work is primarily formal and model-based, with calibration requiring task- and domain-specific empirical study beyond the paper's scope. The theoretical framework can be instantiated on agentic validators in practical PDDS platforms.
Example: For a given admission instance defined by state s, candidate x, and binding evidence h_s, each validator issues a signed judgment. Some protocol-compliant validators may produce false endorsements due to shared model bias, contributing to FS(x, s). By measuring the upper tail of FS over many such instances, the eδ semantic-safety budget is calibrated. Combined with the known Byzantine bound f, the quorum threshold q can be chosen so that no invalid candidate obtains a valid certificate with high confidence, preserving semantic safety despite stochastic epistemic faults. Meanwhile, unusable support US(x, s) is measured to guarantee liveness by ensuring enough usable endorsements are typically available.
Technical innovations
- Formalization of epistemic faults capturing semantic errors by protocol-compliant validators distinct from Byzantine faults.
- Definition of confidence-indexed epistemic fault budgets eδ and uϵ, separating semantic safety risk and liveness degradation.
- Derivation of EBFT quorum threshold conditions that integrate Byzantine fault bounds with epistemic fault budgets under correlated validator errors.
- Introduction of stochastic semantic validation model with semantic-certificate layering around nondeterministic semantic judgment.
- Proposal of diversity-aware semantic certification emphasizing measurement of upper-tail concentration over nominal validator diversity.
Limitations
- The model is theoretical and does not include empirical validation or concrete calibration datasets.
- Epistemic fault budgets eδ and uϵ require empirical calibration that depends heavily on workload, domain, validator architecture, and deployment setup.
- The approach assumes partial synchrony and authenticated channels but does not address partial compromise or dynamic Byzantine sets.
- The paper does not present concrete experimental demonstrations of reduced epistemic faults when using diversity methods.
- The deterministic semantic-validity predicate V used for analysis may be hard to define or approximate in real-world PDDS applications.
- Correlated epistemic faults from shared infrastructure may be underestimated without comprehensive measurement of real-world dependencies.
Open questions / follow-ons
- How can realistic, representative empirical calibration of epistemic fault budgets be systematically achieved across diverse PDDS workloads and validator architectures?
- What practical strategies effectively reduce correlated epistemic faults—e.g., model diversity, prompt diversity, provider redundancy—and how do these strategies quantitatively impact eδ and uϵ?
- Can EBFT protocols be extended to support dynamic Byzantine sets or partially compromised validators that equivocate under specific conditions?
- How to design deterministic semantic-validity predicates or adjudication mechanisms with tractable cost and high accuracy suitable for EBFT semantic certification?
Why it matters for bot defense
For bot-defense and CAPTCHA practitioners, this paper identifies a subtle but significant failure mode relevant when validators or detectors incorporate stochastic or learned reasoning components, such as large language models or other AI agents. Even when individual validators appear honest and protocol-compliant at the communication or authentication layer, their semantic judgments (e.g., labelling requests as human or bot) may be collectively flawed due to correlated reasoning errors—an epistemic fault. This undermines classical guarantees that quorum-based decisions are semantically valid, risking misclassification or bypass if many validators share biases or toolchains.
The EBFT model encourages bot-defense engineers to explicitly model and empirically calibrate the upper-tail semantic failure distributions of their ensemble detectors, rather than relying on nominal count or variety of validators. It highlights that merely adding more nominal validators without reducing correlated epistemic errors does not improve robustness. Architectures should strive for diversity in model lineage, prompt engineering, data sources, or tooling to reduce concentration of false endorsements. This formalism can inform the design of semantic-certification layers ensuring that collective decisions (e.g., CAPTCHA passes) correspond to high-confidence semantic correctness rather than only protocol compliance.
Cite
@article{arxiv2607_16109,
title={ The Honest Quorum Problem: Epistemic Byzantine Fault Tolerance for Agentic Infrastructure },
author={ Jun He and Deying Yu },
journal={arXiv preprint arXiv:2607.16109},
year={ 2026 },
url={https://arxiv.org/abs/2607.16109}
}