Implementing Self-stabilizing Byzantine Fault-tolerant State-machine Replication: a Proof of Concept, Validation and Preliminary Evaluation
Typ
Examensarbete för masterexamen
Program
Publicerad
2019
Författare
Niklasson, Axel
Petersson, Therese
Modellbyggare
Tidskriftstitel
ISSN
Volymtitel
Utgivare
Sammanfattning
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.
Beskrivning
Ämne/nyckelord
Computer Science , engineering , self-stabilization , Byzantine fault-tolerance , failure detection , replicated state machine , cloud storage