PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Jun He, Deying Yu

arXiv:2607.16109v1cs.LGcs.DCcs.MA

TL;DR

Agentic validators may follow protocol while coherently endorsing semantically invalid transitions, making agreement insufficient for semantic validity. The paper defines EBFT with separate confidence-indexed budgets for invalid endorsements and unusable support; its impossibility result shows that agreement and termination can still decide an invalid transition.

  • Problem

    Protocol-compliant validators can coherently endorse an invalid transition, and shared models, prompts, or tools can correlate those errors.

    Source: §1 · pp. 1–2

  • Method

    EBFT augments the Byzantine fault bound with confidence-indexed budgets for coherent invalid endorsement and unusable validator support.

    Source: §11 · p. 20

  • Results

    Agreement and termination can decide a semantically invalid transition even when its certificate is externally valid.

    Source: §5 · p. 8

  • Takeaways & Limitations

    Nominal agent count or provider diversity is insufficient; fault tolerance depends on bounding upper-tail support for invalid judgments.

    Source: §11 · p. 20

    EBFT does not itself produce semantic correctness, which must come from a validity oracle, grounded evidence, a deterministic verifier, or a calibrated probabilistic bound.

    Source: §10.9 · p. 20

Abstract

from arXiv · show

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.

1 Introduction

Agentic validators can obey the protocol and still endorse an invalid state change, so agreement may certify a semantically invalid transition. The paper formalizes this as the Honest Quorum Problem and introduces EBFT to model semantic safety and liveness risks separately.

1 Introduction

  • A quorum can approve a production service-account change that crosses a control-plane isolation boundary even though validators follow the protocol and agreement succeeds.The example distinguishes successful protocol execution from semantic validity and operational safety.Source: §1 · p. 1
  • An epistemic fault is a semantically incorrect judgment by a participant that remains authenticated, responsive, non-equivocating, and protocol-compliant.Shared model lineage, training data, prompts, retrieval, tools, or providers can make validators fail coherently, so nominal identity diversity does not imply epistemic independence.Source: §1 · pp. 1–2
  • EBFT augments the Byzantine bound with e_δ for coherent invalid endorsements and u_ϵ for unusable support, which threatens liveness.The budgets exclude the conventional Byzantine set unless explicitly stated otherwise.Source: §1 · p. 2
  • EBFT derives separate threshold conditions for semantic certificate validity, agreement, liveness, and feasible threshold selection rather than reweighting 3f+1.The stated results do not claim tightness beyond the proved intersection and threshold statements.Source: §1 · p. 2
  • The paper positions EBFT as a fault model and threshold theory for post-deterministic systems, with diversity mechanisms treated as candidates for reducing correlation, not proof of reduced tail risk.It distinguishes semantic validity from execution safety: validity implies safety only if the predicate fully captures the operational invariant.Source: §1 · p. 2

2 Background and Motivation

The background distinguishes agreement and external validity from stochastic semantic judgment, then motivates EBFT through hybrid faults, correlated failures, and certificate-level concentration.

2.1 Byzantine Agreement, SMR, and Quorum Intersection

  • Byzantine agreement and quorum intersection protect consistent decisions against bounded arbitrary faults, while SMR relies on deterministic execution of agreed commands.EBFT retains ordering theory but examines stochastic validators supplying semantic admissibility judgments.Source: §2.1 · p. 2

2.2 Validated Consensus and External Validity

  • Consensus can require an application predicate for external validity, but EBFT addresses cases where semantic validity is contextual or underspecified for deterministic evaluation [11].A committee instead approximates validity through stochastic reasoning, raising the question of whether errors concentrate on the same invalid class.Source: §2.2 · pp. 2–3

2.3 Hybrid Fault Models

  • Hybrid models distinguish safety- and liveness-relevant faults, but a protocol-compliant semantic error fits neither deceitful nor benign faults automatically [12].Treating it as Byzantine can conservatively bound risk but loses the distinction between coherent safety risk and dispersive liveness loss.Source: §2.3 · p. 3

