Amortized Asynchronous Byzantine Reliable Broadcast with Optimal Resilience
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913173430337536 |
|---|---|
| author | Hu, Michael Yiqing Yan, Alvin Hong Yao Li, Jialin |
| author_facet | Hu, Michael Yiqing Yan, Alvin Hong Yao Li, Jialin |
| contents | Byzantine Reliable Broadcast (BRB) is a fundamental primitive in distributed computing and cryptographic systems; reducing the communication cost of BRB thus remains an important research direction. However, most existing works either focus strictly on the synchronous network model or utilize computationally impractical erasure codes. Therefore, to achieve a practical yet network-robust algorithm, one must turn toward committee sampling techniques. However, Committee sampling techniques often forgo optimal resilience ($f < \lfloor\frac{n}{3} \rfloor$) in the face of asynchrony.
This work produces two interesting results: Firstly, we propose a \textit{randomly asynchronous} BRB protocol that can achieve both optimal resilience and asymptotically optimal communication complexity ($O(n|m|)$) through an underutilized technique: \textit{amortization}; and does not utilize computationally expensive \textit{erasure codes}. Next, we show that an optimally resilient BRB protocol utilizing sampled committees cannot exist in a \textit{fully asynchronous} network. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_10372 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Amortized Asynchronous Byzantine Reliable Broadcast with Optimal Resilience Hu, Michael Yiqing Yan, Alvin Hong Yao Li, Jialin Distributed, Parallel, and Cluster Computing Byzantine Reliable Broadcast (BRB) is a fundamental primitive in distributed computing and cryptographic systems; reducing the communication cost of BRB thus remains an important research direction. However, most existing works either focus strictly on the synchronous network model or utilize computationally impractical erasure codes. Therefore, to achieve a practical yet network-robust algorithm, one must turn toward committee sampling techniques. However, Committee sampling techniques often forgo optimal resilience ($f < \lfloor\frac{n}{3} \rfloor$) in the face of asynchrony. This work produces two interesting results: Firstly, we propose a \textit{randomly asynchronous} BRB protocol that can achieve both optimal resilience and asymptotically optimal communication complexity ($O(n|m|)$) through an underutilized technique: \textit{amortization}; and does not utilize computationally expensive \textit{erasure codes}. Next, we show that an optimally resilient BRB protocol utilizing sampled committees cannot exist in a \textit{fully asynchronous} network. |
| title | Amortized Asynchronous Byzantine Reliable Broadcast with Optimal Resilience |
| topic | Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2605.10372 |