Affiliations: Department of Information Management, Chaoyang University of Technology, 168, Jifong E. Rd., Wufong Township, Taichung County 41349, Taiwan, R.O.C., e-mail: scwang@cyut.edu.tw | Department of Business Administration, Chaoyang University of Technology, 168, Jifong E. Rd., Wufong Township, Taichung County 41349, Taiwan, R.O.C., e-mail: kqyan@cyut.edu.tw (corresponding author) | Department of Computer Science, National Chung-Hsing University, 250, Kuo Kuang Road, Taichung, Taiwan 400, R.O.C., e-mail: phd9208@cs.nchu.edu.tw
Abstract: Generally, 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. Unfortunately, existing agreement protocols and results cannot cope with the new network environment and the agreement problem thus needs to be revisited. In this paper, we propose a new agreement protocol to adapt to the scale-free network environment and derive its bound of allowable faulty TMs with two rounds of message exchange. We have proved the correctness of this protocol and analyzed its complexity. It is observed that the scale-free network with the proposed agreement protocol can tolerate more faulty TMs than the networks based on previous studies.
Keywords: Byzantine agreement, consensus, fault-tolerance, scale-free network, complex network and random network
Journal: Informatica, vol. 17, no. 1, pp. 137-150, 2006
