Fault-tolerant semifast implementations of atomic read/write registers

ABSTRACT

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. [3] 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 S<over>t - 2, where t < S<over>2 . 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., implementations that have fast reads or fast writes.This paper provides an answer to this question. It is shown that one can obtain implementations where all writes are fast, i.e., involving a single round-trip communication, and where reads complete in one to two communication rounds under the assumption that no more than t < S<over>2 servers crash. Simulated scenarios included in this paper indicate that only a small fraction of reads require a second communication round. Interestingly the correctness of the implementation does not depend on the number of concurrent readers in the system. The solution is obtained with the help of non-unique virtual ids assigned to each reader, where the readers sharing a virtual id form a virtual node. For the proposed definition of semifast implementations it is shown that implementations satisfying certain assumptions are semifast if and only if the number of virtual ids in the system is less than S<over>t - 2. This result is proved to be tight in terms of the required communication. It is shown that only a single complete two-round read operation may be necessary for each write operation. It is furthermore shown that no semifast implementation exists for the multi-reader, multi-writer model.

REFERENCES

• 1: Hagit Attiya , Amotz Bar-Noy , Danny Dolev, Sharing memory robustly in message-passing systems, Journal of the ACM (JACM), v.42 n.1, p.124-142, Jan. 1995 [doi>10.1145/200836.200869]
• 2: S. Dolev, S. Gilbert, N. Lynch, A. Shvartsman, and J. Welch. Geoquorums: Implementing atomic memory in mobile ad hoc networks, 2003.
• 3: Partha Dutta , Rachid Guerraoui , Ron R. Levy , Arindam Chakraborty, How fast can a distributed atomic read be?, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada [doi>10.1145/1011767.1011802]
• 4: Burkhard Englert , Alexander A. Shvartsman, Graceful Quorum Reconfiguration in a Robust Emulation of Shared Memory, Proceedings of the The 20th International Conference on Distributed Computing Systems ( ICDCS 2000), p.454, April 10-13, 2000
• 5: C. Georgiou, N. Nicolaou, and A. Shvartsman. Fault-tolerant semifast implementations for atomic read/write registers, 2005. http://www.cse.uconn.edu/ ncn03001/pubs/TRs/GNS06.pdf.
• 6: Nancy A. Lynch, Distributed Algorithms, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 7: Nancy A. Lynch , Alexander A. Shvartsman, RAMBO: A Reconfigurable Atomic Memory Service for Dynamic Networks, Proceedings of the 16th International Conference on Distributed Computing, p.173-190, October 28-30, 2002
• 8: N. A. Lynch , A. A. Shvartsman, Robust emulation of shared memory using dynamic quorum-acknowledged broadcasts, Proceedings of the 27th International Symposium on Fault-Tolerant Computing (FTCS '97), p.272, June 25-27, 1997
• 9: P. Vitanyi and B. Awerbuch. Atomic shared register access by asynchronous hardware. In 27th Annual IEEE Symposium on Foundations of Computer Science, pages 233--243, 1986.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.5 Reliability
          Subjects: Fault-tolerance

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.m Miscellaneous

General Terms:
Algorithms, Reliability, Theory

Keywords:
atomicity, communication rounds, distributed algorithms, fault-tolerance, read/write registers