Capacity of Byzantine Agreement With Finite Link Capacity
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. In existing literature, the communication links are implicitly assumed to have infinite capacity. The problem changes significantly when the capacity of links is finite. They define the throughput and capacity of agreement, and identify necessary conditions of achievable agreement throughputs. The authors propose an algorithm structure for achieving agreement capacity in general networks. They also introduce capacity achieving algorithms for two classes of networks: arbitrary four-node networks with at most 1 failure; and symmetric networks of arbitrary size.