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.
Category / Keywords: reliable broadcast, partial broadcast Original Publication (in the same form): DISC'20 Date: received 6 Aug 2020 Contact author: lichen at inf ethz ch Available format(s): PDF | BibTeX Citation Version: 20200811:114045 (All versions of this report) Short URL: ia.cr/2020/963