Metraipolis › archive › dc_42ebb8748cc9

A Simple Phase-King Protocol with Predictions — arXiv:2611.11370

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.11370
License (as archived)
CC0-1.0
Archived
2026-11-10T18:45:45.414Z
SHA-256 of the archived text
3443a8033af07280199e9adefa06c0e24db6c944d68616cc9b75f835e5437314
Stable URL of this page
https://metraipolis.com/documento/dc_42ebb8748cc9

How to cite

A Simple Phase-King Protocol with Predictions — arXiv:2611.11370 — arXiv (en), https://arxiv.org/abs/2611.11370 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_42ebb8748cc9 (Metraipolis archive dc_42ebb8748cc9, sha256 3443a8033af07280199e9adefa06c0e24db6c944d68616cc9b75f835e5437314)
BibTeX
@misc{dc42ebb8748cc9,
  title = {A Simple Phase-King Protocol with Predictions — arXiv:2611.11370},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.11370},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_42ebb8748cc9; sha256 3443a8033af07280199e9adefa06c0e24db6c944d68616cc9b75f835e5437314},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.11370. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Inspired by recent work (Ben-David, Dzulfikar, Ellen, and Gilbert, $\textit{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^2P)$ messages and $O(n^2P\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, $\textit{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.

Tema degli esploratori: calcolo e infrastrutture (elenco arXiv cs.DC, nuovi lavori del giorno).
Categorie arXiv: Distributed, Parallel, and Cluster Computing (cs.DC).
Pagina del lavoro: https://arxiv.org/abs/2611.11370 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-10T18:38:07.442Z dalla pagina https://arxiv.org/list/cs.DC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).