Journal of the ACM Bibliography

Hagit Attiya, Amotz Bar-Noy, and Danny Dolev. Sharing memory robustly in message-passing systems. Journal of the ACM, 42(1):124-142, January 1995. [BibTeX entry]

Copyright: Copyright 1995 by ACM, Inc. CR91: C.1.2 [multiple-instruction-stream, multiple-data-stream processors (MIMD)]; C.2.1 [distributed networks]; C.2.4; D.4.1 [concurrency, multiprocessing/multiprogramming, synchronization]; F.1.1 [relations among models] Terms: Algorithms, Theory, Reliability Keywords: Atomic registers, emulation, fault-tolerance, message passing, processor and link failures, shared memory, and wait-freedom Emulators that translate algorithms from the shared-memory model to two different message-passing models are presented. Both are achieved by implementing a wait-free, atomic, single-writer multi-reader register in unreliable, asynchronous networks. The two message-passing models considered are a complete network with processor failures and an arbitrary network with dynamic link failures.

These results make it possible to view the shared-memory model as a higher-level language for designing algorithms in asynchronous distributed systems. Any wait-free algorithm based on atomic, single-writer multi-reader registers can be automatically emulated in message-passing systems, provided that at least a majority of the processors are not faulty and remain connected. The overhead introduced by these emulations is polynomial in the number of processors in the system.

Immediate new results are obtained by applying the emulators to known shared-memory algorithms. These include, among others, protocols to solve the following problems in the message-passing model in the presence of processor or link failures: multi-writer multi-reader registers, concurrent time-stamp systems, l-exclusion, atomic snapshots, randomized consensus, and implementation of data structures.

The abstract is also available as a LaTeX file, a DVI file, or a PostScript file.

Categories and Subject Descriptors: C.1.2 [Processor Architectures]: Multiple Data Stream Architectures (Multiprocessors); C.2.1 [Computer-Communication Networks]: Network Architecture and Design -- distributed networks; C.2.4 [Computer-Communication Networks]: Distributed Systems; D.4.1 [Operating Systems]: Process Management; F.1.1 [Computation by Abstract Devices]: Models of Computation -- relations among models

General Terms: Algorithms, Theory, Reliability

Additional Key Words and Phrases: Atomic registers, emulation, fault-tolerance, message passing, processor and link failures, shared memory, and wait-freedom

Selected papers that cite this one

Selected references


  • Journal of the ACM homepage
  • Bibliography top level
  • Journal of the ACM Author Index
  • Search the HBP database