Evaluation of algorithms implementing multiple writer multiple reader atomic registers on planet-lab

Abstract

A lot of research has been conducted for studying efficient data survivability in distributed storage systems. A challenging question that researches attempt to address is “How can a distributed system efficiently maintain data consistency among the data replicas despite system asynchrony and failures?” Recent work introduced algorithm SFW where for the first time in the Multiple Writer Multiple Reader setting it allows for both read and write operations to be fast (the operation takes one communication round-trip to complete) but it does so by compromising the system robustness. A Server Side Ordering (SSO) technique and reader/writer predicates are utilized by algorithm SFW to allow fast operations. The goal of this thesis is to evaluate the efficiency and practicality of algorithm SFW in a realistic network environment. For this purpose, a heuristic method is used to implement the reader and writer predicates in order to efficiently search the solution space. The algorithm is implemented in C and Sockets programming and an empirical evaluation of the algorithm is performed on PlanetLab, in respect to the percentage of fast operations, CPU consumption and operation latency. The efficiency of algorithm SFW is compared to that of algorithm SIMPLE - a robust, reliable algorithm that always performs slow operations (the operation takes two communication rounds-trips to complete). It is shown that the efficiency of algorithm SFW is minor over the SIMPLE algorithm in terms of operations latency, nevertheless network resources are reduced since they are essentially traded for CPU time consumption. Furthermore, the experiments suggest that algorithm SFW is best suited in environments that exhibit large communication delay, or when the number of readers and writers is relatively small.