2.4 Common-Mode Failure and Design Diversity

  • N-version diversity was challenged by joint failures; ensemble studies [15] [16] [17] likewise motivate measuring validator error concentration, not labels.The relevant quantity is upper-tail validator weight assigned to one invalid semantic class.Source: §2.4 · p. 3

2.5 Probabilistic Fault Models

  • Probabilistic BFT concerns quorum sampling or protocol guarantees [19], whereas EBFT’s probability concerns how much compliant support endorses the same invalid transition.The uncertainty is in semantic judgments that may share data, tools, prompts, model lineages, or assumptions.Source: §2.5 · p. 3

2.6 Stochastic Semantic Validation

  • Stochastic semantic validation places evidence-based reasoning between a candidate transition and execution; the key risk is enough compliant validators endorsing one invalid candidate for certification.A lone error may be harmless, while scattered errors can impair liveness; the safety-relevant event is certificate-level concentration.Source: §2.6 · pp. 3–4

3 System and Semantic Model

The section defines a base model for admitting proposed transitions and distinguishes protocol-level agreement from semantic validity and execution safety. It specifies the assumptions, judgments, and properties used to analyze that distinction.

3.1 Participants, Network, and Corruption

  • The model has N equally weighted replicas, at most f static Byzantine identities, and authenticated partially synchronous channels; compliant validators may still endorse invalid or reject valid transitions.Source: §3.1 · p. 4

3.2 Admission Instances

  • An admission instance binds the candidate digest, state/context, evidence-package identity, and view; consistent binding blocks compliant validators from combining judgments across packages, though Byzantine validators may equivocate.Source: §3.2 · p. 4

3.3 Semantic Validity and Classes

  • V(x, s) specifies application validity; multiple candidates may be valid, while deterministic canonicalization groups equivalent outcomes and must be justified for the deployment’s certificate schema.Source: §3.3 · pp. 4–5

3.4 Signed Judgments and Certificates

  • Judgments carry an action, semantic class, evidence digest, provenance, and signature; a certificate needs q distinct endorsers agreeing on instance fields and class, though compliant signers can err semantically.Source: §3.4 · p. 5, §3.5 · p. 5

3.5 Fault, Randomness, and Adversary Model

  • Fault probabilities may include correlated workload, validator, retrieval, tool, model, and configuration randomness; bounds are context-conditional unless workload averaging is explicitly stated.Byzantine behavior and pre-synchrony scheduling are worst-case; adaptive task selection requires a uniform bound or an expressly average-case workload bound.Source: §3.5 · pp. 5–6

3.6 Properties

  • The model distinguishes agreement and syntactic external validity from semantic certificate validity, while liveness needs usable support and execution safety depends on V encoding the invariant.Source: §3.6 · p. 6

3.7 Generative Proposal Extension

  • The generative-proposal extension requires explicit aggregation, canonicalization, and evidence-binding rules; absent a named extension, base results concern a proposer-fixed candidate assessed by validators.Source: §3.7 · p. 6

4 The Honest Quorum Problem and Epistemic Fault Model

The Honest Quorum Problem occurs when protocol-compliant validators endorse a semantically invalid candidate, so agreement alone does not establish semantic validity. EBFT separates coherent false endorsements from unusable support to characterize semantic-safety and liveness risks.

4.1 Honest Quorums and Epistemic Faults

  • A protocol-compliant quorum can sign the same invalid candidate, while epistemic faults also include rejecting valid candidates, abstaining, or returning divergent semantic classes.Coherent faults concentrate on the same invalid judgment; dispersive faults may instead reduce liveness.Source: §4.1 · pp. 6–7

4.2 False Endorsement and Semantic-Safety Budgets

  • The confidence-indexed semantic-safety budget bounds false-endorsement weight among protocol-compliant validators, excluding Byzantine support by definition.Pointwise budgets condition on a fixed instance; workload-level budgets depend on the stated workload support or distribution.Source: §4.2 · p. 7

4.3 Unusable Support and Liveness Budgets

  • A committee can have low false-endorsement risk yet fail to certify valid candidates when validators reject, abstain, time out, disagree, or fail canonicalization.The liveness budget separately bounds unusable support.Source: §4.3 · p. 7

