Implementation and Evaluation of Shared Memory Emulation on top of Quorum Reconfiguration

Abstract

The purpose of this thesis is to evaluate the performance of an implementation of a self-stabilizing quorum reconfiguration algorithm by Dolev, Georgiou, Marcoullis, and Schiller[1] both in isolation and when paired with the atomic read/write shared memory emulation algorithm by Lynch and Schvartsman [2]. Furthermore, the correctness of the implementation of the reconfiguration algorithm is validated through the use of invariants and lemmas. The performance of the implemented reconfiguration algorithm and the shared memory emulation algorithm are initially evaluated in isolation in order to get the baseline performance. They are then evaluated when paired together in order to evaluate how the pairing affects the performance compared to the performance of the individual algorithms. The evaluation is done in a distributed setting and evaluated for systems consisting of between three and nine processors. The performance metrics of the evaluation are latency, number of messages sent and delivered as well as the number of full-loop iterations necessary to complete an operation. The results indicate that for this implementation, there is no significant loss in performance when pairing the reconfiguration algorithm and the shared memory emulation compared to having them executed in isolation. These results can therefore be seen as an indication that when implemented in a similar manner, having this reconfiguration algorithm is a viable option for providing quorums to another algorithm in a distributed system. In addition, our results show that the main increase in latency when scaling the number of processors is due to the increase in the data being processed, since the number of full-loop iterations necessary for an operation stays constant, even for larger processor configurations.