A Coded Shared Atomic Memory Algorithm 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 three main contributions: (1) We present a atomic shared-memory emulation algorithm that we call Coded Atomic...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Published: |
2014
|
| Online Access: | http://hdl.handle.net/1721.1/88551 |
| _version_ | 1811076737650393088 |
|---|---|
| author | Cadambe, Viveck R. Lynch, Nancy Medard, Muriel Musial, Peter |
| author2 | Nancy Lynch |
| author_facet | Nancy Lynch Cadambe, Viveck R. Lynch, Nancy Medard, Muriel Musial, Peter |
| author_sort | Cadambe, Viveck R. |
| collection | MIT |
| description | 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 three main contributions: (1) We present a 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 cost of CAS is N/(N-2f) . The storage cost of CAS is unbounded. (2) We present a modification of the CAS algorithm known as CAS with Garbage Collection (CASGC). The CASGC algorithm is parametrized by an integer 'd' 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 'd', the CASGC algorithm with parameter 'd' satisfies atomicity and liveness. We explicitly characterize the storage cost of CASGC, and show that it has the same communication cost as CASGC. (3) We describe an algorithm known as the Communication Cost Optimal Atomic Storage (CCOAS) algorithm that achieves a smaller communication cost than CAS and CASGC. In particular, CCOAS incurs read and write communication costs of N/(N-f) measured in terms of number of object values. We also discuss drawbacks of CCOAS as compared with CAS and CASGC. |
| first_indexed | 2024-09-23T10:26:39Z |
| id | mit-1721.1/88551 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T10:26:39Z |
| publishDate | 2014 |
| record_format | dspace |
| spelling | mit-1721.1/885512019-04-11T12:40:17Z A Coded Shared Atomic Memory Algorithm for Message Passing Architectures Cadambe, Viveck R. Lynch, Nancy Medard, Muriel Musial, Peter Nancy Lynch Theory of Computation 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 three main contributions: (1) We present a 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 cost of CAS is N/(N-2f) . The storage cost of CAS is unbounded. (2) We present a modification of the CAS algorithm known as CAS with Garbage Collection (CASGC). The CASGC algorithm is parametrized by an integer 'd' 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 'd', the CASGC algorithm with parameter 'd' satisfies atomicity and liveness. We explicitly characterize the storage cost of CASGC, and show that it has the same communication cost as CASGC. (3) We describe an algorithm known as the Communication Cost Optimal Atomic Storage (CCOAS) algorithm that achieves a smaller communication cost than CAS and CASGC. In particular, CCOAS incurs read and write communication costs of N/(N-f) measured in terms of number of object values. We also discuss drawbacks of CCOAS as compared with CAS and CASGC. 2014-08-06T18:00:06Z 2014-08-06T18:00:06Z 2014-08-01 2014-08-06T18:00:06Z http://hdl.handle.net/1721.1/88551 MIT-CSAIL-TR-2014-015 28 p. application/pdf |
| spellingShingle | Cadambe, Viveck R. Lynch, Nancy Medard, Muriel Musial, Peter A Coded Shared Atomic Memory Algorithm for Message Passing Architectures |
| title | A Coded Shared Atomic Memory Algorithm for Message Passing Architectures |
| title_full | A Coded Shared Atomic Memory Algorithm for Message Passing Architectures |
| title_fullStr | A Coded Shared Atomic Memory Algorithm for Message Passing Architectures |
| title_full_unstemmed | A Coded Shared Atomic Memory Algorithm for Message Passing Architectures |
| title_short | A Coded Shared Atomic Memory Algorithm for Message Passing Architectures |
| title_sort | coded shared atomic memory algorithm for message passing architectures |
| url | http://hdl.handle.net/1721.1/88551 |
| work_keys_str_mv | AT cadambeviveckr acodedsharedatomicmemoryalgorithmformessagepassingarchitectures AT lynchnancy acodedsharedatomicmemoryalgorithmformessagepassingarchitectures AT medardmuriel acodedsharedatomicmemoryalgorithmformessagepassingarchitectures AT musialpeter acodedsharedatomicmemoryalgorithmformessagepassingarchitectures AT cadambeviveckr codedsharedatomicmemoryalgorithmformessagepassingarchitectures AT lynchnancy codedsharedatomicmemoryalgorithmformessagepassingarchitectures AT medardmuriel codedsharedatomicmemoryalgorithmformessagepassingarchitectures AT musialpeter codedsharedatomicmemoryalgorithmformessagepassingarchitectures |