A Simple Phase-King Protocol with Predictions

Abstract

Inspired by recent work (Ben-David, Dzulfikar, Ellen, and Gilbert, $\text{Byzantine Agreement with Predictions}$, PODC 2025) we study synchronous binary Byzantine Agreement in the learning-augmented setting, where each process receives predictions about which processes are honest or Byzantine. We present a deterministic Phase King protocol for the anauthenticated setting, combining early stopping with a specifically designed prediction-aware king selection procedure. For at most $t<n/3$ Byzantine processes, the protocol handles arbitrarily many prediction errors, improving upon the $O(n^{3/2})$ bound of Ben-David et al., and terminates within $O(P)$ communication rounds, where $P=1+\min \{\mathbf{B}/n,f\}$, $\mathbf{B}$ is the total number of incorrect prediction bits held by honest processes, and $f$ is the actual number of Byzantine processes. Our protocol uses $O(n^{2}P)$ messages and $O(n^{2}P\log n)$ bits, avoiding the initial cubic bit cost of exchanging complete prediction vectors. In comparison to very recent independent work (Dufay, Dzulfikar, and Gilbert, $\text{Predictions Can Only Help! Communication Efficient Byzantine Agreement with Predictions}$, DISC 2026), which achieves the same error tolerance and round complexity but better communication bounds, our construction provides a much simpler Phase King approach that completely avoids involved preprocessing constructions, rendering it more practical, especially for achieving agreement in time-evolving networks. We believe that the novel prediction-aware king selection technique of our scheme is of independent interest and can find further applications in learning-augmented distributed consensus.