Welcome to the resource topic for 2020/963
Title:
From Partial to Global Asynchronous Reliable Broadcast
Authors: Diana Ghinea, Martin Hirt, 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 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: 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{b-4}{b-2} n + \frac{8}{b-2}\right) corruptions; For b > 4 odd, is secure up to t < \left(\frac{b-3}{b-1} n + \frac{6}{b-1}\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{b-1}{b+1} n corruptions. 3) There is no protocol for (nonstop) reliable broadcast secure up to t \ge \frac{b-1}{b+1} n corruptions, implying that the reliable broadcast protocol is asymptotically optimal, and the nonstop reliable broadcast protocol is optimal.
ePrint: https://eprint.iacr.org/2020/963
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .