On the Power of Imperfect Broadcast

A fundamental result in information-theoretic fault-tolerant distributed computing is that unconditionally secure broadcast (or Byzantine agreement) among three players is impossible if one player is misbehaving. In particular, imperfect broadcast with failure probability epsi is achievable if and only if epsi ges (3 - radic5)/2. In this paper, we examine to what extent the failure probability of imperfect broadcast can be reduced. As a main result, we show that, among three players, broadcast with failure probability epsi can be turned into broadcast with negligible failure probability if and only if epsi < 1/3. This result is finally extended to the more general case of n players and any number of misbehaving players