  Dynamic distributed storage algorithms such as DynaStore, Reconfigurable
Paxos, RAMBO, and RDS, do not ensure liveness (wait-freedom) in asynchronous
runs with infinitely many reconfigurations. We prove that this is inherent for
asynchronous dynamic storage algorithms, including ones that use $\Omega$ or
$\diamond S$ oracles. Our result holds even if only one process may fail,
provided that machines that were successfully removed from the system's
configuration may be switched off by an administrator. Intuitively, the
impossibility relies on the fact that a correct process can be suspected to
have failed at any time, i.e., its failure is indistinguishable to other
processes from slow delivery of its messages, and so the system should be able
to reconfigure without waiting for this process to complete its pending
operations.
  To circumvent this result, we define a dynamic eventually perfect failure
detector, and present an algorithm that uses it to emulate wait-free dynamic
atomic storage (with no restrictions on reconfiguration rate). Together, our
results thus draw a sharp line between oracles like $\Omega$ and $\diamond S$,
which allow some correct process to continue to be suspected forever, and a
dynamic eventually perfect one, which does not.
