Byzantine Agreement with Predictions
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913819316453376 |
|---|---|
| author | Ben-David, Naama Dzulfikar, Muhammad Ayaz Ellen, Faith Gilbert, Seth |
| author_facet | Ben-David, Naama Dzulfikar, Muhammad Ayaz Ellen, Faith Gilbert, Seth |
| contents | 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 $Ω(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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_01793 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Byzantine Agreement with Predictions Ben-David, Naama Dzulfikar, Muhammad Ayaz Ellen, Faith Gilbert, Seth Distributed, Parallel, and Cluster Computing 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 $Ω(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. |
| title | Byzantine Agreement with Predictions |
| topic | Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2505.01793 |