Dynamic atomic storage without consensus
Authors:
Open Access
- 11 April 2011
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 58 (2) , 1-32
Abstract
This article 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 article, we specify the problem of dynamic atomic read/write storage in terms of the interface available to the users of such storage. We discover that, perhaps surprisingly, dynamic R/W storage is solvable in a completely asynchronous system: we present DynaStore, an algorithm that solves this problem. Our result implies that atomic R/W storage is in fact easier than consensus, even in dynamic systems.Keywords
This publication has 16 references indexed in Scilit:
- Tight failure detection bounds on atomic object implementationsJournal of the ACM, 2010
- Reconfigurable Distributed Storage for Dynamic Networks2006
- Group communication specificationsACM Computing Surveys, 2001
- On the impossibility of group membership1996
- Sharing memory robustly in message-passing systemsJournal of the ACM, 1995
- Atomic snapshots of shared memoryJournal of the ACM, 1993
- A dynamic accessibility protocol for replicated databasesData & Knowledge Engineering, 1991
- Linearizability: a correctness condition for concurrent objectsACM Transactions on Programming Languages and Systems, 1990
- On interprocess communicationDistributed Computing, 1986
- Consistency and recovery control for replicated files1985