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.
Collections
- Τμήμα Πληροφορικής [73]