Reaching Consensus in a Dual Fallible Scale Free Network

Abstract

Consensus problem plays a key role in the design of fault tolerant distributed system. Over the years, a number of solutions to consensus problem have been proposed with varying assumption of the network structures. However, most existing consensus protocols are designed for random networks. Recently, many large complex networks have emerged and displayed a scale free feature, which influences the system to reach a different common value. Unfortunately, existing consensus protocols and results cannot cope with the new network environment and the consensus problem thus needs to be revisited. The proposed protocol is called as the dual TM protocol (DTMP), which can make each correct processor reach a consensus value to cope with the faulty component in the scale free network. However, DTMP can make all correct processors reaching consensus with two rounds of message exchange and tolerate the maximum number of allowable components.