Byzantine Agreement with Predictions

In this paper, we study the problem of \emph{Byzantine Agreement with predictions}. Along with a proposal, each process is also given a prediction, i.e., extra information which is not guaranteed to be true. For example, one might imagine that the prediction is produced by a network security monitoring service that looks for patterns of malicious behavior. Our goal is to design an algorithm that is more efficient when the predictions are accurate, degrades in performance as predictions decrease in accuracy, and still in the worst case performs as well as any algorithm without predictions even when the predictions are completely inaccurate. On the negative side, we show that Byzantine Agreement with predictions still requires $\Omega(n^2)$ messages, even in executions where the predictions are completely accurate. On the positive side, we show that \emph{classification predictions} can help improve the time complexity. For (synchronous) Byzantine Agreement with classification predictions, we present new algorithms that leverage predictions to yield better time complexity, and we show that the time complexity achieved is optimal as a function of the prediction quality.