View article

This paper investigates time-efficient implementations of atomic read–write registers in message-passing systems where the number of readers can be unbounded. In particular we study the case of a single writer, multiple readers, and S servers, such that the writer, any subset of the readers, and up to t servers may crash. A recent result of Dutta et al. [P. Dutta, R. Guerraoui, R.R. Levy, A. Chakraborty, How fast can a distributed atomic read be? In: Proceedings of the 23rd ACM Symposium on Principles of Distributed Computing, 2004, pp. 236–245] shows how to obtain fast implementations in which both reads and writes complete in one communication round-trip, under the constraint that the number of readers is less than St−2, where t<S2. In that same paper the authors pose a question of whether it is possible to relax the bound on readers, and at what cost, if semifast implementations are considered, i.e …