摘要：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 4 even, is secure up to t 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.
