Coded Emulation of Shared Atomic Memory for Message Passing Architectures

This paper considers the communication and storage costs of emulating atomic (linearizable) multi-writer multi-reader shared memory in distributed message-passing systems. The paper contains two main contributions: (1) We present an atomic shared-memory emulation algorithm that we call Coded Atomic Storage (CAS). This algorithm uses erasure coding methods. In a storage system with N servers that is resilient to f server failures, we show that the communication 0cost of CAS is [N over N−2f]. The storage cost of CAS is unbounded. (2) We present a variant of CAS known as CAS with Garbage Collection (CASGC). The CASGC algorithm is parametrized by an integer δ and has a bounded storage cost. We show that in every execution where the number of write operations that are concurrent with a read operation is no bigger than δ, the CASGC algorithm with parameter δ satisfies atomicity and liveness. We explicitly characterize the storage cost of CASGC, and show that it has the same communication cost as CAS.United States. Air Force Office of Scientific Research (Contract FA9550-13-1-0042)National Science Foundation (U.S.) (Award CCF-1217506)National Science Foundation (U.S.) (Award 0939370-CCF)Bae Systems National Security Solutions Inc. (Award 739532-SLIN 0004