Paper 2020/963
From Partial to Global Asynchronous Reliable Broadcast
Diana Ghinea, Martin Hirt, and ChenDa LiuZhang
Abstract
Broadcast is a fundamental primitive in distributed computing. It allows a sender to consistently distribute a message among $n$ recipients. The seminal result of Pease et al. [JACM'80] shows that in a complete network of synchronous bilateral channels, broadcast is achievable if and only if the number of corruptions is bounded by $t < n/3$. To overcome this bound, a fascinating line of works, Fitzi and Maurer [STOC'00], Considine et al. [JC'05] and Raykov [ICALP'15], proposed strengthening the communication network by assuming partial synchronous broadcast channels, which guarantee consistency among a subset of recipients. We extend this line of research to the asynchronous setting. We consider reliable broadcast protocols assuming a communication network which provides each subset of $b$ parties with reliable broadcast channels. A natural question is to investigate the tradeoff between the size $b$ and the corruption threshold $t$. We answer this question by showing feasibility and impossibility results: 1) A reliable broadcast protocol that: For $3 \le b \le 4$, is secure up to $t < n/2$ corruptions; For $b > 4$ even, is secure up to $t < \left(\frac{b4}{b2} n + \frac{8}{b2}\right)$ corruptions; For $b > 4$ odd, is secure up to $t < \left(\frac{b3}{b1} n + \frac{6}{b1}\right)$ corruptions. 2) A nonstop reliable broadcast, where parties are guaranteed to obtain output as in reliable broadcast but may need to run forever, secure up to $t < \frac{b1}{b+1} n$ corruptions. 3) There is no protocol for (nonstop) reliable broadcast secure up to $t \ge \frac{b1}{b+1} n$ corruptions, implying that the reliable broadcast protocol is asymptotically optimal, and the nonstop reliable broadcast protocol is optimal.
Metadata
 Available format(s)
 Publication info
 Published elsewhere. DISC'20
 Keywords
 reliable broadcastpartial broadcast
 Contact author(s)
 lichen @ inf ethz ch
 History
 20200811: received
 Short URL
 https://ia.cr/2020/963
 License

CC BY
BibTeX
@misc{cryptoeprint:2020/963, author = {Diana Ghinea and Martin Hirt and ChenDa LiuZhang}, title = {From Partial to Global Asynchronous Reliable Broadcast}, howpublished = {Cryptology ePrint Archive, Paper 2020/963}, year = {2020}, note = {\url{https://eprint.iacr.org/2020/963}}, url = {https://eprint.iacr.org/2020/963} }