🤖 machine learning

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

This paper introduces Epistemic Byzantine Fault Tolerance (EBFT), a new consensus framework for agentic infrastructure that addresses the "Honest Quorum Problem" by extending traditional fault tolerance to account for correlated reasoning errors among protocol-compliant agents, thereby ensuring semantic validity and liveness through confidence-indexed bounds on invalid endorsements and unusable support.

Original authors: Jun He, Deying Yu

Published 2026-07-20

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Jun He, Deying Yu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a world where computers don't just follow rigid, pre-written instructions like a calculator, but instead act like tiny, reasoning employees. These "agentic" computers can look at a messy situation, read a policy, and decide what to do next. But here's the catch: because they use probabilistic reasoning (like guessing the best move in a game), they can sometimes make a "smart" mistake. They might follow all the rules perfectly, sign the right forms, and answer on time, yet still decide to do something dangerous.

To keep these digital employees in line, we use a system called Byzantine Fault Tolerance. Think of this as a super-strict voting club. The club's rule is simple: as long as a certain number of members vote "yes," the decision is final. Traditionally, we assumed that if a member wasn't a "bad guy" (a traitor trying to break the system), they would always vote the correct thing. But what if the "good guys" are all using the same textbook, the same teacher, and the same study guide? They might all agree on the wrong answer, not because they are traitors, but because they all learned the same mistake. This is the scary new problem this paper tackles: a group of honest, rule-following computers agreeing on a disaster.

The Honest Quorum Problem: When Good Guys Agree on the Wrong Thing

This paper, titled The Honest Quorum Problem, dives into a very specific headache for the future of AI and computer networks. It asks: What happens when a group of honest, rule-following AI agents all agree to do something that is actually a terrible idea?

In the old days of computer science, we had a safety net called Byzantine Fault Tolerance (BFT). Imagine a group of generals trying to decide whether to attack a castle. Some generals might be traitors (Byzantine faults) who try to trick the others. The BFT rule says: "As long as we have enough honest generals, we can ignore the traitors and make a safe decision." The key assumption was that the "honest" generals would always know the right answer.

But the authors of this paper point out that this assumption is broken in the age of AI. They introduce a new concept called an Epistemic Fault. "Epistemic" just means "related to knowledge." An epistemic fault happens when an AI agent is perfectly honest—it follows the protocol, signs the digital signature, and doesn't lie—but its reasoning is wrong.

The "Honest Quorum" Scenario
Imagine a committee of seven AI agents (validators) tasked with approving a change to a cloud server.

The Setup: One agent suggests, "Let's give this user the ability to delete all our data."
The Trap: All seven agents are "honest." They aren't traitors. They are all following the rules. But, they all happen to be trained on the same dataset, use the same search tools, and have the same "blind spots."
The Result: All seven agents vote "Yes." They form a perfect Quorum (a majority). The system says, "Great! We have a certificate! Let's do it!"
The Disaster: The system deletes all the data. The protocol worked perfectly, but the meaning of the decision was wrong.

The paper calls this the Honest Quorum Problem. It's a failure where the system is technically "correct" (everyone agreed, signatures are valid) but semantically "broken" (the action is dangerous).

The New Solution: EBFT

The authors propose a new safety model called Epistemic Byzantine Fault Tolerance (EBFT). Instead of just counting heads, EBFT tries to measure how likely it is that the honest agents will all make the same mistake.

They introduce two new "budgets" to manage this risk:

The Safety Budget ( $e_\delta$ ): This is a limit on how many honest agents can falsely agree on a bad idea.
- Analogy: Imagine you are hiring a team of art critics to judge a painting. You know that sometimes, even good critics can be fooled by a fake. The Safety Budget asks: "What is the maximum number of critics who could all be fooled by the same fake painting at the same time?" If your team is too small, or if they all went to the same art school, that number might be too high, and you can't trust their vote.
The Liveness Budget ( $u_\epsilon$ ): This is a limit on how many honest agents might fail to vote at all (by getting confused, timing out, or refusing to answer).
- Analogy: If too many critics are too busy, too confused, or too scared to vote, you can't reach a decision. This budget measures how many "no-shows" or "I don't knows" you can tolerate before the system freezes.

How It Works in Practice

The paper suggests a two-step process to keep things safe:

Step 1: The Calibration (The "Test Drive")
Before you let your AI committee make real decisions, you have to test them. You give them a bunch of practice problems where you know the right answer.

You check: "How often did they all agree on the wrong answer?" (This gives you the Safety Budget).
You check: "How often did they get stuck or refuse to answer?" (This gives you the Liveness Budget).
Crucially, you check if they are actually diverse. If you have seven agents, but they all use the same "brain" (model) and the same "library" (retrieval source), they will likely fail together. The paper argues that just having seven different names isn't enough; you need to prove they don't share the same hidden weaknesses.

