REVIEW 2 major objections 5 minor 23 references
This paper establishes the Honest Quorum Problem: protocol-compliant but semantically mistaken validators can form a certificate for an invalid transition, and a single threshold chosen from two epistemic budgets can make that unlikely whil
Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →
T0 review · deepseek-v4-flash
2026-08-01 21:18 UTC pith:7DDJK5QJ
load-bearing objection A genuinely useful fault model for AI validators with correct conditional threshold math—but the calibration pipeline as written does not instantiate the central budgets, so treat it as a framework, not a deployable protocol. the 2 major comments →
The Honest Quorum Problem: Epistemic Byzantine Fault Tolerance for Agentic Infrastructure
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The paper's central claim is that agreement is orthogonal to semantic validity: a well-formed certificate can be created entirely by authenticated, responsive, non-equivocating, protocol-compliant validators who share a false semantic judgment. EBFT separates the fault model into three parts: the Byzantine bound f, the coherent false-endorsement budget eδ, and the unusable-support budget uε. The threshold theorem then says that, on calibrated confidence events, choosing any integer q with max(⌊f+eδ⌋+1, ⌊(N+f)/2⌋+1) ≤ q ≤ ⌊N−f−uε⌋ simultaneously gives semantic certificate validity, deterministic agreement under non-equivocation, and liveness. The proof is a quorum-intersection argument: inval
What carries the argument
The q-signature semantic-certificate protocol and the two confidence events Eδ and Uε. Validators sign structured judgments bound to a canonical evidence digest; a certificate is just q endorsements for the same candidate and class. The safety event Eδ bounds the upper-tail weight of false endorsements outside the Byzantine set by eδ, and the liveness event Uε bounds unusable support by uε. The protocol's power is that a single integer q can satisfy all three requirements when the interval in Theorem 6.4 is nonempty; the quorum-intersection lemma carries the agreement half.
Load-bearing premise
The load-bearing premise is that eδ and uε can be conservatively estimated from labeled calibration tasks in the target domain and stay valid under the live workload; if ground-truth labels are absent or the workload shifts, the threshold interval certifies nothing.
What would settle it
On a labeled workload, calibrate eδ and uε, compute q from Theorem 6.4, then evaluate held-out invalid and valid tasks. If invalid transitions receive certificates noticeably more often than the claimed δ confidence, or valid transitions fail liveness more often than ε, the sufficiency guarantee collapses.
If this is right
- An operator with calibrated eδ and uε can commit to a single quorum threshold that provides semantic certificate validity, agreement, and liveness at once.
- Agreement safety is decoupled from semantic error: the 2q−N > f condition depends only on the Byzantine equivocation bound, so epistemic mistakes do not create forks.
- Adding models, providers, or prompts changes safety only if the measured upper tail of false endorsement or unusable support drops; nominal diversity has no inherent value.
- If false endorsers are conservatively reclassified as Byzantine, the classical 3F+1 bound reapplies on the safety event, at the cost of ignoring liveness.
- Without a concentration bound or another semantic grounding mechanism, no count-only certificate rule can guarantee semantic validity.
Where Pith is reading between the lines
- Because calibration needs ground-truth labels V(x,s), the scheme is strongest exactly where a deterministic verifier already exists; where labels are unavailable, the thresholds are best read as a risk model rather than a guarantee.
- The risk-profile and expiry mechanism points toward a testable operational pattern: any model-weight, prompt, retrieval, or tool change should invalidate the current threshold until recalibration, and an online canary could detect silent drift.
- For LLM ensembles, the upper-tail view suggests measuring the largest false-endorsement coalition and the concentration of unusable support, since pairwise agreement statistics cannot determine quorum-level safety.
- An adaptive adversary who can steer contexts after calibration is outside the base theorem; a natural extension is to require eδ to hold uniformly over adversarially selected instances or to fold influenceable validators into the Byzantine bound.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper introduces the Honest Quorum Problem and an Epistemic Byzantine Fault Tolerance (EBFT) model for agentic validators that are protocol-compliant but can make semantically incorrect judgments. It defines confidence-indexed budgets eδ for coherent false endorsement outside the Byzantine set and uε for unusable support, then derives quorum-threshold conditions for semantic certificate validity, agreement, liveness, and feasible integer thresholds (Section 6). The central result, Theorem 6.4, states that if qmin ≤ q ≤ qmax then the q-signature protocol simultaneously prevents invalid certificates on event Eδ, prevents conflicting certificates deterministically, and permits valid certificates on event Uε. Sections 7–8 propose a two-phase calibration/admission methodology, including a synthetic illustrative budget calculation in Table 5. The paper is framed as a positioning/theory contribution rather than an empirical study.
Significance. If the calibration problem were solved, EBFT would be a conceptually valuable extension of BFT: it separates semantic error concentration from Byzantine equivocation, shows that agreement thresholds depend only on the Byzantine bound f, and explicitly models correlated epistemic faults. The lower-bound results in Section 5 are correctly framed as existence/necessity arguments, and the paper is unusually honest about its conditional guarantees and limitations (Section 10). The threshold arithmetic itself is simple and correct, and the manuscript is transparent that Table 5 is synthetic. However, the practical force of the framework rests entirely on whether eδ and uε can be reliably calibrated, and the proposed calibration does not estimate the quantities required by Definitions 4.6–4.7. As a result, the paper currently delivers a coherent conditional theory with an uninstantiated and, as proposed, mismatched calibration methodology.
major comments (2)
- [§8.1, Appendix B.3, Definitions 4.6/4.7] Definitions 4.6–4.7 define eδ/uε as upper-tail quantiles of the supremum of false-endorsement (resp. unusable) weight over all invalid (resp. valid) (x,s)∈D: P[sup_D F_S > e] ≤ δ. The calibration in §8.1 and Appendix B.3 estimates, per labeled task m, an upper confidence bound for the quantile of the marginal count F_m (Clopper–Pearson/bootstrap). A per-task quantile does not control the supremum over D. Even for independent tasks, if each task has P(F_m>e)≤δ, the maximum over M tasks exceeds e with probability up to Mδ; the binomial 'number of exceedances' procedure in §8.1 targets the count of tasks exceeding e, not the event that any task does. Hence be+δ is not an upper confidence bound for the eδ used in q>f+eδ, and Table 5's synthetic values do not instantiate Theorem 6.4. The caveats in §10.2/10.3 about workload shift and sample size do not address this estimator-target mismatch.
- [Theorem 6.4 (population inequalities)] The exact integer interval qmin ≤ q ≤ qmax is correct, but the claim that the unrounded inequalities N>2f+eδ+uε and N>3f+2uε are 'sufficient in the integral-count setting' is false. These conditions are necessary for the real interval max{f+eδ,(N+f)/2} < q ≤ N−f−uε to be nonempty, but they do not guarantee an integer q exists. Counterexample: N=10, f=2, eδ=1.2, uε=1.2 satisfies both inequalities, yet qmin=max(⌊3.2⌋+1,⌊12/2⌋+1)=7 and qmax=⌊10−2−1.2⌋=6. The exact floor/ceiling test should be presented as the sole feasibility criterion; the unrounded conditions should be described as necessary for real feasibility, not sufficient for integer feasibility.
minor comments (5)
- [§6.2, Eq. (6.7)–(6.8)] The 'equivalently' formulas using ceilings are valid only when eδ and uε are integral. For real-valued budgets, ceil(f+eδ+1) can differ from floor(f+eδ)+1 (e.g., f=2, eδ=1.2 gives 5 vs 4). Please clarify explicitly which rounding rule applies when empirical upper endpoints are non-integral.
- [§8.1, Table 5] The homogeneous row reports beδ=4.2 while the largest false-endorsement coalition is 5. Since beδ is a quantile rather than a coalition size, the relationship should be explained to avoid confusion.
- [§4.4, Eqs. (4.6)–(4.7)] If D is an infinite domain, the supremum over D may not be measurable without additional assumptions. The paper should state a measurability or finite-support condition, or restrict D to a finite task set.
- [§8, RQ1–RQ4] The evaluation section is a methodology description and reports no experimental results. This is acceptable for a theory paper, but the abstract and introduction should make even clearer that the calibration pipeline is not validated on real data; otherwise Table 5 may be mistaken for empirical evidence.
- [§10.4] The suggestion to use 'Chebyshev or Markov variants for dependent variables' is vague. Markov-type bounds depend on the actual distributional object being bounded; specify what moments or dependence assumptions are needed to make the conservative adjustment concrete.
Circularity Check
Safety and liveness thresholds restate the Eδ/Uϵ definitions; only agreement and threshold algebra are independent.
specific steps
-
self definitional
[Section 4.2, Definitions 4.4–4.6 and Eq. 4.6; Section 6.1, Theorem 6.1, Eqs. 6.1–6.2]
"Eδ = {ω ∈ Ω | sup_{(x,s)∈D, V(x,s)=0} F_S(x,s)(ω) ≤ eδ(S,D)} ... Condition on the event Eδ, under which every invalid candidate under consideration receives at most eδ protocol-compliant false-endorsement weight outside the Byzantine set. If q > f+eδ, then no invalid candidate can form a q-signature semantic certificate."
The event Eδ is defined (Def. 4.6/Eq. 4.6) as the event that the supremum false-endorsement weight over all invalid candidates is at most eδ. Theorem 6.1's proof then uses exactly that fact—'On Eδ, protocol-compliant validators outside B contribute at most eδ false endorsements to any invalid candidate'—and adds |B|≤f. Requiring q>f+eδ is simply requiring the certificate threshold to exceed the worst-case invalid support already bounded in the definition. So semantic certificate validity on Eδ is the budget definition restated as an integer inequality; no independent property is derived. The paper's own Section 10.3 concedes the theorem 'can consume a defensible bound on invalid endorsement; it does not create that bound.'
-
self definitional
[Section 4.3, Definitions 4.7–4.8 and Eq. 4.7; Section 6.1, Theorem 6.3, Eqs. 6.5–6.6]
"Uϵ = {ω ∈ Ω | sup_{(x,s)∈D, V(x,s)=1} U_S(x,s)(ω) ≤ uϵ(S,D)} ... condition on the event Uϵ under which at most uϵ protocol-compliant validator weight is unusable. ... If q≤N−f−uϵ, then the valid candidate can obtain a q-signature certificate."
Uϵ (Eq. 4.7) is defined as the event that unusable protocol-compliant support is at most uϵ, so on Uϵ usable support is at least N−f−uϵ by the fixed committee size and Byzantine bound. Theorem 6.3's liveness condition q≤N−f−uϵ is exactly 'the threshold does not exceed the usable support guaranteed by the definition of Uϵ.' Thus liveness on Uϵ is also a restatement of the budget definition plus a counting argument, not an independent derivation. As with safety, the paper is transparent that the guarantee is conditional on the calibrated budget, but the threshold theorem itself carries no information beyond the event definition.
full rationale
The central threshold arithmetic in Section 6 is internally consistent: agreement (Theorem 6.2) is an independent deterministic quorum-intersection result, and the feasibility interval (Theorem 6.4) correctly combines the three inequalities. However, the paper's safety and liveness 'derivations' do not add content beyond the definitions of the confidence events. Eδ (Eq. 4.6) is defined as the event that the sup of false-endorsement weight is ≤ eδ; Theorem 6.1 then assumes Eδ and concludes that q>f+eδ prevents invalid certificates. That is the budget definition plus |B|≤f, restated as a threshold. Likewise Uϵ (Eq. 4.7) already contains the count bound used by Theorem 6.3. The paper is unusually candid about this: Section 10.3 says the theorem 'can consume a defensible bound on invalid endorsement; it does not create that bound,' and Section 8.1 admits the illustrative budgets are synthetic. The calibration gap—per-task quantiles in Section 8.1 versus the sup-tail object in Definition 4.6—is a statistical soundness problem rather than a circularity, though it reinforces that the budget values are not independently instantiated; Section 10.2 also flags workload shift. Self-citations [4]–[7] frame the research program but are not premises of the proofs, so they are not load-bearing circularity. Overall, safety and liveness reduce by construction to their inputs, while agreement and threshold algebra are independent; hence partial circularity.
Axiom & Free-Parameter Ledger
free parameters (2)
- eδ (semantic-safety budget) =
none in paper; synthetic Table 5 uses beδ+ = 5.0 (homogeneous) and 2.0 (heterogeneous)
- uε (liveness budget) =
none in paper; synthetic Table 5 uses buε+ = 2.0 (homogeneous) and 1.0 (heterogeneous)
axioms (5)
- domain assumption Protocol-compliant validators never equivocate and sign at most one judgment per log position.
- domain assumption Static Byzantine set B with |B|≤f, authenticated channels, and partial synchrony after GST.
- domain assumption Deterministic canonicalization πs maps semantically equivalent outcomes to the same class (Assumption 3.3).
- domain assumption Semantic-validity predicate V and labeled calibration tasks in D are reliable.
- ad hoc to paper Stochastic events Eδ and Uε are correctly calibrated with known probabilities.
read the original 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_\delta$ bounds coherent invalid endorsements outside the Byzantine set, and $u_\epsilon$ 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.
Figures
Reference graph
Works this paper leans on
-
[1]
Reaching agreement in the presence of faults.Journal of the ACM, 27(2):228–234, 1980
Marshall Pease, Robert Shostak, and Leslie Lamport. Reaching agreement in the presence of faults.Journal of the ACM, 27(2):228–234, 1980
1980
-
[2]
The byzantine generals problem.ACM Transactions on Programming Languages and Systems, 4(3):382–401, 1982
Leslie Lamport, Robert Shostak, and Marshall Pease. The byzantine generals problem.ACM Transactions on Programming Languages and Systems, 4(3):382–401, 1982
1982
-
[3]
Schneider
Fred B. Schneider. Implementing fault-tolerant services using the state machine approach: A tutorial.ACM Computing Surveys, 22(4):299–319, 1990
1990
-
[4]
The Post-Deterministic Man- ifesto: A new foundation for trustworthy autonomous infrastructure
Jun He and Deying Yu. The Post-Deterministic Man- ifesto: A new foundation for trustworthy autonomous infrastructure. arXiv preprint arXiv:2606.01722, 2026
Pith/arXiv arXiv 2026
-
[5]
Jun He and Deying Yu. OpenKedge: Governing agen- tic mutation with execution-bound safety and evidence chains.arXiv preprint arXiv:2604.08601, 2026
Pith/arXiv arXiv 2026
-
[6]
Jun He and Deying Yu. Semantic Quorum Assurance: Collective certification for non-deterministic AI infras- tructure.arXiv preprint arXiv:2606.08021, 2026
Pith/arXiv arXiv 2026
-
[7]
Sovereign Assurance Boundary: Certificate-bound admission for agentic infrastructure
Jun He and Deying Yu. Sovereign Assurance Boundary: Certificate-bound admission for agentic infrastructure. arXiv preprint arXiv:2606.11632, 2026
Pith/arXiv arXiv 2026
-
[8]
Consensus in the presence of partial synchrony.Journal of the ACM, 35(2):288–323, 1988
Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer. Consensus in the presence of partial synchrony.Journal of the ACM, 35(2):288–323, 1988
1988
-
[9]
Practical byzantine fault tolerance
Miguel Castro and Barbara Liskov. Practical byzantine fault tolerance. InProceedings of the Third Sympo- sium on Operating Systems Design and Implementation, pages 173–186, Berkeley, CA, USA, 1999. USENIX Association
1999
-
[10]
Byzantine quorum systems.Distributed Computing, 11(4):203–213, 1998
Dahlia Malkhi and Michael Reiter. Byzantine quorum systems.Distributed Computing, 11(4):203–213, 1998
1998
-
[11]
On the validity of consensus.arXiv preprint arXiv:2301.04920, 2023
Pierre Civit, Seth Gilbert, Rachid Guerraoui, Jovan Ko- matovic, and Manuel Vidigueira. On the validity of consensus.arXiv preprint arXiv:2301.04920, 2023
Pith/arXiv arXiv 2023
-
[12]
Alejandro Ranchal-Pedrosa and Vincent Gramoli. Basilic: Resilient optimal consensus protocols with benign and deceitful faults.arXiv preprint arXiv:2204.08670, 2022
Pith/arXiv arXiv 2022
-
[13]
The n-version approach to fault- tolerant software.IEEE Transactions on Software Engi- neering, SE-11(12):1491–1501, 1985
Algirdas Avizienis. The n-version approach to fault- tolerant software.IEEE Transactions on Software Engi- neering, SE-11(12):1491–1501, 1985
1985
-
[14]
Knight and Nancy G
John C. Knight and Nancy G. Leveson. An experimental evaluation of the assumption of independence in multi- version programming.IEEE Transactions on Software Engineering, SE-12(1):96–109, 1986
1986
-
[15]
Consensus is not verification: Why crowd wisdom strategies fail for LLM truthfulness
Yegor Denisov-Blanch, Joshua Kazdan, Jessica Chud- novsky, Rylan Schaeffer, Sheng Guan, Soji Adeshina, and Sanmi Koyejo. Consensus is not verification: Why crowd wisdom strategies fail for LLM truthfulness. arXiv preprint arXiv:2603.06612, 2026
arXiv 2026
-
[16]
Yigit Turkmen, Baturalp Buyukates, and Melih Bastopcu. Don’t always pick the highest-performing model: An information theoretic view of LLM ensemble selection.arXiv preprint arXiv:2602.08003, 2026
arXiv 2026
-
[17]
Coding triangle: How does large language model understand code?arXiv preprint arXiv:2507.06138, 2025
Taolin Zhang, Zihan Ma, Maosong Cao, Junnan Liu, Songyang Zhang, and Kai Chen. Coding triangle: How does large language model understand code?arXiv preprint arXiv:2507.06138, 2025
Pith/arXiv arXiv 2025
-
[18]
Another advantage of free choice: Completely asynchronous agreement protocols
Michael Ben-Or. Another advantage of free choice: Completely asynchronous agreement protocols. InPro- ceedings of the Second Annual ACM Symposium on Prin- ciples of Distributed Computing, pages 27–30, 1983
1983
-
[19]
Probabilistic byzantine fault tolerance.arXiv preprint arXiv:2405.04606, 2024
Diogo Avelas, Hasan Heydari, Eduardo Alchieri, Tobias Distler, and Alysson Bessani. Probabilistic byzantine fault tolerance.arXiv preprint arXiv:2405.04606, 2024
Pith/arXiv arXiv 2024
-
[20]
Fischer, Nancy A
Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson. Impossibility of distributed consensus with one faulty process.Journal of the ACM, 32(2):374–382, 1985
1985
-
[21]
Jun He and Deying Yu. Sovereign Agentic Loops: De- coupling AI reasoning from execution in real-world systems.arXiv preprint arXiv:2604.22136, 2026
Pith/arXiv arXiv 2026
-
[22]
Verifiable Agentic Infrastructure: Proof-derived authorization for sovereign AI systems
Jun He and Deying Yu. Verifiable Agentic Infrastructure: Proof-derived authorization for sovereign AI systems. arXiv preprint arXiv:2605.15228, 2026
Pith/arXiv arXiv 2026
-
[23]
Jun He and Deying Yu. Protocol-Driven Development: Governing generated software through invariants and continuous evidence.arXiv preprint arXiv:2605.12981, 2026. 26
Pith/arXiv arXiv 2026
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.