Capacity of Byzantine Consensus in Capacity Limited Point-to-Point Networks

Date Added: Dec 2011
Format: PDF

In this paper, the authors investigate the problem of maximizing the throughput, i.e., achieving capacity, of Byzantine consensus in point-to-point networks, in which each link has a capacity constraint. They derive an upper bound of the capacity of consensus in general point-to-point networks, and prove its tightness in 4-node complete networks by construction. They also provide a probabilistically correct algorithm that achieves the upper bound in general networks. In the last decade, they observe a tremendous growth in the popularity of data oriented online services, such as cloud computing, data centers and online storage. More and more enterprises run their critical business applications on data centers.