Self-Stabilizing Binary Consensus: Implementation and Evaluation of Self-Stabilizing Binary Consensus
Ladda ner
Typ
Examensarbete för masterexamen
Program
Publicerad
2021
Författare
Sjöö, Amanda
Modellbyggare
Tidskriftstitel
ISSN
Volymtitel
Utgivare
Sammanfattning
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.
Beskrivning
Ämne/nyckelord
Binary Consensus , self-Stabilization , Arbitrary Transient Faults , Distributed Systems , Fault-Tolerance , Binary Consensus using Randomization , Failure Detectors