Self-Stabilizing Services for Emulating Distributed Shared Memory on Message Passing Platforms

Examensarbete för masterexamen

Please use this identifier to cite or link to this item: https://hdl.handle.net/20.500.12380/255947
Download file(s):
File Description SizeFormat 
255947.pdfFulltext1.23 MBAdobe PDFView/Open
Type: Examensarbete för masterexamen
Master Thesis
Title: Self-Stabilizing Services for Emulating Distributed Shared Memory on Message Passing Platforms
Authors: Gustafsson, Robert
Lindhé, Andreas
Abstract: 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.
Keywords: Data- och informationsvetenskap;Computer and Information Science
Issue Date: 2018
Publisher: Chalmers tekniska högskola / Institutionen för data- och informationsteknik (Chalmers)
Chalmers University of Technology / Department of Computer Science and Engineering (Chalmers)
URI: https://hdl.handle.net/20.500.12380/255947
Collection:Examensarbeten för masterexamen // Master Theses



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