2004 · 68 citations · 8 references
ComputingComputer EngineeringComputer ScienceComputer ArchitectureFault ToleranceMessage PassingDistributed ComputingDistributed Memory SystemsAtomic Memory OperationsMessage Passing ArchitecturesMessage Passing InterfaceMessage-passing Algorithms
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 < S/2) and require one communication round-trip for every write, and two round-trips for every read.We investigate the possibility of fast implementations, namely, implementations that complete both reads and writes in one round-trip. We show that, interestingly, the existence of a fast implementation depends on the maximum number of readers considered. More precisely, we show that a fast implementation is possible if and only if the number of readers is less that S<over>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".
8
Maurice Herlihy · ACM Transactions on Programming Languages and Systems · 1991 · 1.8K citations · Full text
Leslie Lamport · Distributed Computing · 1986 · 843 citations