Date Added: Jul 2010
In this paper, the authors consider the problem of maximizing the throughput of Byzantine agreement, when communication links have finite capacity. Byzantine agreement is a classical problem in distributed computing, with initial solutions presented in the seminal work of Pease, Shostak and Lamport. The notion of throughput here is similar to that used in the networking/communications literature on unicast or multicast traffic. The authors identify necessary conditions for an agreement throughput of R to be achievable. They also provide tight sufficient conditions by construction for agreement throughput R in four-node networks.