This paper considers unconditionally secure protocols for reliable broadcast among a set of n players, some of which may be corrupted by an active (Byzantine) adversary. In the standard model with a complete, synchronous network of pairwise authentic communication channels among the players, broadcast is achievable if and only if the number of corrupted players is less than n/3. We show that, by extending this model only by the existence of a broadcast channel among three players, global broadcast is achievable if and only if the number of corrupted players is less than n/2. Moreover, for this an even weaker primitive than broadcast among three players is sufficient. All protocols are efficient.
Fitzi and Maurer REF showed that with the existence of a "two-cast channel" (i.e., broadcast channel among three players), Byzantine agreement is achievable if and only if the number of faulty processes is less than a half.
From partial consistency to global broadcast
STOC '00
Computer Science