Implementing Self-stabilizing Byzantine Fault-tolerant State-machine Replication: a Proof of Concept, Validation and Preliminary Evaluation

Examensarbete för masterexamen

Please use this identifier to cite or link to this item:
Download file(s):
File Description SizeFormat 
CSE 19-55 Niklasson_Peterson.pdfImplementing Self-stabilizing Byzantine Fault-tolerant State-machine Replication30.63 MBAdobe PDFThumbnail
Bibliographical item details
Type: Examensarbete för masterexamen
Title: Implementing Self-stabilizing Byzantine Fault-tolerant State-machine Replication: a Proof of Concept, Validation and Preliminary Evaluation
Authors: Niklasson, Axel
Petersson, Therese
Abstract: As the usage of cloud-based services increases, so does the demand on high availability and reliability on these services, which can be achieved using state machine replication. This project covers the implementation of proof-of-concept, validation and preliminary evaluation of the Self-Stabilizing Byzantine Tolerant Replicated State Machine Based on Failure Detectors algorithm presented by Dolev, Georgiou, Marcoullis and Schiller. We are the first to implement and practically validate the algorithm, along with performing a preliminary evaluation using the PlanetLab EU platform. The implemented codebase along with its extensive tooling can be used in other projects implementing and evaluation distributed algorithms and at the time of writing, the codebase is a fundamental part of two other project at the department. The main goal of this project is to perform a practical validation of the algorithm, which has successfully shown that the algorithm performs correctly for all implemented test cases. The primary implementation of the algorithm is implemented as a list supporting only append operations, similar to a blockchain. The second implementation removes all overhead related to an ever-growing list and only supports a “no operation” operation. The result from the preliminary evaluation, conducted with both implementations, indicate that the overhead introduced by self-stabilization increases as the number of nodes increases and is also depending on the chosen state machine. It has been shown that the system performs best with a minimum (six) number of nodes. Furthermore, it has also been shown that such a system is able to converge to a serviceable system state within seconds, which compared to human intervention can be considered to be very satisfactory.
Keywords: Computer Science;engineering;self-stabilization;Byzantine fault-tolerance;failure detection;replicated state machine;cloud storage
Issue Date: 2019
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.