Optimal Agreement in a Generalized Scale-Free NetworkByzantine Agreement • September 5th, 2008
Contract Type FiledSeptember 5th, 2008Generally, the task in a distributed system must achieve an agreement. It requires a set of processors to agree on a common value even if some components are corrupted. There are significant studies on this agreement problem in a regularized network environment, such as the fully connected, broadcast, and multicast networks. Recently, many large complex networks have emerged and displayed a scale-free feature, which influences the system to reach a common value differently. Such a unanimity problem is called the Byzantine Agreement (BA). The BA problem is one of the most important problems in designing a fault-tolerant distributed system. Unfortunately, existing BA protocols and results cannot cope with the new network environment and the BA problem thus needs to be revisited. In this paper, a new BA protocol is proposed to adapt to the scale-free network environment and derive its bound of allowable faulty components with the minimum number of message exchanges. We have proved the cor