Resilient Byzantine Agreement with Predictions

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$ nodes and a parameter $\alpha \in [0, 1]$, we present algorithms that tolerate up to $\alpha \cdot n$ faulty nodes when the predictor is correct (consistency), and up to $\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-\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$. 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.