Capacity of byzantine agreement
Guanfeng Liang, Nitin H. Vaidya · 2010
In this paper, we consider the problem of maximizing the throughput of Byzantine agreement, for two cases: i. communication link's capacity is fixed; and ii. the sum capacity of all links in the system is fixed. Byzantine 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. In case i, we characterize the maximum achievable agreement throughput in four-node networks. In case ii, we identify sufficient condition for achieving agreement throughput R.