From Partial to Global Asynchronous Reliable Broadcast

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

International Symposium on Distributed Computing — DISC 2020, Oct 2020.

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 that 1) For $3 \leq b \leq 4$ , is secure up to $t < n / 2$ corruptions; 2) For $b > 4$ even, is secure up to $t < (\frac{b - 4}{b - 2} n + \frac{8}{b - 2})$ corruptions; 3) For $b > 4$ odd, is secure up to $t < (\frac{b - 3}{b - 1} n + \frac{6}{b - 1})$ corruptions.

-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.

-There is no protocol for (nonstop) reliable broadcast secure up to $t \geq \frac{b - 1}{b + 1} n$ corruptions, implying that our reliable broadcast protocol is asymptotically optimal, and the nonstop version is optimal.

BibTeX Citation

@inproceedings{GhHiLi20,
    author       = {Diana Ghinea and Martin Hirt and Chen-Da Liu Zhang},
    title        = {From Partial to Global Asynchronous Reliable Broadcast},
    booktitle    = {International Symposium on Distributed Computing --- DISC 2020},
    year         = {2020},
    month        = {10},
}