AbstractCopyright: 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
- Cynthia Dwork, Joseph Y. Halpern, and Orli Waarts. Performing work efficiently in the presence of faults. SIAM Journal on Computing, 27(5):1457-1491, October 1998.
- Dahlia Malkhi and Michael Reiter. Byzantine quorum systems. In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pages 569-578, El Paso, Texas, 4-6 May 1997.
Selected references
- Yehuda Afek, Hagit Attiya, Danny Dolev, Eli Gafni, Michael Merritt, and Nir Shavit. Atomic snapshots of shared memory. Journal of the ACM, 40(4):873-890, September 1993.
- Yehuda Afek, Baruch Awerbuch, and Eli Gafni. Applying static network protocols to dynamic networks. In 28th Annual Symposium on Foundations of Computer Science, pages 358-370, Los Angeles, California, 12-14 October 1987. IEEE.
- Hagit Attiya, Amotz Bar-Noy, Danny Dolev, David Peleg, and Rüdiger Reischuk. Renaming in an asynchronous environment. Journal of the ACM, 37(3):524-548, July 1990.
- Baruch Awerbuch. Optimal distributed algorithms for minimum weight spanning tree, counting, leader election and related problems (detailed summary). In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, pages 230-240, New York City, 25-27 May 1987.
- Baruch Awerbuch, Yishay Mansour, and Nir Shavit. Polynomial end-to-end communication (extended abstract). In 30th Annual Symposium on Foundations of Computer Science, pages 358-363, Research Triangle Park, North Carolina, 30 October-1 November 1989. IEEE.
- Benny Chor and Lior Moscovici. Solvability in asynchronous environments (extended abstract). In 30th Annual Symposium on Foundations of Computer Science, pages 422-427, Research Triangle Park, North Carolina, 30 October-1 November 1989. IEEE.
- Danny Dolev, Eli Gafni, and Nir Shavit. Toward a non-atomic era: l-exclusion as a test case. In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, pages 78-92, Chicago, Illinois, 2-4 May 1988.
- Danny Dolev and Nir Shavit. Bounded concurrent time-stamp systems are constructible. In Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing, pages 454-466, Seattle, Washington, 15-17 May 1989.
- Cynthia Dwork, David Shmoys, and Larry Stockmeyer. Flipping persuasively in constant expected time (preliminary version). In 27th Annual Symposium on Foundations of Computer Science, pages 222-232, Toronto, Ontario, Canada, 27-29 October 1986. IEEE.
- Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson. Impossibility of distributed consensus with one faulty process. Journal of the ACM, 32(2):374-382, April 1985.
- Gary L. Peterson and James E. Burns. Concurrent reading while writing II: The multi-writer case. In 28th Annual Symposium on Foundations of Computer Science, pages 383-392, Los Angeles, California, 12-14 October 1987. IEEE.
- Paul M. B. Vitányi and Baruch Awerbuch. Atomic shared register access by asynchronous hardware (detailed abstract). In 27th Annual Symposium on Foundations of Computer Science, pages 233-243, Toronto, Ontario, Canada, 27-29 October 1986. IEEE.