4.4 Confidence Events and Calibration Scope

  • EBFT keeps semantic-safety and liveness budgets separate, and pairwise error correlation alone cannot determine the probability of quorum-scale false endorsement.Empirical estimates depend on committee, workload, model and tool choices, confidence parameters, and calibration time; report sample sizes, stratification, adjudication, and confidence intervals.Source: §4.4 · pp. 7–8

4.5 Proposal-Generation Extension

  • The proposal-generation extension measures coherent invalid support by semantic class, but requires its own aggregation and canonicalization rules before use in a quorum theorem.The base budget instead concerns false endorsements of a proposer-supplied candidate.Source: §4.5 · p. 8

5 Impossibility and Lower Bounds

The lower bounds separate protocol-visible agreement from semantic correctness: an invalid transition can be certified even when the protocol meets agreement and termination. Count-only acceptance cannot guarantee semantic validity under unrestricted semantic errors; an additional grounding assumption is needed.

5 Impossibility and Lower Bounds

  • Agreement and termination can hold while an invalid transition obtains a certificate, so protocol-visible agreement does not establish semantic certificate validity.The result is an existence separation, not a necessary condition or tight threshold result.Source: §5 · p. 8
  • With unrestricted semantic errors, any nontrivial certificate rule based only on signed identities and protocol-visible judgments can accept an invalid candidate with probability one.The construction uses two interpretations compatible with the same visible transcript, one valid and one invalid.Source: §5 · p. 9
  • A replicated model family that alone satisfies the threshold creates an unsafe-certificate probability floor of at least the common-mode event’s probability.This is a lower bound for a fixed committee and static Byzantine adversary, not an upper bound or a tight bound unless other unsafe events are ruled out.Source: §5 · p. 9
  • Agreement-only protocols cannot guarantee semantic certificate validity for all executions without an additional semantic grounding mechanism.Possible mechanisms include a validity oracle, trusted verifier, bounded false-endorsement distribution, or independently justified semantic evidence.Source: §5 · pp. 9–10

6 EBFT Safety, Agreement, and Liveness Thresholds

EBFT derives separate quorum conditions for semantic validity, deterministic agreement, and liveness, then identifies when one threshold can satisfy all three. Its epistemic budgets separate invalid endorsements from unusable support, rather than treating both as Byzantine behavior.

6.1 Semantic Certificate Validity, Agreement, and Liveness

  • On Eδ, q > f + eδ prevents any invalid candidate from forming a certificate within the stated calibrated scope.This is a probabilistic sufficient condition, not claimed tight for protocols with additional semantic-validity evidence.Source: §6.1 · p. 10
  • q > (N + f)/2 prevents two conflicting certificates under authenticated signatures when only Byzantine validators may equivocate.The intersection argument does not count non-equivocating epistemic errors as Byzantine faults.Source: §6.1 · p. 10, The inequality is necessary and… · p. 10
  • On Uϵ, q ≤ N − f − uϵ lets a valid candidate obtain a certificate after GST under partial synchrony.This sufficient condition is not claimed tight for protocols with additional recovery mechanisms.Source: The inequality is necessary and… · p. 10, This is a probabilistic sufficient… · p. 11

6.2 Threshold Feasibility

  • A single integer q in [qmin, qmax] satisfies all three displayed threshold conditions; Eδ and Uϵ jointly hold with probability at least 1 − δ − ϵ by the union bound.A sharper joint probability bound may replace the union bound when dependence between the events is modeled directly.Source: §6.2 · p. 11

6.3 Conservative Full-Byzantine Reduction

  • Treating false endorsers as Byzantine yields the sufficient classical condition N ≥ 3(f + eδ) + 1 on Eδ, but is deliberately pessimistic.This reduction does not express the liveness budget uϵ and is not necessary for the base certificate rule.Source: §6.3 · p. 12

6.4 Comparison

  • Epistemic faults remain non-equivocating, so agreement depends only on f, while eδ and uϵ separately bound certificate-safety and liveness risks.When eδ = uϵ = 0, the feasibility conditions reduce to the usual N > 3f condition.Source: §6.4 · p. 12

