000109738 001__ 109738
000109738 005__ 20190812205104.0
000109738 037__ $$aCONF
000109738 245__ $$aAmnesic Distributed Storage
000109738 269__ $$a2007
000109738 260__ $$c2007
000109738 336__ $$aConference Papers
000109738 520__ $$aDistributed 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.
000109738 700__ $$aChockler, Gregory
000109738 700__ $$0240335$$g105326$$aGuerraoui, Rachid
000109738 700__ $$aKeidar, Idit
000109738 773__ $$tProceedings of the 21st International Symposium on Distributed Computing (DISC'07)
000109738 909C0 $$xU10407$$pDCL$$0252114
000109738 909CO $$pconf$$pIC$$ooai:infoscience.tind.io:109738
000109738 937__ $$aLPD-CONF-2007-014
000109738 973__ $$rREVIEWED$$sPUBLISHED$$aEPFL
000109738 980__ $$aCONF