Amnesic Distributed Storage

Distributed storage algorithms implement the abstraction of a shared register over distributed base objects. We study a specific class of storage algorithms, which we call amnesic: these have the pragmatic property that old values written in the implemented register might be eventually forgotten, i.e., they are not permanently kept in the storage and might be overwritten in the base objects by more recent values. This paper precisely captures this property and argues that most storage algorithms are amnesic. We establish a fundamental impossibility of an amnesic storage algorithm to implement a robust register abstraction over a set of base objects of which at least one can fail arbitrarily, even if only in a responsive manner, unless readers are allowed to write to the base objects. Our impossibility helps justify the assumptions made by practical robust storage algorithms. We also derive from this impossibility the first sharp distinction between safe and regular registers. Namely, we show that, if readers do not write, then no amnesic algorithm can implement a regular register using safe registers.