Date Added: Jun 2009
This paper deals with the emulation of atomic Read/Write (R/W) storage in dynamic asynchronous message passing systems. In static settings, it is well known that atomic R/W storage can be implemented in a fault-tolerant manner even if the system is completely asynchronous, whereas consensus is not solvable. In contrast, all existing emulations of atomic storage in dynamic systems rely on consensus or stronger primitives, leading to a popular belief that dynamic R/W storage is unattainable without consensus. In this paper, the authors specify the problem of dynamic atomic read/write storage in terms of the interface available to the users of such storage.