From Partial Consistency to Global Broadcast

Matthias Fitzi and Ueli Maurer

Proc. 32nd ACM Symposium on Theory of Computing — STOC 2000, ACM, pp. 494–503, May 2000.

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.

BibTeX Citation

@inproceedings{FitMau00,
    author       = {Matthias Fitzi and Ueli Maurer},
    title        = {From Partial Consistency to Global Broadcast},
    editor       = {Frances Yao},
    booktitle    = {Proc.~32nd ACM Symposium on Theory of Computing --- STOC 2000},
    pages        = 494--503,
    year         = 2000,
    month        = 5,
    publisher    = {ACM},
}