Abstract:In Byzantine agreement with predictions each process begins with an input value and some (unreliable) prediction bits. Recently, it has been shown that with \emph{classification predictions}---where the predictions predict each process to be honest or faulty---Byzantine agreement can be completed more quickly than without predictions, circumventing the traditional $\Omega(f)$ round lower bound. However, existing algorithms either handle limited prediction errors or send too many messages. Moreover, they all exchange $\Omega(n^3)$ bits---enough to allow the processes to approximately agree on the classifications. In fact, it almost seemed necessary to share a significant number of prediction bits if one wanted to tolerate a high number of incorrect predictions.
In this paper, we show that this high level of communication is not inherent to a round-efficient protocol with predictions. We provide an unauthenticated algorithm with near-optimal $\tilde{\mathcal{O}}(n^2)$ communication complexity and optimal resilience $t < n/3$. Furthermore, with authentication, we give an algorithm with optimal $\mathcal{O}(n^2\kappa)$ communication complexity (where $\kappa$ is a security parameter) and near-optimal resilience $t < (\frac{1}{2} - \epsilon)n$ for any constant $\epsilon > 0$. All of our results have optimal round complexity for any number of errors in the predictions.
From: Muhammad Ayaz Dzulfikar [view email]
[v1]
Wed, 13 May 2026 03:14:51 UTC (40 KB)
[v2]
Wed, 12 Aug 2026 07:07:48 UTC (57 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。