Kishori Konwar: Storage-Optimized Data-Atomic Algorithms for Handling Erasures and Errors in Distributed Storage Systems

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^2 ) and n/(n-f) x (c + 1), where c denotes the number of writes  that are concurrent with the particular read. In comparison with the recent CASGC algorithm (by Cadambe, Lynch, Muriel and Musial that appeared in NCA 2014), which also uses MDS codes, SODA offers lower storage cost while pays more on the communication cost.

We will also present a modification of SODA, called SODA_err,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 SODA_err algorithm uses an [n, k] MDS code such that k = n − 2e − f. SODA_err also guarantees liveness and atomicity, while maintaining an optimized total storage cost of n/(n−f−2e).

Collaborators: Erez Kantor, Nancy Lynch, Muriel Medard, N. Prakash and Alex Shvartsman