Self-Stabilizing Services for Emulating Distributed Shared Memory on Message Passing Platforms
Ladda ner
Typ
Examensarbete för masterexamen
Master Thesis
Master Thesis
Program
Computer systems and networks (MPCSN), MSc
Publicerad
2018
Författare
Gustafsson, Robert
Lindhé, Andreas
Modellbyggare
Tidskriftstitel
ISSN
Volymtitel
Utgivare
Sammanfattning
We use self-stabilization techniques to construct a distributed service for shared memory emulation on message passing platforms. We are the first to implement and practically evaluate the self-stabilizing algorithm for atomic shared memory emulation developed by Dolev, Petig and Schiller, which in turn is the first algorithm of its kind to address privacy, malicious behaviour and self-stabilization. Furthermore, we have used techniques from the Self-Stabilizing Reconfiguration paper by Dolev et al. to create a mechanism for performing a virtually synchronous global reset of the entire system to deal with transient faults. With a firm analytical basis, these algorithms provide the tools needed to deal with arbitrary starting configurations and recover to legal behaviour within a bounded time. To show the applicability and correctness in practice, we have created an evaluation environment using PlanetLab. The evaluation shows that our implementation of the self-stabilizing version of the Coded Shared Atomic Memory algorithm (CAS) scales very well both in terms of the number of servers and in terms of the number of concurrent clients. It is shown to have only a constant overhead compared to the traditional CAS algorithm. Furthermore, the evaluation shows that it scales well with respect to data object size too—the system shows almost no slowdown for data objects up to 512 KiB, and is only slightly slower for data objects up to 1 MiB. Last but not least, the evaluation reveals that the global reset mechanism, which is the worst case scenario for handling transient faults, is as fast as a few client operations. For systems with up to 20 servers, the global reset is done within a few seconds. The same techniques used in this project can also be used to create a multitude of other self-stabilizing services and algorithms, such as self-stabilizing Paxos and self-stabilizing Virtual Synchrony to name a few.
Beskrivning
Ämne/nyckelord
Data- och informationsvetenskap , Computer and Information Science