Paper 2020/963

From Partial to Global Asynchronous Reliable Broadcast

Diana Ghinea, Martin Hirt, and Chen-Da Liu-Zhang

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 $$ parties with reliable broadcast channels. A natural question is to investigate the trade-off between the size $$ and the corruption threshold $$. We answer this question by showing feasibility and impossibility results: 1) A reliable broadcast protocol that: For $$, is secure up to $$ corruptions; For $$ even, is secure up to $$ corruptions; For $$ odd, is secure up to $$ 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 $$ corruptions. 3) There is no protocol for (nonstop) reliable broadcast secure up to $$ corruptions, implying that the reliable broadcast protocol is asymptotically optimal, and the nonstop reliable broadcast protocol is optimal.