Metraipolis › archive › dc_df278eff4643

Byzantine Causal Reliable Broadcast with Constant Metadata Overhead — arXiv:2609.37913

Source: arXiv (en)
Original: https://arxiv.org/abs/2609.37913
License (as archived): CC0-1.0
Archived: 2026-10-07T16:59:11.570Z
SHA-256 of the archived text: cfb745f5ddf35c10b9a9e12894cd948be851afedc74c54eb3ff4f62735ce3f69
Stable URL of this page: https://metraipolis.com/documento/dc_df278eff4643

How to cite

Byzantine Causal Reliable Broadcast with Constant Metadata Overhead — arXiv:2609.37913 — arXiv (en), https://arxiv.org/abs/2609.37913 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_df278eff4643 (Metraipolis archive dc_df278eff4643, sha256 cfb745f5ddf35c10b9a9e12894cd948be851afedc74c54eb3ff4f62735ce3f69)

BibTeX

@misc{dcdf278eff4643,
  title = {Byzantine Causal Reliable Broadcast with Constant Metadata Overhead — arXiv:2609.37913},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.37913},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_df278eff4643; sha256 cfb745f5ddf35c10b9a9e12894cd948be851afedc74c54eb3ff4f62735ce3f69},
  year = {2026}
}

Archived text

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

Asynchronous Byzantine Reliable Broadcast (BRB) is a fundamental primitive that guarantees agreement and validity in distributed systems subject to Byzantine faults, but it lacks ordering guarantees. Causal message ordering is important for many applications such as blockchain and social networking. Existing solutions for Byzantine Causal Reliable Broadcast (BCRB) have several drawbacks. Such protocols typically append vector clocks or dependency barriers to application messages, resulting in a metadata overhead that scales linearly with $n$, the number of processes in the system. In this paper, we propose the first optimal message overhead BCRB algorithm that guarantees safety. We do this by re-engineering Bracha's BRB algorithm with relatively small but critical modifications, and prove that our algorithm solves BCRB with optimal message metadata. The algorithm achieves constant-size $\mathcal{O}(1)$ message metadata overhead and $\mathcal{O}(n^2)$ messages, resulting in $\mathcal{O}(n^2)$ communication word complexity. This is as against $\mathcal{O}(n^3)$ communication word complexity of existing protocols. The algorithm tolerates $f < n/3$ Byzantine processes, which is the well-known optimal resilience bound, and uses four phases.

Tema degli esploratori: calcolo e infrastrutture (retro-catalogo arXiv: annunci del 2026-09-30 in cs.DC).
Categorie arXiv: Distributed, Parallel, and Cluster Computing (cs.DC) ; Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2609.37913 — 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-10-07T16:31:32.465Z dalla pagina https://arxiv.org/catchup/cs.DC/2026-09-30?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).