7 Diversity-Aware Semantic Certification

Diversity affects EBFT thresholds only through measured reductions in calibrated risk budgets. The process separates offline committee calibration from runtime admission under the resulting signed profile.

7 Diversity-Aware Semantic Certification

  • Diversity changes threshold mathematics only when it measurably lowers calibrated upper bounds for invalid endorsements or unusable support.A qualitative diversity score alone is not part of the certificate argument unless tied to one of those quantities.Source: §7 · p. 12, §7.1 · pp. 12–13

7.1 Phase A: Offline Calibration

  • Phase A calibrates committee-specific upper bounds on labeled tasks within a specified workload domain, recording confidence, provenance, overlap assumptions, and expiry.Selection also observes latency, cost, capability, and jurisdiction constraints; profiles expire and are rotated after relevant configuration changes.Source: §7.1 · pp. 12–13

7.2 Phase B: Runtime Admission

  • At runtime, validators endorse a canonical request digest only under a matching, unexpired calibrated profile; commit requires q⋆ valid endorsements, otherwise the service abstains or escalates.A failed certificate does not by itself establish that the candidate is semantically invalid.Source: §7.2 · p. 14

8 Calibration and Evaluation Methodology

The methodology outlines calibration, evaluation, and operational checks for estimating EBFT budgets and selecting committees and thresholds. A hypothetical comparison illustrates how estimated budgets can determine threshold feasibility; it is not an experimental result.

8 Calibration and Evaluation Methodology

  • Calibration uses labeled or externally verifiable tasks and reserves held-out workload families to test whether estimated budgets generalize across task families.Random train/test splits within one task family are insufficient for this purpose.Source: §8 · p. 14
  • The methodology measures false endorsements and rejections, abstentions, validator dependence, coalition size, budget estimates, certificate and liveness failures, latency, and cost.Adversarial tests include shared poisoned evidence, ambiguous policies, prompt injection, retrieval corruption, and model-family-targeted traps.Source: §8 · p. 15
  • The evaluation compares theorem-derived thresholds with independence-based, majority, fixed-weight, and single-validator baselines using unsafe-certificate and no-certificate rates.The comparison tests whether thresholds based on upper-confidence estimates are conservative, not whether the theorem predicts exact frequencies.Source: §8 · p. 15
  • Rare-event estimates require reporting sample sizes, task and committee counts, uncertainty methods, and budget confidence endpoints; a few hundred examples cannot support a 10^-6 risk claim.If the sample cannot resolve the target confidence level, the methodology calls for reporting the weakest supported bound or an insufficient sample.Source: §8 · p. 15
  • The risk profile records validator provenance and is rerun or retired after model, tool, retrieval, or workload-domain changes, or when tests or confidence intervals invalidate its assumptions.Runtime admission checks the domain, provenance, and precomputed threshold q.Source: §8 · p. 15, Figure 2 · p. 15

8.1 Illustrative Budget Calculation

  • The illustrative calculation estimates safety budgets from false endorsements on invalid tasks and liveness budgets from unusable support on valid tasks.It compares hypothetical homogeneous and heterogeneous committees of seven validators, rather than reporting experimental results.Source: §8.1 · p. 15, Table 5 · p. 16
  • In the illustrative N=7, f=1 comparison, the heterogeneous committee is feasible only at q*=5, while the homogeneous configuration is infeasible.The homogeneous safety threshold q=7 violates the liveness constraint under the stated assumptions.Source: Table 5 · p. 16, §8.1 · p. 16

9 Related Work

The related work situates EBFT among consensus, quorum, fault-model, and diversity research while distinguishing semantic concentration risk from conventional protocol and network faults. It connects the model to agentic systems and semantic quorum assurance.

9.1 Byzantine Agreement and State Machine Replication

  • Classical Byzantine agreement and SMR provide ordering and replication foundations; EBFT retains that ordering theory while addressing stochastic semantic admission.The cited background describes agreement despite arbitrary faults, SMR command ordering, and practical replication under timing and authentication assumptions [8,9].Source: §9.1 · p. 16

