How fast can a distributed atomic read be?

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/(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".

Published in:
Proceedings of the 23rd ACM Symposium on Principles of Distributed Computing (PODC'04), 236 - 245
Presented at:
Proceedings of the 23rd ACM Symposium on Principles of Distributed Computing (PODC'04), St. John's, Newfoundland, Canada, July 25-28, 2004

 Record created 2006-04-05, last modified 2018-03-17

Download fulltext

Rate this document:

Rate this document:
(Not yet reviewed)