Novel fault-tolerant distributed algorithms for approximate Byzantine consensus

Abstract

Reaching consensus in a network which contains faulty nodes is a critical problem in the eld of distributed and multi-agent systems. A distributed system which intends to do a certain task needs to display robustness against adverse behavior of some of its faulty nodes, known also as Byzantine nodes. In this thesis, a novel Mean- Select-Reduced (MSR) fault tolerant algorithm is proposed for achieving Approximate Byzantine Consensus. It is shown that the topological condition required for the success of the algorithm is more relaxed compared to the previous results. In contrary to results that appeared in the literature, it is proved that synchronicity of networks and presence of delay on communication paths do not change this condition. Subsequently, the convergence rate and time analysis for the proposed fault-tolerant algorithm is carried out and the results are extended to time-varying networks. In most of the fault-tolerant algorithms that have been introduced for Byzantine networks, it is assumed that each node has knowledge of the maximum number of faulty nodes, ft, in the network. In this thesis, we also propose a new family of algorithms which do not require this a priori information and evaluate their performance facing Byzantine failures