9.2 Hybrid and Asymmetric Fault Models

  • EBFT extends hybrid fault-model and quorum reasoning by bounding coherent invalid semantic support, shifting part of assurance from identity counting to distributional estimation.Its distinguishing object is semantic concentration among protocol-compliant validators, not a new network or message-failure class.Source: §9.3 · pp. 16–17, §9.2 · p. 16

9.4 Common-Mode and Correlated Failures

  • Diversity does not establish independence: distinct agents, providers, or prompts may share failure domains, so their effect on coherent invalid support must be tested.The concern parallels common-mode failures in N-version programming.Source: §9.4 · p. 17, §9.5 · p. 17

9.6 Probabilistic Consensus

  • Unlike probabilistic consensus, which uses probability for scheduler behavior, random choices, or termination, EBFT uses it to bound semantic concentration risk among stochastic validators.The related work notes that LLM-ensemble value depends on whether errors disperse or concentrate over semantic classes.Source: §9.6 · p. 17, §9.8 · p. 17

9.7 External Validity and Application-Aware Consensus

  • EBFT focuses on semantic validity that is expensive, uncertain, or approximated by reasoning participants, rather than validity checked syntactically or by deterministic application logic.The cited work on consensus validity treats validity as a first-class property [11]; EBFT addresses semantic admission by stochastic reasoning.Source: §9.7 · p. 17

9.9 Agentic Distributed Systems

  • Agentic infrastructure is one application of the post-deterministic model: stochastic outputs may enter replicated decisions, while protocols and evidence govern operational mutations.The relevant participant need not be an LLM; it can be any stochastic reasoning or synthesis process admitted by quorum.Source: §9.9 · p. 17

9.10 Post-Deterministic Distributed Systems

  • Post-deterministic distributed systems retain deterministic coordination while participants derive transitions through stochastic or nondeterministic semantic procedures.EBFT identifies upper-tail support for a common invalid semantic class as a safety-relevant quantity.Source: §9.10 · pp. 17–18

9.11 Semantic Quorum Assurance

  • Semantic Quorum Assurance combines quorum certificates with evidence about semantic validity; EBFT operationalizes it with eδ and uϵ budgets and models correlated invalid support.Prior SQA work proposed diverse sandboxed validators, adaptive thresholds, and evidence-backed certificates [6], while the Sovereign Assurance Boundary places certificates at runtime admission [7].Source: §9.11 · p. 18

10 Discussion and Limitations

The discussion distinguishes deterministic agreement from statistical semantic and liveness guarantees, then details their dependence on calibration scope, evidence, and system assumptions. It also identifies operational costs and limits on what EBFT establishes.

10.1 Statistical versus Deterministic Guarantees

  • Agreement can be deterministic under protocol assumptions, but semantic validity and liveness depend on confidence events; statistical guarantees do not make semantic correctness deterministic.The guarantee is a quantified certificate risk under explicit probabilistic and protocol assumptions, conditional on the committee, domain, evidence, canonicalization, adversary model, expiration policy, and budgets remaining valid.Source: §10.1 · p. 18, §10.9 · p. 20

10.2 Workload Selection and Distribution Shift

  • Budgets apply only to their calibrated workload and sampling convention; workload or state shifts require domain checks, profile expiration, escalation, and recalibration.Held-out families and adversarial tests provide evidence about a stated domain, not all future tasks.Source: §10.2 · p. 18

10.3 Validity Oracles and Label Uncertainty

  • Calibration separates validator behavior from estimation uncertainty, and the theorem consumes a defensible invalid-endorsement bound rather than creating one.A deterministic validity oracle or executable external verifier is the strongest setting; weaker labels require recording their provenance and uncertainty.Source: §10.3 · p. 18

10.4 Hidden Common Failure Domains

  • Diversity reduces eδ or uϵ only if it reduces coherent-failure probability or weight under the calibrated workload; provider labels do not prove independence.Proprietary black-box APIs can make lineage and training-corpus audits unavailable, requiring conservative upper confidence bounds for latent dependence.Source: §10.4 · pp. 18–19

