Metraipolis › archive › dc_b3bfd3fbcbd3
Byzantine Causal Reliable Broadcast (BCRB) with Constant-Size Message Metadata — arXiv:2609.24018
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.24018
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-09T06:53:04.960Z
- SHA-256 of the archived text
8a5b548ecffe5ec7e59500e483ad55b52bc1cd5602c3f64d27396ea0d613cc41- Stable URL of this page
https://metraipolis.com/documento/dc_b3bfd3fbcbd3
How to cite
Byzantine Causal Reliable Broadcast (BCRB) with Constant-Size Message Metadata — arXiv:2609.24018 — arXiv (en), https://arxiv.org/abs/2609.24018 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_b3bfd3fbcbd3 (Metraipolis archive dc_b3bfd3fbcbd3, sha256 8a5b548ecffe5ec7e59500e483ad55b52bc1cd5602c3f64d27396ea0d613cc41)
BibTeX
@misc{dcb3bfd3fbcbd3,
title = {Byzantine Causal Reliable Broadcast (BCRB) with Constant-Size Message Metadata — arXiv:2609.24018},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.24018},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_b3bfd3fbcbd3; sha256 8a5b548ecffe5ec7e59500e483ad55b52bc1cd5602c3f64d27396ea0d613cc41},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.24018. 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. In this paper, we address Byzantine Causal Reliable Broadcast (BCRB), which builds on BRB to enforce causal message ordering. We present a novel BCRB protocol that decouples causal ordering from the BRB layer, achieving constant-size $\mathcal{O}(1)$ message metadata overhead and $\mathcal{O}(n^2)$ communication word complexity as against $\mathcal{O}(n^3)$ communication word complexity of existing protocols; here $n$ is the number of processes. We present two variants of our protocol: a cryptographic version using a threshold encryption scheme and sequence gating, and its non-cryptographic version. In the cryptographic version, senders broadcast ciphertexts immediately, and decryption shares are piggybacked on out-of-band ACKs, preventing early decryption and front-running. In both versions, causal safety is achieved probabilistically. We evaluate the probability of causal safety violations using a random variable path analysis under independent exponential link delay distributions. We show that both variants satisfy liveness and the probability of weak safety violation is bounded by $\mathcal{O}(f^{-3}\cdot\ln^3 f)$, where $f$ is the upper bound on the number of Byzantine processes, and $f < n/3$ and $f=\mathcal{O}(n)$. Further, for the crypto version, we show that the probability of strong safety violation is bounded by $\mathcal{O}(f^{-1} \cdot \ln^2 f)$. We also show how to modify our two protocols to guarantee 100\% weak safety keeping $\mathcal{O}(1)$ message space overhead but with $\mathcal{O}(n^3)$ messages and $\mathcal{O}(n^3)$ communication word complexity.
Tema degli esploratori: calcolo e infrastrutture (retro-catalogo arXiv: annunci del 2026-09-22 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.24018 — 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-09T06:50:13.537Z dalla pagina https://arxiv.org/catchup/cs.DC/2026-09-22?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).