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

View/ Open
Date
2010-08Author
Savva, AndreasPublisher
Πανεπιστήμιο Κύπρου, Σχολή Θετικών και Εφαρμοσμένων Επιστημών / University of Cyprus, Faculty of Pure and Applied SciencesPlace of publication
CyprusGoogle Scholar check
Metadata
Show full item recordAbstract
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.