Distributed consensus in faulty networks

Abstract

The objective of this thesis is to develop fault tolerant consensus algorithms in the presence of two types of fault models: (i) Structured Byzantine (StrBYZ) faults that send different structured information to its in-neighbors, (ii) Unstructured Byzan tine (uStrBYZ) faults which send different random erroneous information to its in neighbors. For the StrBYZ fault model, it is shown that the network of non-faulty nodes can achieve approximate Byzantine consensus for synchronous and asynchronous networks without using a fault tolerant algorithm. Furthermore, the analysis is extended to the study of approximate Byzantine group consensus in which the non-faulty nodes reach more than one equilibrium. As opposed to the StrBYZ fault model, it is impossible to guarantee approximate Byzantine consensus under the uStrBYZ fault model without employing a fault tolerant algorithm. To remedy this situation, two fault tolerant algorithms, so called Layered Mean-Select-Reduced (L-MSR) and Rooted Mean-Select-Reduced (R-MSR) are pro posed. Necessary and sufficient conditions for the success of these algorithms for single equilibrium are presented. Moreover, it is shown that L-MSR and R-MSR algorithms can also be used to solve the approximate Byzantine group consensus problem. Another contribution of this thesis is to introduce a parameter independent fault tolerant algorithm that can be used to guarantee approximate Byzantine consensus. Using the proposed distributed fault detection scheme, the requirement on the know ledge of the number of faulty agents is relaxed. Convergence analysis for the proposed algorithm is carried out.