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

Examensarbete för masterexamen

Please use this identifier to cite or link to this item:
Download file(s):
File Description SizeFormat 
CSE 21-150 Sjöö.pdf828.54 kBAdobe PDFView/Open
Bibliographical item details
Type: Examensarbete för masterexamen
Title: Self-Stabilizing Binary Consensus: Implementation and Evaluation of Self-Stabilizing Binary Consensus
Authors: Sjöö, Amanda
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.
Keywords: Binary Consensus;self-Stabilization;Arbitrary Transient Faults;Distributed Systems;Fault-Tolerance;Binary Consensus using Randomization;Failure Detectors
Issue Date: 2021
Publisher: Chalmers tekniska högskola / Institutionen för data och informationsteknik
Collection:Examensarbeten för masterexamen // Master Theses

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.