The Honest Quorum Problem: Epistemic Byzantine Fault Tolerance for Agentic Infrastructure

• URL: http://arxiv.org/abs/2607.16109v1
• Date: Fri, 17 Jul 2026 16:43:00 GMT
• Title: The Honest Quorum Problem: Epistemic Byzantine Fault Tolerance for Agentic Infrastructure
• Abstract summary: State machine replication (SMR) and Byzantine fault-tolerant (BFT) consensus guarantee agreement despite a bounded number of faulty participants.<n>Agentic validators expose a weaker boundary: an authenticated, responsive, non-equivocating, and protocol-compliant reasoning participant may still endorse a semantically invalid transition.<n>We define Epistemic Byzantine Fault Tolerance (EBFT), a fault-tolerance model for agentic infrastructure and post-deterministic distributed systems.
• Score: 2.124730017640531
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: State machine replication (SMR) and Byzantine fault-tolerant (BFT) consensus guarantee agreement despite a bounded number of arbitrary, colluding faulty participants. However, these guarantees rely on participants outside this set correctly executing the protocol's transition semantics. Agentic validators expose a weaker boundary: an authenticated, responsive, non-equivocating, and protocol-compliant reasoning participant may still endorse a semantically invalid transition due to reasoning errors. We call this failure mode an epistemic fault, and the collective phenomenon the Honest Quorum Problem (where "honest" means protocol-compliant, not semantically correct). Such a quorum can satisfy ordinary checks while forming a certificate for an invalid transition. Thus, agreement alone does not guarantee semantic validity or execution safety. Furthermore, because agentic validators often share model weights, training distributions, prompts, or toolchains, they are highly susceptible to correlated epistemic faults. We define Epistemic Byzantine Fault Tolerance (EBFT), a fault-tolerance model for agentic infrastructure and post-deterministic distributed systems. EBFT augments the conventional Byzantine fault bound with two separate, confidence-indexed quantities: $e_δ$ bounds coherent invalid endorsements outside the Byzantine set, and $u_ε$ bounds unusable validator support that degrades liveness. These quantities characterize semantic safety risk and liveness degradation independently. We derive quorum-threshold conditions for semantic validity, consensus agreement, liveness, and feasible threshold selection, and outline a calibration methodology for estimating these budgets. We show that adding nominally distinct agents improves fault tolerance only when it measurably reduces the upper-tail concentration of invalid endorsements or unusable support.

Related papers

• A distribution-free certification framework for trustworthy crash-severity prediction [1.089614199781423]
  We develop a certification layer that wraps any severity model unmodified.<n>On 5.2 million Texas records across seven base models spanning four decades, the layer attaches identical validity.<n>The framework is released as an open-source package with theorem-level tests.
  arXiv  Detail & Related papers  (2026-09-10T14:20:08Z)
• ECO/CPO-DAG: A Contradiction-Based Accountability Layer for Adversarial Supply Chains [0.0]
  ECO/CPO-DAG is a domain-specific accountability protocol for adversarial supply chains.<n>It formalizes contradiction detection as a supplemental validation layer.<n>The protocol's boundary is explicit: it detects provable contradictions, not consistent lies.
  arXiv  Detail & Related papers  (2026-07-07T21:03:26Z)
• Denoised Conformal Alignment for Reliable Selection of Conditional Average Treatment Effect Predictions [10.945117945979566]
  We study reliable selection for black-box CATE predictors.<n>We construct doubly robust proxy errors from pseudo-outcomes.<n>We propose Denoised Conformal Alignment.
  arXiv  Detail & Related papers  (2026-07-03T10:00:28Z)
• Semantic Quorum Assurance: Collective Certification for Non-Deterministic AI Infrastructure [2.124730017640531]
  We introduce Quorum Semantic Assurance (SQA), a control-plane primitive for governing non-deterministic agentic infrastructure.<n>SQA represents proposals as declarative execution contracts bound to cryptographic evidence chains and routes them to a diverse panel of read-only, sandboxed validator agents.<n>On 500 infrastructure-inspired mutation scenarios, with safety results reported on held-out safe/unsafe trials excluding ambiguous scenarios, SQA reduces unsafe approval from 18.5% for single-agent validation to 0.3%.
  arXiv  Detail & Related papers  (2026-06-06T07:31:04Z)
