|
On the Impossibility of Robust
Storage with Constrained Space
Chockler, Guerraoui & Keidar
Abstract
We study distributed storage algorithms that emulate a read/write shared
memory abstraction over distributed base storage objects. To be practical,
it is desirable that a storage algorithm be constrained : only a bounded
number of values should be stored in each base storage object at a given
time, for the values might represent the content of large files in real
applications. To be robust, a storage algorithm should ideally tolerate
contention, asynchrony, the crash failure of the writer, as well as arbitrary
failures of any number of readers and a threshold of base objects. We
prove the impossibility of devising a constrained robust storage algorithm
with even one arbitrary failure of a base object. A corollary of our impossibility
implies the first sharp separation between safe and regular storage.
|
|
