Dynamic Atomic Storage without Consensus
Dynamic Atomic Storage without Consensus
复制标题
DOI：
10.1145/1944345.1944348
复制
发表时间：
2011-04-01
影响因子：
2.5
通讯作者：
Shraer, Alexander
中科院分区：
文献类型：
--
作者：
Aguilera, Marcos K.;Keidar, Idit;Shraer, Alexander
本文讨论动态异步消息传递系统中原子读/写（R/W）存储的仿真。在静态设置中，众所周知，即使系统完全异步，原子R/W存储也可以以容错方式实现，而共识是不可解决的。相比之下，所有现有的仿真原子存储在动态系统中依赖于共识或更强的原语，导致一个流行的信念，即动态R/W存储是无法实现的没有consense.In这篇文章中，我们指定的问题，动态原子读/写存储的用户提供的接口，这样的存储。我们发现，也许令人惊讶的是，动态R/W存储是可解决的，在一个完全异步的系统：我们提出DynaStore，算法，解决了这个问题。我们的结果表明，原子R/W存储实际上比共识更容易，即使在动态系统中。
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.