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 an atomic shared-memory emulation algorithm that we call Coded Atomi...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer Berlin Heidelberg
2017
|
| Online Access: | http://hdl.handle.net/1721.1/107661 https://orcid.org/0000-0003-4059-407X https://orcid.org/0000-0003-3045-265X |
| _version_ | 1826209850373177344 |
|---|---|
| author | Musial, Peter Cadambe, Viveck R. Medard, Muriel Lynch, Nancy Ann |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Musial, Peter Cadambe, Viveck R. Medard, Muriel Lynch, Nancy Ann |
| author_sort | Musial, Peter |
| 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 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 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 parameterized by an integer δ and has a bounded storage cost. We show that the CASGC algorithm satisfies atomicity. In every execution of CASGC where the number of server failures is no bigger than f, we show that every write operation invoked at a non-failing client terminates. We also show that in an execution of CASGC with parameter δ where the number of server failures is no bigger than f, a read operation terminates provided that the number of write operations that are concurrent with the read is no bigger than δ. We explicitly characterize the storage cost of CASGC, and show that it has the same communication cost as CAS. (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−2f) measured in terms of number of object values. We also discuss drawbacks of CCOAS as compared with CAS and CASGC. |
| first_indexed | 2024-09-23T14:32:45Z |
| format | Article |
| id | mit-1721.1/107661 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T14:32:45Z |
| publishDate | 2017 |
| publisher | Springer Berlin Heidelberg |
| record_format | dspace |
| spelling | mit-1721.1/1076612022-10-01T21:41:40Z A coded shared atomic memory algorithm for message passing architectures Musial, Peter Cadambe, Viveck R. Medard, Muriel Lynch, Nancy Ann Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Research Laboratory of Electronics Medard, Muriel Lynch, Nancy Ann 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 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 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 parameterized by an integer δ and has a bounded storage cost. We show that the CASGC algorithm satisfies atomicity. In every execution of CASGC where the number of server failures is no bigger than f, we show that every write operation invoked at a non-failing client terminates. We also show that in an execution of CASGC with parameter δ where the number of server failures is no bigger than f, a read operation terminates provided that the number of write operations that are concurrent with the read is no bigger than δ. We explicitly characterize the storage cost of CASGC, and show that it has the same communication cost as CAS. (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−2f) measured in terms of number of object values. We also discuss drawbacks of CCOAS as compared with CAS and CASGC. United States. Air Force Office of Scientific Research (Contract Numbers FA9550-13-1-0023, FA9550-14-1-0043) National Science Foundation (U.S.) (Award Numbers CCF-1217506, CCF-0939370, CCF-1553248) Bae Systems National Security Solutions Inc. (award 739532-SLIN 0004) 2017-03-23T16:53:52Z 2017-04-11T21:29:35Z 2016-06 2015-03 2017-02-05T04:20:14Z Article http://purl.org/eprint/type/JournalArticle 0178-2770 1432-0452 http://hdl.handle.net/1721.1/107661 Cadambe, Viveck R., Nancy Lynch, Muriel Mèdard, and Peter Musial. “A Coded Shared Atomic Memory Algorithm for Message Passing Architectures.” Distributed Computing 30, no. 1 (June 13, 2016): 49–73. doi:10.1007/s00446-016-0275-x. https://orcid.org/0000-0003-4059-407X https://orcid.org/0000-0003-3045-265X en http://dx.doi.org/10.1007/s00446-016-0275-x Distributed Computing Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ Springer-Verlag Berlin Heidelberg application/pdf Springer Berlin Heidelberg Springer Berlin Heidelberg |
| spellingShingle | Musial, Peter Cadambe, Viveck R. Medard, Muriel Lynch, Nancy Ann 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/107661 https://orcid.org/0000-0003-4059-407X https://orcid.org/0000-0003-3045-265X |
| work_keys_str_mv | AT musialpeter acodedsharedatomicmemoryalgorithmformessagepassingarchitectures AT cadambeviveckr acodedsharedatomicmemoryalgorithmformessagepassingarchitectures AT medardmuriel acodedsharedatomicmemoryalgorithmformessagepassingarchitectures AT lynchnancyann acodedsharedatomicmemoryalgorithmformessagepassingarchitectures AT musialpeter codedsharedatomicmemoryalgorithmformessagepassingarchitectures AT cadambeviveckr codedsharedatomicmemoryalgorithmformessagepassingarchitectures AT medardmuriel codedsharedatomicmemoryalgorithmformessagepassingarchitectures AT lynchnancyann codedsharedatomicmemoryalgorithmformessagepassingarchitectures |