Communication Efficient Byzantine Agreement with Predictions
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914562550267904 |
|---|---|
| author | Dzulfikar, Muhammad Ayaz Gilbert, Seth |
| author_facet | Dzulfikar, Muhammad Ayaz Gilbert, Seth |
| contents | 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 $Ω(f)$ round lower bound. However, existing algorithms either handle limited prediction errors or send too many messages. Moreover, they all exchange $Ω(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 (and sharing of predictions) is not inherent by developing an unauthenticated algorithm with $\tilde{O}(n^{2.5})$ communication complexity. Furthermore, with authentication, we give an algorithm with optimal $O(n^2κ)$ communication complexity (where $κ$ is a security parameter). All of our results have optimal round complexity for any number of errors in the predictions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_12935 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Communication Efficient Byzantine Agreement with Predictions Dzulfikar, Muhammad Ayaz Gilbert, Seth Distributed, Parallel, and Cluster Computing 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 $Ω(f)$ round lower bound. However, existing algorithms either handle limited prediction errors or send too many messages. Moreover, they all exchange $Ω(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 (and sharing of predictions) is not inherent by developing an unauthenticated algorithm with $\tilde{O}(n^{2.5})$ communication complexity. Furthermore, with authentication, we give an algorithm with optimal $O(n^2κ)$ communication complexity (where $κ$ is a security parameter). All of our results have optimal round complexity for any number of errors in the predictions. |
| title | Communication Efficient Byzantine Agreement with Predictions |
| topic | Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2605.12935 |