Fault-Diagnosis and Decision Making Algorithm for Determining Faulty Nodes in Malicious Networks

Introduction

Decision making and consensus in an unreliable environment is an important issue that has received significant amount of attention in the literature (Maggs et al. 2012; Pasqualetti et al. 2012; Olfati-Saber et al. 2007). Recent interests in research in the area of unmanned vehicles have led to design of automatic control systems. On the other hand, the problem of consensus in a distributed system is vital for members in order to have a reliable system. Researchers have considered the consensus problem from two different approaches. From the first point of view, researchers consider all network members as a healthy unit (Maggs et al. 2012; Alekeish & Ezhilchelvan 2012; Kar & Moura 2007). Therefore, there is no adverse condition affecting the consensus process. Maggs et al. (Maggs et al. 2012) proposed an average consensus protocol for the clock synchronization problem in wireless sensor networks. They proposed a consensus approach to compensate clock function in each unit. However, there are many systems subject to failures. Therefore, the consensus problem also has been considered in systems with faulty units. Byzantine Agreement (BA) (Lamport et al. 1982; Cheng et al. 2008; Lee & Ewe 2007; Okun 2009; Wang et al. 2010) problem is one of the well-known problems in the area of distributed consensus introduced by Lamport et al. (Lamport et al. 1982) and since then various algorithms have been proposed for different network models (Cheng et al. 2008; Khosravi et al. 2011; Chiang et al. 2010; Wang & Yan 2000; Lamport et al. 1982). While Byzantine agreement has been studied extensively over the years, the original model has been mostly continued to be used for different topologies (Wang et al. 2010; Lee & Ewe 2007). In (Lamport et al. 1982), the authors presented an algorithm to solve BA problem in rounds for the first time, where is the number of arbitrary faulty processors in network , , and . The main goal of different studies is to develop an optimum algorithm in terms of number of message exchange rounds and number of communication bits and also to increase maximum number of allowable faulty units in the system. However, many protocols have been designed for solving the BA problem in different network structures like generalized connected and ad hoc networks (Cheng et al. 2008; Chiang et al. 2010; Yan & Wang 2005) and different fault models (Meyer & Pradhan 1991; Siu et al. 1998; Siu et al. 1996). In general, all of the protocols designed for BA problem must satisfy the following conditions:

• •

  All fault-free processors agree on a common value.

• •

  If the source processor is fault-free then all fault-free processors find the source initial value as the agreement value.