An Optimal Solution of Byzantine Agreement in a Scale Free Network
Kuo-Qin Yan, Shu-Ching Wang, Shun-Sheng Wang · 2008
With the fast development of Internet, in order to increase systematic operation ability, the distributed system has replaced the large-scale computer system gradually. In generally, the task in a distributed system must achieve an agreement. 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. Traditionally, this problem was well formulated in a random network. However, in recently, many large complex networks have emerged and displayed a scale free feature. It is an important topic that can represent the structure of highly fault-tolerant ability in the scale free network (SFN). In our research, the BA problem is revisited in a SFN. The proposed protocol uses the minimum number of message exchanges to reach an agreement within the distributed system while tolerating the maximum number of faulty components in SFN.