• IMPACT-CYCLE: A Contract-Based Multi-Agent System for Claim-Level Supervisory Correction of Long-Video Semantic Memory [73.22944697933603]
  Existing pipelines produce opaque, end-to-end outputs that expose no intermediate state for inspection.<n>We present IMPACT-Cycle, a supervisory multi-agent system that reformulates long-video understanding as a multimodal iterative claim-level maintenance.
  arXiv  Detail & Related papers  (2026-04-22T03:03:33Z)
• Preregistered Belief Revision Contracts [2.28438857884398]
  We introduce PBRC (Preregistered Belief Revision Contracts), a protocol-level mechanism that separates open communication from admissible change.<n>A PBRC contract publicly fixes first-order evidence triggers, admissible revision operators, a priority rule, and a fallback policy.<n>We show that auditable trigger protocols admit evidential PBRC normal forms that preserve belief trajectories and canonicalized audit traces.
  arXiv  Detail & Related papers  (2026-04-16T22:22:54Z)
• Byzantine-Robust and Differentially Private Federated Optimization under Weaker Assumptions [89.52532304099522]
  Federated Learning (FL) enables clients to collaboratively train a shared model without centralizing their raw data, offering an inherent level of privacy.<n> gradients and model updates can still leak sensitive information, while malicious servers may mount adversarial attacks such as Byzantine manipulation.<n>These vulnerabilities highlight the need to address differential privacy (DP) and Byzantine robustness within a unified framework.<n>We propose Byz-Clip21-SGD2M, a new algorithm that integrates robust aggregation with double momentum and carefully designed clipping.
  arXiv  Detail & Related papers  (2026-03-24T17:39:09Z)
• LATA: Laplacian-Assisted Transductive Adaptation for Conformal Uncertainty in Medical VLMs [61.06744611795341]
  Medical vision-language models (VLMs) are strong zero-shot recognizers for medical imaging.<n>We propose texttttextbfLATA (Laplacian-Assisted Transductive Adaptation), a textittraining- and label-free refinement.<n>texttttextbfLATA sharpens zero-shot predictions without compromising exchangeability.
  arXiv  Detail & Related papers  (2026-02-19T16:45:38Z)
• A Coin Flip for Safety: LLM Judges Fail to Reliably Measure Adversarial Robustness [57.510025257780306]
  We show that existing validation protocols fail to account for substantial distribution shifts inherent to red-teaming.<n>We propose ReliableBench, a benchmark of behaviors that remain more consistently judgeable, and JudgeStressTest, a dataset designed to expose judge failures.
  arXiv  Detail & Related papers  (2026-02-04T15:13:35Z)
• Trusted Uncertainty in Large Language Models: A Unified Framework for Confidence Calibration and Risk-Controlled Refusal [31.458406135473805]
  We present UniCR, a unified framework that turns heterogeneous uncertainty evidence into a calibrated probability of correctness.<n>UniCR learns a lightweight calibration head with temperature scaling and proper scoring.<n>Experiments on short-form QA, code generation with execution tests, and retrieval-augmented long-form QA show consistent improvements in calibration metrics.
  arXiv  Detail & Related papers  (2025-09-01T13:14:58Z)
• COIN: Uncertainty-Guarding Selective Question Answering for Foundation Models with Provable Risk Guarantees [51.5976496056012]
  COIN is an uncertainty-guarding selection framework that calibrates statistically valid thresholds to filter a single generated answer per question.<n>COIN estimates the empirical error rate on a calibration set and applies confidence interval methods to establish a high-probability upper bound on the true error rate.<n>We demonstrate COIN's robustness in risk control, strong test-time power in retaining admissible answers, and predictive efficiency under limited calibration data.
  arXiv  Detail & Related papers  (2025-06-25T07:04:49Z)
• TrustLoRA: Low-Rank Adaptation for Failure Detection under Out-of-distribution Data [62.22804234013273]
  We propose a simple failure detection framework to unify and facilitate classification with rejection under both covariate and semantic shifts.<n>Our key insight is that by separating and consolidating failure-specific reliability knowledge with low-rank adapters, we can enhance the failure detection ability effectively and flexibly.
  arXiv  Detail & Related papers  (2025-04-20T09:20:55Z)
• Robustness and Accuracy Could Be Reconcilable by (Proper) Definition [109.62614226793833]
  The trade-off between robustness and accuracy has been widely studied in the adversarial literature. We find that it may stem from the improperly defined robust error, which imposes an inductive bias of local invariance. By definition, SCORE facilitates the reconciliation between robustness and accuracy, while still handling the worst-case uncertainty.
  arXiv  Detail & Related papers  (2022-02-21T10:36:09Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.