Resilient Byzantine Agreement with Predictions
Julien Dallot, Darya Melnyk, Tijana Milentijevic, Stefan Schmid, Patrik Welters · 2026
Read Resilient Byzantine Agreement with Predictions by Julien Dallot, Darya Melnyk, Tijana Milentijevic, Stefan Schmid, Patrik Welters (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-19452.txt.
Introduction
Dallot and team study Byzantine agreement when nodes carry a predictor flagging suspects. They fully characterize the consistency-robustness trade-off in both plain and authenticated settings. With n nodes and a tuning parameter, their methods handle a set fraction of faulty nodes when the flags are right, and fewer when they are wrong. Authenticated robustness roughly doubles the plain bound. The bounds are exactly tight: one more faulty node makes agreement fail. Resilience also degrades linearly as predictions go wrong, halving the loss rate under authentication.
Catalog record
| CREATOR | Julien Dallot, Darya Melnyk, Tijana Milentijevic, Stefan Schmid, Patrik Welters |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 65546 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.19452
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Resilient Byzantine Agreement with Predictions Julien Dallot, Darya Melnyk, Tijana Milentijevic, Stefan Schmid, Patrik Welters Abstract The Byzantine Agreement (BA) problem is a fundamental task in distributed computing where nodes in a network need to agree on a common output in the presence of arbitrary (worst-case) node failures. In real-world applications, nodes can be monitored over time to provide ML predictions of faulty behavior in a network. In this work, we answer the question of whether predictions can improve the fault tolerance of a distributed system without sacrificing correctness when the predictions are wrong. We consider a prediction-augmented study of Byzantine agreement in which each node receives, in addition to its input bit, a predicted set of honest nodes. We focus on algorithmic resilience — the maximum number of faulty nodes an algorithm can tolerate — and present algorithms and impossibility results whose resilience depends 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 n nodes and a parameter α ∈ [ 0 , 1 ] \alpha\in[0,1] , we present algorithms that tolerate up to α ⋅ n \alpha\cdot n faulty nodes when the predictor is correct ( consistency ), and up to 1 − α 2 ⋅ n − 1 \frac{1-\alpha}{2}\cdot n-1 faulty nodes when the predictor is arbitrarily wrong ( robustness) . In the authenticated setting, the robustness bound improves to ( 1 − α ) ⋅ n − 1 (1-\alpha)\cdot n-1 . We prove matching impossibility results, showing that these tradeoffs are optimal and independent of the particular prediction system. 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 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. TU Berlin, [email protected] TU Berlin, [email protected] TU Berlin, [email protected] TU Berlin and Weizenbaum Institute, [email protected] HU Berlin, [email protected] {CCSXML} ¡ccs2012¿ ¡concept¿ ¡concept_id¿10003752.10003809.10010172¡/concept_id¿ ¡concept_desc¿Theory of computation Distributed algorithms¡/concept_desc¿ ¡concept_significance¿500¡/concept_significance¿ ¡/concept¿ ¡concept¿ ¡concept_id¿10003752.10010070.10010071¡/concept_id¿ ¡concept_desc¿Theory of computation Machine learning theory¡/concept_desc¿ ¡concept_significance¿500¡/concept_significance¿ ¡/concept¿ ¡/ccs2012¿ ccs Theory of computation Machine learning theory ccs Theory of computation Distributed algorithms keywords Learning-Augmented Algorithms, Byzantine Agreement, Distributed Algorithms † † runningauthor: J. Dallot, D. Melnyk, T. Milentijevic, S. Schmid and P. Welters † † funding: This work was supported by the German Research Foundation (DFG), Schwerpunktprogramm SPP 2378: ReNO-2 (511099228), 2025-2029 1 Introduction Byzantine Agreement (BA) [ 19 , 23 ] is a most fundamental and intensively studied problem in distributed computing. It requires nodes to agree on a common output despite arbitrary, worst-case node failures, called Byzantine behavior in the literature. This work explores how predictions about the other nodes’ behavior can be used to improve the resilience of BA. Indeed, in practice, nodes can often monitor and collect data about other nodes, and use machine-learned classifiers, anomaly detectors, or reputation algorithms, to guess how trustworthy other nodes are. This is a natural model for many distributed systems operating over longer time periods, such as blockchain: suspicious behavior of the participants can be monitored and, to some extent, detected [ 6 ] . However, with new participants and new capabilities of these systems, mistakes in the prediction are not preventable. Motivated by Machine Learning (ML), prediction-augmented algorithms have already received much attention and have been applied successfully in various domains already. Early work originated in the context of online algorithms, where predictions about the future events are used by algorithms to overcome worst-case bounds [ 21 ] , and many significant insights have been obtained how to improve the competitive ratio of different online algorithms [ 15 , 11 , 24 , 26 , 8 , 21 ] . But also data structures [ 3 ] and most recently also distributed computing tasks [ 5 , 2 ] have been improved with predictions. In particular, Ben-David et al. [ 2 ] studied whether nodes can benefit from predictions about the correctness of other nodes in Byzantine Agreement to speed up agreement, hence focusing on the efficiency . In this paper, we are interested in the resilience of prediction-augmented algorithms. In particular, we initiate the study of whether predictions about node behaviors can allow us to tolerate more node failures in Byzantine Agreement. This is challenging since predictions are inherently unreliable. And while accurate predictions can substantially improve the resilience, relying on them unconditionally can compromise correctness when they are wrong. Hence, as with any prediction-augmented algorithm, a useful prediction-augmented Byzantine agreement protocol should navigate the trade-off between consistency , i.e., benefit when predictions are correct, and robustness , i.e., not suffer when predictions are of poor quality or even adversarial. Beyond these extremes, we aim for smoothness : the protocol should lose resilience gradually, rather than abruptly, as the number of incorrect predictions increases. 1.1 Contributions This paper initiates the study of whether and how ML predictions can be used to improve the resilience of algorithms for the Byzantine Agreement problem. Specifically, we ask: given n nodes and t faults, can we use predictions to overcome the upper bounds of n>3t (without authentication) [ 23 ] and n>2t (with authentication) [ 19 ] on the resilience of the agreement protocols? We answer these questions affirmatively. We design prediction-augmented algorithms which, given a prediction of which nodes are trustworthy (honest), surpass any prediction-free algorithm in case of accurate predictions (i.e., consistency) while ensuring provable resilience guarantees against any prediction (i.e., robustness). In addition, we study the resilience of our algorithms as the prediction accuracy declines (i.e., smoothness) and provide resilience guaranties for any fraction of accurately predicted nodes. Our algorithms are tuned with a trust parameter \alpha\in[0,1] which is the desired consistency (tolerated fraction of faulty nodes for good predictions) and interpolates between prudent or risky algorithms depending on how much one trusts the predictor. We provide theoretical results for four settings: we consider two communication models, where the communication channels can either be authenticated or not; and we consider two models of predictions, a global model in which the predictions are publicly available to all nodes (e.g., broadcast by an ML monitoring system) and a local model in which predictions are only available locally. Our results for global predictions are summarized in Figure 1 . Starting from existing, prediction-free agreement algorithms, we build prediction-augmented algorithms to achieve better resilience bounds in the non-authenticated setting ( Section 3 and Section 4 ) as well as the authenticated setting ( Appendix C ) and finally derive impossibility results for local predictions ( Section 5 ). Characterizing consistency and robustness. Our first technical contribution is a complete characterization of the possible consistency and robustness trade-offs under global predictions for non-authenticated and authenticated channels. Results in the global setting are summarized in Table 1 . Pred. Communications Consistency Robustness Impossible Rob. Global Non-Auth \alpha\in\left[\tfrac{1}{3},1\right] \tfrac{1-\alpha}{2}-\frac{1}{n}\ ^{(\text{Thm.}\ref{thm:consistency-robustness})} \frac{1-\alpha}{2}\ ^{(\text{Thm.}\ref{thm:impossibility-consistency-robustness})} Auth \alpha\in\left[\tfrac{1}{2},1\right] (1-\alpha)-\frac{1}{n}\ ^{(\text{Thm.}\ref{thm:auth-consistency-robustness})} (1-\alpha)\ ^{(\text{Thm.}\ref{thm:auth-impossibility-consistency-robustness})} Local Non-Auth \alpha\in\left[\tfrac{1}{3},\tfrac{1}{2}\right[ (unknown)