Byzantine Accountability Without Consensus: Strong Eventual Consistency for Non-Associative, Stochastic, Robust Aggregation

This paper studies the Byzantine Agreement problem where the nodes have access to a predictor that flags nodes for suspicion of faulty (Byzantine) behavior. We focus on algorithmic resilience -- the maximum number of faulty nodes an algorithm can tolerate -- and present algorithms and impossibility results whose resilience depend on the accuracy of the predictor. As our first main result, we bring a complete characterization of the consistency--robustness trade-offs in both the non-authenticated and authenticated settings: for $n$ nodes and a parameter $α\in [0, 1]$, we present algorithms that tolerate up to $α\cdot n$ faulty nodes when the predictor is correct (consistency), and up to $\frac{1-α}{2} \cdot n - 1$ faulty nodes when the predictor is arbitrarily wrong (robustness); in the authenticated setting the robustness bound improves to $(1-α) \cdot n - 1$. These trade-offs are exactly tight as we show that one additional faulty node renders the problem impossible. Our second main result characterizes smoothness: the rate at which resilience degrades as the predictor becomes less accurate. We show that resilience linearly decreases in the number of wrong predictions as long as that number stays within a constant fraction of $n$. Concretely, in the non-authenticated setting each additional wrong prediction loses one unit of resilience, whereas in the authenticated setting the decline is halved since two wrong predictions are needed to lose one unit of resilience.

Robust aggregation is the core operation in Byzantine-tolerant federated learning. To ensure the quality of aggregation independently of data distribution or attacks, validity conditions are needed. They provide geometric guarantees of where the output of the aggregation must lie. The widespread convex validity requires the output to lie in the convex hull of the honest vectors. Although this guarantee is strong in theory, it is poorly suited to modern federated learning systems, as it has dimension-dependent resilience and excludes many practical aggregation rules. We introduce the minimum enclosing ball (MEB) validity condition for robust aggregation, as well as its multiplicative relaxation, $c$-MEB validity, where $c$ is a constant. We show that exact MEB validity still suffers from limited resilience, while relaxed $c$-MEB validity is achievable if a majority of clients is honest, i.e. $n>2t$. We give an optimal MinMax-MEB rule for the relaxed condition with the bound $c<\sqrt{2}$ and prove explicit relaxed-MEB guarantees for standard aggregators including minimum-diameter averaging, medoid and geometric median. Finally, we relate MEB validity to convex, relaxed-convex and box validity studied in prior literature, thus providing a systematic map of geometric validity conditions for Byzantine-robust aggregation. Our results show that relaxed MEB validity connects validity conditions in distributed computing and Byzantine-tolerant aggregation rules, and offers a practical alternative to convex validity.

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.