  The focus of this paper is to understand storage costs of emulating an atomic
shared memory over an asynchronous, distributed message passing system.
Previous literature has developed several shared memory emulation algorithms
based on replication and erasure coding techniques. In this paper, we present
information-theoretic lower bounds on the storage costs incurred by shared
memory emulation algorithms. Our storage cost lower bounds are universally
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
$\mathcal{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 number of
states it can take on; the total-storage cost of algorithm $A$ is the sum of
the storage cost of all servers.
  Our results are as follows. (i) We show that if algorithm $A$ does not use
server gossip, then the total storage cost is lower bounded by $2
\frac{N}{N-f+1}\log_2|\mathcal{V}|-o(\log_2|\mathcal{V}|)$. (ii) The total
storage cost is at least $2 \frac{N}{N-f+2}
\log_{2}|\mathcal{V}|-o(\log_{2}|\mathcal{V}|)$ even if the algorithm uses
server gossip. (iii) We consider algorithms where the write protocol sends
information about the value in at most one phase. We show that the total
storage cost is at least $\nu^* \frac{N}{N-f+\nu^*-1} \log_2( |\mathcal{V}|)-
o(\log_2(|\mathcal{V}|),$ where $\nu^*$ is the minimum of $f+1$ and the number
of active write operations of an execution.
