Information-Theoretic Lower Bounds on the Storage Cost of Shared Memory Emulation
© 2016 ACM. The focus of this paper is to understand storage costs of em- ulating an atomic shared memory over an asynchronous, dis- tributed message passing system. Previous literature has de- veloped several shared memory emulation algorithms based on replication and erasure coding techniques, and...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Association for Computing Machinery (ACM)
2021
|
| Online Access: | https://hdl.handle.net/1721.1/137752 |
| _version_ | 1826204525682229248 |
|---|---|
| author | Cadambe, Viveck R. Wang, Zhiying Lynch, Nancy |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Cadambe, Viveck R. Wang, Zhiying Lynch, Nancy |
| author_sort | Cadambe, Viveck R. |
| collection | MIT |
| description | © 2016 ACM. The focus of this paper is to understand storage costs of em- ulating an atomic shared memory over an asynchronous, dis- tributed message passing system. Previous literature has de- veloped several shared memory emulation algorithms based on replication and erasure coding techniques, and analyzed the storage costs of the proposed algorithms. In this pa- per, we present the first known information-theoretic lower bounds on the storage costs incurred by shared memory em- ulation algorithms. Our storage cost lower bounds are uni- versally applicable, that is, we make no assumption on the structure of the algorithm or the method of encoding the data. We consider an arbitrary algorithm A that implements an atomic multi-writer-single-reader (MWSR) shared memory variable whose values come from a finite set V over a system of N servers connected by point-to-point asynchronous links. We require that in every fair execution of algorithm A where the number of server failures is smaller than a parameter f, every operation invoked at a non-failing client terminates. We define the storage cost of a server in algorithm A as the logarithm (to base 2) of the number of states it can take on; the total storage cost of algorithm A is the sum of the storage cost of all servers. Previously, it was known that the storage cost cannot be smaller than N/N-f log2 |V|. We develop three new lower bounds on the storage cost of algorithm A. • In our first lower bound, we show that if algorithm A does not use server gossip, then the total storage cost is lower bounded by 2N/N-f+1 log2 |V| - o(log2 |V|). • In our second lower bound we show that the total stor- age cost is at least 2N/N-f+2 log2 |V| - o(log2 |V|) even if the algorithm uses server gossip. • In our third lower bound, we consider algorithms where the write protocol sends information about the value in at most one phase. For such algorithms, we show that the total storage cost is at least v∗ N/N-f+v∗-1 log2(|V|) -o(log2(|V|), where v∗ is the minimum of f + 1 and the number of active write operations of an execution. Our first and second lower bounds are approximately twice as strong as the previously known bound of N/N-f log2 |V|. Furthermore, our first two lower bounds apply even for regu- lar, single-writer-single-reader (SWSR) shared memory em- ulation algorithms. Our third lower bound is much larger than our first and second lower bounds, although it is appli- cable to a smaller class of algorithms where the write proto- col has certain restrictions. In particular, our third bound is comparable to the storage cost achieved by most shared memory emulation algorithms in the literature, which nat- urally fall under the class of algorithms studied. Our proof ideas are inspired by recent results in coding theory. |
| first_indexed | 2024-09-23T12:56:36Z |
| format | Article |
| id | mit-1721.1/137752 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T12:56:36Z |
| publishDate | 2021 |
| publisher | Association for Computing Machinery (ACM) |
| record_format | dspace |
| spelling | mit-1721.1/1377522022-09-28T11:03:33Z Information-Theoretic Lower Bounds on the Storage Cost of Shared Memory Emulation Cadambe, Viveck R. Wang, Zhiying Lynch, Nancy Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science © 2016 ACM. The focus of this paper is to understand storage costs of em- ulating an atomic shared memory over an asynchronous, dis- tributed message passing system. Previous literature has de- veloped several shared memory emulation algorithms based on replication and erasure coding techniques, and analyzed the storage costs of the proposed algorithms. In this pa- per, we present the first known information-theoretic lower bounds on the storage costs incurred by shared memory em- ulation algorithms. Our storage cost lower bounds are uni- versally applicable, that is, we make no assumption on the structure of the algorithm or the method of encoding the data. We consider an arbitrary algorithm A that implements an atomic multi-writer-single-reader (MWSR) shared memory variable whose values come from a finite set V over a system of N servers connected by point-to-point asynchronous links. We require that in every fair execution of algorithm A where the number of server failures is smaller than a parameter f, every operation invoked at a non-failing client terminates. We define the storage cost of a server in algorithm A as the logarithm (to base 2) of the number of states it can take on; the total storage cost of algorithm A is the sum of the storage cost of all servers. Previously, it was known that the storage cost cannot be smaller than N/N-f log2 |V|. We develop three new lower bounds on the storage cost of algorithm A. • In our first lower bound, we show that if algorithm A does not use server gossip, then the total storage cost is lower bounded by 2N/N-f+1 log2 |V| - o(log2 |V|). • In our second lower bound we show that the total stor- age cost is at least 2N/N-f+2 log2 |V| - o(log2 |V|) even if the algorithm uses server gossip. • In our third lower bound, we consider algorithms where the write protocol sends information about the value in at most one phase. For such algorithms, we show that the total storage cost is at least v∗ N/N-f+v∗-1 log2(|V|) -o(log2(|V|), where v∗ is the minimum of f + 1 and the number of active write operations of an execution. Our first and second lower bounds are approximately twice as strong as the previously known bound of N/N-f log2 |V|. Furthermore, our first two lower bounds apply even for regu- lar, single-writer-single-reader (SWSR) shared memory em- ulation algorithms. Our third lower bound is much larger than our first and second lower bounds, although it is appli- cable to a smaller class of algorithms where the write proto- col has certain restrictions. In particular, our third bound is comparable to the storage cost achieved by most shared memory emulation algorithms in the literature, which nat- urally fall under the class of algorithms studied. Our proof ideas are inspired by recent results in coding theory. 2021-11-08T18:09:26Z 2021-11-08T18:09:26Z 2016-07 2019-06-13T14:46:36Z Article http://purl.org/eprint/type/ConferencePaper https://hdl.handle.net/1721.1/137752 Cadambe, Viveck R., Wang, Zhiying and Lynch, Nancy. 2016. "Information-Theoretic Lower Bounds on the Storage Cost of Shared Memory Emulation." en 10.1145/2933057.2933118 Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Association for Computing Machinery (ACM) arXiv |
| spellingShingle | Cadambe, Viveck R. Wang, Zhiying Lynch, Nancy Information-Theoretic Lower Bounds on the Storage Cost of Shared Memory Emulation |
| title | Information-Theoretic Lower Bounds on the Storage Cost of Shared Memory Emulation |
| title_full | Information-Theoretic Lower Bounds on the Storage Cost of Shared Memory Emulation |
| title_fullStr | Information-Theoretic Lower Bounds on the Storage Cost of Shared Memory Emulation |
| title_full_unstemmed | Information-Theoretic Lower Bounds on the Storage Cost of Shared Memory Emulation |
| title_short | Information-Theoretic Lower Bounds on the Storage Cost of Shared Memory Emulation |
| title_sort | information theoretic lower bounds on the storage cost of shared memory emulation |
| url | https://hdl.handle.net/1721.1/137752 |
| work_keys_str_mv | AT cadambeviveckr informationtheoreticlowerboundsonthestoragecostofsharedmemoryemulation AT wangzhiying informationtheoreticlowerboundsonthestoragecostofsharedmemoryemulation AT lynchnancy informationtheoreticlowerboundsonthestoragecostofsharedmemoryemulation |