Decision making by means of distributed consensus algorithms can be used in systems where centralized control is difficult or impossible. Algorithms that perform such a coordination in a fixed period of time - wait-free algorithms - can be beneficial in real-life distributed systems. These algorithms should be efficient and robust towards various disturbances, since the distributed consensus problem becomes non-trivial in real-life networked systems, restricted in connectivity and time.
Solutions that can solve consensus problem in such systems often decrease efficiency with stochastic disturbances. At the same time, some other algorithms can increase performance with disturbances. Employment of stochastic disturbances to promote efficiency and robustness of consensus is called randomization. Randomization has limited application to wait-free algorithms, due to the stochasticity it employs.
In this thesis we focus on wait-free algorithms for binary majority consensus with stochastic elements. First, we show that two standard algorithms, Gacs-Kurdyumov-Levin (GKL) and Simple Majority (SM) consensus, converge more often if randomized by noise and message loss in ordered and topologically random networks.
Next, we propose a Random Neighbor Majority (RNM) consensus with embedded randomization by neighbor selection. We show that with additional randomization by noise and errors RNM can outperform the GKL and SM in asynchronous environments.
Then we investigate the impact of the faulty nodes on consensus. We investigate faulty nodes with random, full, and persistent failure with different layout over the network. We show that faulty nodes with persistent failure are more adverse for binary majority consensus than faulty nodes with random and full failure. We show that randomization can promote robustness towards faulty nodes, and that RNM is more robust towards faulty nodes than GKL and SM.
We conclude the thesis with summary of results, explain open issues and discuss further research directions.