10.5 Canonicalization and Evidence Correlation

  • Canonicalization and shared evidence can dominate model diversity: syntactic normalization may align equivalent digests, but semantic parsing differences can still undermine agreement about the validated policy.Ambiguous canonicalization warrants runtime escalation; the system must canonicalize at the semantic policy boundary or enforce parser homogeneity.Source: §10.5 · p. 19

10.6 Adaptive Adversaries

  • Adaptive task choice, targeted influence, provider updates, or shared evidence corruption can invalidate an average-case budget; stronger adversaries require a uniform bound or a larger Byzantine bound.The proposed response includes provenance tracking and canary verification to detect silent model changes and expire affected profiles.Source: §10.6 · p. 19

10.7 Cost of Epistemic Diversity

  • Larger or more heterogeneous committees can raise cost, latency, complexity, privacy exposure, and unusable support, making committee selection a constrained engineering problem.Diversity is valuable when it improves estimated budgets enough to meet thresholds within acceptable operational and governance limits.Source: §10.7 · p. 19

10.8 Performance and Latency Overheads

  • Semantic certification may take hundreds of milliseconds to seconds for model inference, making it unlikely to fit the ordinary synchronous deterministic-validation path.Off-critical-path validation, optimistic execution, and semantic caching are described as alternatives, each with its own failure model and controls.Source: §10.8 · p. 20

11 Conclusion

The conclusion identifies a fault mode in which protocol compliance and semantic correctness diverge. EBFT addresses it with separate confidence-indexed bounds for invalid endorsement and unusable support, emphasizing that nominal diversity alone is not fault tolerance.

11 Conclusion

  • A validator can authenticate, respond on time, sign correctly, and avoid equivocation while still making an incorrect semantic judgment about an operational transition.This separates protocol compliance from semantic correctness.Source: §11 · p. 20
  • EBFT adds eδ for coherent invalid endorsement threatening semantic certificate validity and uϵ for unusable support threatening liveness to the conventional Byzantine bound.These are distinct confidence-indexed semantic budgets.Source: §11 · p. 20
  • Nominal agent count or provider diversity is insufficient evidence of fault tolerance; the relevant bound concerns protocol-compliant support concentrated on an invalid semantic judgment.Agreement can be well signed and protocol valid without establishing semantic validity.Source: §11 · p. 20

Appendix A Formal Proofs

Appendix A sets the equal-weight model and derives conditions for one integer quorum threshold to satisfy semantic validity, agreement, and liveness, with deterministic specializations and a conservative Byzantine reduction.

A.1 Preliminaries and Quorum-Intersection Lemma

  • The base model uses identity counts and confidence-indexed events to bound false endorsements and unusable support outside the Byzantine set.The Byzantine set is static, and the budgets are measured in units of validator support.Source: §A.1 · pp. 20–21
  • Two q-quorums intersect in more than f validators exactly when q > (N + f)/2.The lemma is deterministic and establishes a set-intersection condition, not a lower bound for every consensus protocol.Source: §A.1 · p. 21

A.8 Threshold-Feasibility Corollary

  • A single threshold satisfies semantic validity, agreement, and liveness when the integer interval qmin ≤ q ≤ qmax is nonempty.The safety and agreement bounds set the lower endpoint; the liveness bound sets the upper endpoint.Source: §A.8 · p. 23
  • Ignoring integer rounding, N > 3f + 2uϵ is a sufficient population condition for threshold feasibility.The joint probability of the semantic-safety and liveness events is at least 1 − δ − ϵ by the union bound.Source: §A.8 · p. 23

A.9 Deterministic ec/ei Specialization

  • With deterministic bounds eδ = ec and uϵ = ec + ei, a sufficient population condition is N > max {2f + 2ec + ei, 3f + 2ec + 2ei}.The authors do not claim this specialization is tight.Source: §A.9 · pp. 23–24

A.10 Conservative Full-Byzantine Reduction

  • The conservative full-Byzantine reduction charges protocol-compliant false endorsers as Byzantine identities for quorum-intersection purposes.The reduction is an intentional conservative accounting choice.Source: §A.10 · p. 24

