Byzantine Agreement Given Partial Broadcast

Jeffrey Considine, Matthias Fitzi, Matthew Franklin, Leonid A. Levin, Ueli Maurer, and David Metcalf

Journal of Cryptology, vol. 18, no. 3, pp. 191–217, Jul 2005.

This paper considers unconditionally secure protocols for reliable broadcast among a set of $n$ players, where up to $t$ of the players can be corrupted by a (Byzantine) adversary but the remaining $h = n - t$ players remain honest. In the standard model with a complete, synchronous network of bilateral authenticated communication channels among the players, broadcast is achievable if and only if $2 n / h < 3$ . We show that, by extending this model by the existence of partial broadcast channels among subsets of $b$ players, global broadcast can be achieved if and only if the number $h$ of honest players satisfies $2 n / h < b + 1$ . Achievability is demonstrated by protocols with communication and computation complexities polynomial in the size of the network, i.e., in the number of partial broadcast channels. A respective characterization for the related consensus problem is also given.

BibTeX Citation

@article{CFFLMM05,
    author       = {Jeffrey Considine and Matthias Fitzi and Matthew Franklin and Leonid A. Levin and Ueli Maurer and David Metcalf},
    title        = {{B}yzantine Agreement Given Partial Broadcast},
    journal      = {Journal of Cryptology},
    pages        = {191--217},
    number       = {3},
    volume       = {18},
    year         = {2005},
    month        = {7},
}

Files and Links

There are currently no associated files available.