Self-Stabilizing Binary Consensus: Implementation and Evaluation of Self-Stabilizing Binary Consensus

Abstract

Binary consensus is a fundamental problem in distributed systems that is especially hard to solve for some system models. In this thesis, we explore binary consensus for a specifically complicated system model; A fully connected asynchronous message passing system with unreliable channels where at most a minority of processors can fail and arbitrary transient faults can happen. This system model extends the system model of previous binary consensus algorithms and is thus even more fault tolerant. One of the main challenges in distributed systems is to create algorithms that are both efficient and have high reliability and high fault-tolerance. For this thesis, the objective is to find if a binary consensus algorithm in this strict system model can be efficient. In the thesis we solved binary consensus with two different approaches, using randomization and using the class Ω of failure detectors. We then evaluated the algorithms with focus on efficiency i.e., latency. We also implemented other improvement techniques to our algorithms in order to get an even better performance. The two techniques we used was hybrids and the Look-Ahead method. By implementing all different versions of binary consensus we were able to compare their different behaviours and speculate in their usefulness for different distributed systems. From our tests we especially found that the randomized binary consensus algorithm showed very promising result regarding latency and system scalability.