A.2 Proof of Agreement/Semantic-Validity Separation

The proofs distinguish semantic validity from agreement and liveness, then describe how labeled tasks and empirical quantiles can estimate false-endorsement and unusable-support budgets.

A.2 Proof of Agreement/Semantic-Validity Separation

  • An invalid transition can be certified even when every validator is protocol-compliant and the consensus protocol achieves agreement and termination.The theorem gives an existence separation, not a necessary or tight threshold condition.Source: §A.2 · p. 21

A.3 Count-Only Impossibility Proof

  • Without a semantic oracle or grounding assumption, a count- or weight-only rule can accept an invalid candidate with probability one.The result applies to any nontrivial rule based on protocol-visible identities, weights, and judgments.Source: §A.3 · pp. 21–22

A.4 Common-Mode Replication Theorem

  • If a replicated model family alone meets the certificate threshold during a common-mode failure, unsafe-certificate probability is at least the probability of that event.Adding validators from that family does not lower this floor while the cloned group still meets the threshold.Source: §A.4 · p. 22

A.5 Semantic-Certificate Validity Theorem

  • On Eδ, no invalid candidate forms a q-signature certificate when q exceeds the maximum Byzantine plus protocol-compliant false-endorsement support.For integer thresholds, the sufficient bound is q ≥ ⌊f + eδ⌋ + 1.Source: §A.5 · p. 22

A.6 Agreement Theorem

  • Conflicting q-certificates cannot both form when 2q − N > f, because their intersection must include a protocol-compliant validator.The condition is necessary and sufficient for this quorum-intersection property, not a global lower bound for all protocols.Source: §A.6 · pp. 22–23

A.7 Liveness Theorem

  • On Uϵ, a valid candidate can obtain a certificate when q does not exceed the guaranteed usable protocol-compliant support.The result assumes partial synchrony after GST and does not cover protocols with additional recovery mechanisms.Source: §A.7 · p. 23

B.1 Task Sampling

  • Calibration fixes the workload domain and configuration, samples tasks before inspecting validator outputs, and records the intended guarantee scope.The procedure distinguishes splits within a task family from held-out workload-family splits and does not reuse average-case estimates for adversarial selection without a valid bound.Source: Appendix B · p. 24, §B.1 · p. 24

B.2 Semantic Labels

  • Each task needs a defensible semantic-validity label bound to its state, transition, policy, evidence, and admissible actions.Label uncertainty is recorded separately from validator error.Source: §B.2 · p. 24

B.4 Uncertainty Intervals and Rare-Event Limitations

The calibration methodology addresses uncertainty and workload shift, tracks committee provenance, and records inputs and estimates in a reproducibility schema.

B.4 Uncertainty Intervals and Rare-Event Limitations

  • Uncertainty intervals account for sampling uncertainty under the stated procedure, while hidden label bias, measurement error, and unmodeled common-mode structure require separate assumptions or sensitivity analysis.Small calibration sets cannot justify extremely small tail probabilities; report the weakest defensible upper bound when sample size is insufficient.Source: §B.4 · p. 25

B.5 Distribution-Shift Checks

  • Calibration budgets are stress-tested on held-out workload families and adversarial conditions, with material increases triggering domain narrowing, threshold recomputation, committee reselection, or recalibration.Checks include shared poisoned evidence, ambiguous policies, prompt injection, retrieval corruption, and model-family-specific traps.Source: §B.5 · p. 25

B.6 Committee Provenance

  • Committee provenance records model, prompt, retrieval, tool, policy, provider, and evidence-source dependencies because changes can alter both budgets.The signed risk profile includes an expiration date and rerun criteria tied to provenance changes.Source: §B.6 · p. 25

B.7 Reproducibility Data Schema

  • The reproducibility schema records calibration inputs and estimates alongside run, domain, task, validator, and shift metadata.It is a record schema, not a report of experimental results.Source: §B.7 · pp. 25–26

Related papers

Loading 2607.16109v1…