From Partial to Global Asynchronous Reliable Broadcast

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 trade-off between the size b and the corruption threshold t. We answer this question by showing feasibility and impossibility results:  
- A reliable broadcast protocol Π_{RBC} that:  
- For 3 ≤ b ≤ 4, is secure up to t < n/2 corruptions. 
- For b > 4 even, is secure up to t < ((b-4)/(b-2) n + 8/(b-2)) corruptions. 
- For b > 4 odd, is secure up to t < ((b-3)/(b-1) n + 6/(b-1)) corruptions.  
- A nonstop reliable broadcast Π_{nRBC}, where parties are guaranteed to obtain output as in reliable broadcast but may need to run forever, secure up to t < (b-1)/(b+1) n corruptions. 
- There is no protocol for (nonstop) reliable broadcast secure up to t ≥ (b-1)/(b+1) n corruptions, implying that Π_{RBC} is an asymptotically optimal reliable broadcast protocol, and Π_{nRBC} is an optimal nonstop reliable broadcast protocol.