Step 2: The Runtime (The "Real Deal")
When a real request comes in, the system checks the test results first.

If the request looks like something the committee hasn't been tested on, or if the test results show the committee is too risky, the system says, "Nope, I'm not voting on this." It might ask a human to step in.
If the request is safe and the committee is ready, it counts the votes. But now, the "passing score" (the threshold) is calculated based on those test budgets, not just a simple math formula like "more than half."

What the Paper Says (and Doesn't Say)

The authors are very careful about what they claim. They prove that:

Just having agreement (everyone voting the same way) does not guarantee the decision is safe.
You cannot rely on simple math (like the old "3f + 1" rule) to fix this. You need to measure the risk of the AI's reasoning.
You need a specific "calibration" process to measure how often the AI agents make correlated mistakes.

They do not claim to have a magic bullet that makes AI perfectly safe. They admit that:

If the AI agents share hidden connections (like the same training data or the same cloud provider), they might still fail together in ways we can't predict.
This system adds extra steps and time (latency) because you have to test and verify before acting.
The "budgets" are estimates based on testing. If the AI gets updated or the world changes, you have to re-test everything.

The Big Takeaway

The paper's main message is a warning and a guide. It warns us that in a world of smart, reasoning AI, being "honest" isn't enough. A group of honest agents can still vote for a disaster if they all think alike.

To fix this, we can't just count votes. We have to measure the quality of the agreement. We need to know: "Are these agents truly independent, or are they just seven clones of the same mistake?" By using these new "budgets" and testing the agents rigorously before letting them vote, we can build systems that are safe even when the agents are imperfect. It's a shift from trusting that "good guys" will always be right, to proving that "good guys" won't all be wrong at the same time.

Technical Summary: The Honest Quorum Problem and Epistemic Byzantine Fault Tolerance

1. Problem Statement: The Honest Quorum Problem

The paper identifies a critical failure mode in distributed systems where "agentic" validators—participants that use stochastic, learned, or generative reasoning to make semantic judgments—operate within a deterministic consensus protocol.

In classical Byzantine Fault Tolerance (BFT), the system assumes that any participant outside a bounded set of "Byzantine" (arbitrarily faulty) nodes is "honest," meaning they correctly implement the protocol's transition or validation semantics. The Honest Quorum Problem weakens this partition. It posits a scenario where a quorum of validators is:

Protocol-compliant: They authenticate correctly, respond within timeouts, follow the voting protocol, and do not equivocate (sign conflicting messages).
Semantically incorrect: Despite protocol compliance, they collectively endorse a state transition that violates an application-level invariant (e.g., granting unauthorized write access).

This failure is termed an epistemic fault. Unlike traditional Byzantine faults, epistemic faults arise from the stochastic nature of the validators' reasoning processes. Multiple protocol-compliant validators may fail coherently because they share underlying dependencies such as model lineage, training distributions, prompt patterns, retrieval sources, toolchains, or provider infrastructure. Consequently, nominal identity diversity does not guarantee epistemic independence.

The paper establishes that protocol agreement does not imply semantic validity, and semantic validity does not imply execution safety. A system can reach a well-formed certificate for an invalid transition if the concentration of protocol-compliant validators endorsing that specific invalid class exceeds the quorum threshold.

2. Methodology: Epistemic Byzantine Fault Tolerance (EBFT)

To address this, the paper defines Epistemic Byzantine Fault Tolerance (EBFT), a fault-tolerance model for "Post-Deterministic Distributed Systems" (PDDS)—systems where deterministic coordination surrounds stochastic semantic judgment.

Core Definitions

EBFT augments the conventional Byzantine fault bound ( $f$ ) with two confidence-indexed quantities that bound the behavior of protocol-compliant validators ( $H$ ):

$e_\delta$ (Semantic-Safety Budget): A bound on the weight of coherent invalid endorsement by protocol-compliant validators outside the Byzantine set. This quantifies the risk that enough honest validators will falsely agree on an invalid transition.
$u_\epsilon$ (Liveness Budget): A bound on unusable support from protocol-compliant validators. This includes false rejections, abstentions, timeouts, divergent outputs, or canonicalization failures that prevent a valid candidate from forming a certificate.

These budgets are defined over a specific workload domain $D$ and are conditional on events $E_\delta$ and $U_\epsilon$ , which hold with probabilities $1-\delta$ and $1-\epsilon$ , respectively.

Threshold Derivation

The paper derives certificate-threshold conditions ( $q$ ) that separate the requirements for safety, agreement, and liveness:

Semantic Certificate Validity: To prevent an invalid candidate from forming a certificate, the threshold must satisfy $q > f + e_\delta$ . This ensures that even if all Byzantine nodes ( $f$ ) and the maximum allowed coherent false endorsements ( $e_\delta$ ) vote for an invalid transition, they cannot reach the quorum.
Agreement: To prevent conflicting certificates, the threshold must satisfy $2q - N > f$ (or $q > (N+f)/2$ ). Crucially, this condition depends only on the Byzantine bound $f$ . Because protocol-compliant validators in EBFT do not equivocate, they do not threaten agreement, even if they are epistemically faulty.
Liveness: To ensure a valid candidate can obtain a certificate, the threshold must satisfy $q \le N - f - u_\epsilon$ . This ensures that the available usable support from honest validators is sufficient to meet the threshold.

The paper proves that a feasible integer threshold $q$ exists only if the system size $N$ satisfies specific population inequalities (e.g., $N > 2f + e_\delta + u_\epsilon$ ).

Calibration and Diversity

The paper emphasizes that "diversity" (different models, providers, or prompts) is not a proof of safety. Instead, diversity is a mechanism to reduce the upper-tail concentration of errors. The methodology requires offline calibration to estimate $e_\delta$ and $u_\epsilon$ empirically for a specific committee configuration.

Risk Profiles: A signed risk profile is generated during calibration, specifying the domain, committee, thresholds, and provenance (model versions, prompts, tools).
Runtime Admission: At runtime, the system checks if the request falls within the calibrated domain and if the risk profile is valid. If the request is valid, the system dispatches isolated validation packages. A certificate is formed only if the number of endorsements meets the pre-calibrated threshold $q$ .
Recalibration: Profiles must expire or be revoked upon model updates, workload shifts, or detection of new common-mode failures.

3. Key Contributions

Formalization of the Honest Quorum Problem: The paper defines a failure mode where protocol-compliant, non-equivocating validators collectively endorse a semantically invalid transition due to correlated epistemic errors.
Definition of EBFT: It introduces a fault model that separates arbitrary Byzantine behavior from confidence-indexed semantic budgets ( $e_\delta$ and $u_\epsilon$ ) for protocol-compliant validators.
Threshold Theorems: It derives necessary and sufficient conditions for semantic certificate validity, agreement, and liveness in PDDS. Notably, it proves that agreement depends solely on the Byzantine bound, while safety and liveness depend on the epistemic budgets.
Diversity-Aware Assurance: It reframes diversity not as a guarantee of independence, but as a variable that must be measured to reduce the upper-tail concentration of invalid endorsement. It outlines a methodology for estimating these budgets via calibration and adversarial testing.

4. Results and Theoretical Bounds

Impossibility Results: The paper proves that without additional semantic grounding (e.g., a validity oracle, trusted verifier, or calibrated concentration bound), no protocol relying solely on agreement signals can guarantee semantic certificate validity. If the distribution of semantic errors is unrestricted, an invalid candidate can satisfy any count-based certificate rule with probability one.
Common-Mode Failure Floor: If a subset of validators shares a latent common-mode failure (e.g., identical model weights), the probability of an unsafe certificate is at least the probability of that common-mode event, regardless of the number of validators.
Threshold Feasibility: The paper provides exact integer formulas for selecting $q$ such that semantic validity, agreement, and liveness are simultaneously satisfied under the defined probabilistic events. It shows that simply reweighting the classical $3f+1$ formula is insufficient; the system must explicitly account for $e_\delta$ and $u_\epsilon$ .

5. Significance and Claims

The paper positions EBFT as a theoretical framework for agentic infrastructure, where autonomous agents (LLMs, reasoning systems) participate in distributed control planes. Its primary significance lies in:

Decoupling Agreement from Semantics: It explicitly models the gap between "protocol agreement" (deciding the same log entry) and "semantic validity" (the entry being safe/correct).
Quantifying Epistemic Risk: It moves beyond qualitative claims of "diversity" to quantitative bounds on correlated semantic failures.
Operationalizing Safety: It proposes a two-phase admission process (offline calibration + runtime admission) that allows systems to use stochastic validators while maintaining rigorous, probabilistic safety guarantees.

The authors state modestly that this work is a "positioning" within the OpenKedge research program, not a product description. They do not claim to solve semantic correctness deterministically but rather to provide a fault model and threshold theory for systems where semantic judgment is inherently stochastic. The guarantees are conditional on the validity of the calibration, the stability of the workload domain, and the accuracy of the estimated budgets.