Information-Theoretic Lower Bounds on the Storage Cost of Shared Memory Emulation

Abstract

© 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.