Asynchronous Consensus Protocol for the Unreliable Un-fully Connected Network

Abstract

In order to achieve reliability in the distributed system, we need a mechanism to enable the system as a whole to continue to function despite the system has some faulty components. The Consensus problem is for the fault-free processors to cope with the faulty components and reach a common value from each other in the distributed system. Traditionally, the Consensus problems were solved in the synchronous network. Subsequently, Chandra and Toueg solved the Consensus problem with crash faulty processor in the asynchronous fully connected network in 1996. In this paper, we will solve the Consensus with dual failure mode (both crash fault and malicious fault) on communication links. The proposed protocol uses the minimum number of rounds of message exchange and can tolerate the maximum number of allowable faulty communication links to make each fault-free processor reach a common consensus value.