How fast can a distributed atomic read be?
How fast can a distributed atomic read be?
复制标题
DOI：
10.1145/1011767.1011802
复制
发表时间：
2004-07
期刊：
影响因子：
--
通讯作者：
P. Dutta;R. Guerraoui;Ron R. Levy;Arindam Chakraborty
中科院分区：
文献类型：
--
作者：
P. Dutta;R. Guerraoui;Ron R. Levy;Arindam Chakraborty
本文讨论了在异步消息传递系统上设计基本原子读写数据结构的有效实现的问题。特别是，我们考虑在单个写入器，多个读取器（也称为SWMR原子寄存器）和S服务器的情况下，这种抽象的时间有效的实现：写入器，读取器和S服务器中的t可能会因崩溃而失败。先前的实现容忍任何少数服务器的故障（即，t t-2。当t ≥ 1时，在多写入器的情况下，快速实现是不可能的。我们的结果在规则寄存器实现和原子寄存器实现的时间复杂度之间，以及单写入器实现和多写入器实现的时间复杂度之间画出了清晰的线。结果也导致重新审视，在消息传递的上下文中，民间传说定理“原子读必须写”。
This paper addresses the problem of designing an efficient implementation of a basic atomic read-write data structure over an asynchronous message-passing system. In particular, we consider time-efficient implementations of this abstraction in the case of a single writer, multiple readers (also called a SWMR atomic register) and S servers: the writer, the readers, and t out of the S servers may fail by crashing. Previous implementations tolerate the failure of any minority of servers (i.e., t t-2. We also show that a fast implementation is impossible in a multiple writers setting when t ≥ 1.Our results draw sharp lines between the time-complexity of regular and atomic register implementations, as well as between single-writer and multi-writer implementations. The results lead also to revisit, in a message-passing context, the folklore theorem that "atomic reads must write".