Paper Info
Title
Storage-Optimized Data-Atomic Algorithms for Handling Erasures and Errors in Distributed Storage Systems
Abstract
Erasure codes are increasingly being studied in the context of implementing atomic memory objects in large scale asynchronous distributed storage systems. When compared with the traditional replication based schemes, erasure codes have the potential of significantly lowering storage and communication costs while simultaneously guaranteeing the desired resiliency levels. In this work, we propose the Storage-Optimized Data-Atomic (SODA) algorithm for implementing atomic memory objects in the multi-writer multi-reader setting. SODA uses Maximum Distance Separable (MDS) codes, and is specifically designed to optimize the total storage cost for a given fault-tolerance requirement. For tolerating f server crashes in an n-server system, SODA uses an [n, k] MDS code with k = n - f, and incurs a total storage cost of n/n-f. SODA is designed under the assumption of reliable point-to-point communication channels. The communication cost of a write and a read operation are respectively given by O(f <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> ) and n/n-f(δ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">w</sub> +1), where δ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">w</sub> denotes the number of writes that are concurrent with the particular read. In comparison with the recent CASGC algorithm [1], which also uses MDS codes, SODA offers lower storage cost while pays more on the communication cost. We also present a modification of SODA, called SODA <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">err</sub> , to handle the case where some of the servers can return erroneous coded elements during a read operation. Specifically, in order to tolerate f server failures and e error-prone coded elements, the SODAerr algorithm uses an [n, k] MDS code such that k = n - 2e - f. SODAerr also guarantees liveness and atomicity, while maintaining an optimized total storage cost of n/n-f-2e.
Year
DOI
Venue
2016
10.1109/IPDPS.2016.55
2016 IEEE International Parallel and Distributed Processing Symposium (IPDPS)
Keywords
DocType
Volume
atomicity,muti-writer multi-reader,codes for storage,storage cost,communication cost
Conference
abs/1605.01748
ISSN
ISBN
Citations 
1530-2075
978-1-5090-2141-3
2
PageRank 
References 
Authors
0.38
12
6
Name
Order
Citations
PageRank
Kishori M. Konwar110717.49
N. Prakash218911.66
Erez Kantor314513.55
Nancy A. Lynch4101701838.61
Muriel Médard56828599.31
Alexander A. Schwarzmann621.39