Sharing memory robustly in message-passing systems

ABSTRACT

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.

REFERENCES

• 1: Karl Abrahamson, On achieving consensus using a shared memory, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.291-302, August 15-17, 1988, Toronto, Ontario, Canada [doi>10.1145/62546.62594]
• 2: Yehuda Afek , Hagit Attiya , Danny Dolev , Eli Gafni , Michael Merritt , Nir Shavit, Atomic snapshots of shared memory, Journal of the ACM (JACM), v.40 n.4, p.873-890, Sept. 1993 [doi>10.1145/153724.153741]
• 3: ~AFEK, Y., AWERBUCH, B., AND GAFNI, E. 1987. Applying static network protocols to dynamic ~networks. In Proceedings of the 28th Symposium on Foundations of Computer Science. IEEE, ~New York, pp. 358-369.
• 4: Yehuda Afek , Danny Dolev , Eli Gafni , Michael Merritt , Nir Shavit, A bound first-in, first-enabled solution to the 1-exclusion problem, Proceedings of the 4th international workshop on Distributed algorithms, p.422-432, June 1991, Bari, Italy
• 5: Eli Gafni , Yehuda Afek, End-to-end communication in unreliable networks, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.131-148, August 15-17, 1988, Toronto, Ontario, Canada [doi>10.1145/62546.62570]
• 6: Yehuda Afek , Eli Gafni, Bootstrap network resynchronization (extended abstract), Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.295-307, August 19-21, 1991, Montreal, Quebec, Canada [doi>10.1145/112600.112625]
• 7: James H. Anderson, Composite registers, Distributed Computing, v.6 n.3, p.141-154, April 1993 [doi>10.1007/BF02242703]
• 8: James Aspnes , M. Herlihy, Fast randomized consensus using shared memory, Journal of Algorithms, v.11 n.3, p.441-461, Sep. 1990 [doi>10.1016/0196-6774(90)90021-6]
• 9: J. Aspnes , M. Herlihy, Wait-free data structures in the asynchronous PRAM model, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.340-349, July 02-06, 1990, Island of Crete, Greece [doi>10.1145/97444.97701]
• 10: Hagit Attiya , Amotz Bar-Noy , Danny Dolev , David Peleg , Rüdiger Reischuk, Renaming in an asynchronous environment, Journal of the ACM (JACM), v.37 n.3, p.524-548, July 1990 [doi>10.1145/79147.79158]
• 11: H. Attiya , D. Dolev , N. Shavit, Bounded polynomial randomized consensus, Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, p.281-293, June 1989, Edmonton, Alberta, Canada [doi>10.1145/72981.73001]
• 12: B. Awerbuch, Optimal distributed algorithms for minimum weight spanning tree, counting, leader election, and related problems, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.230-240, January 1987, New York, New York, United States [doi>10.1145/28395.28421]
• 13: ~AWERBUCH, B., MANSOUR, Y., AND SHAVIT, N. 1989. Polynomial end-to-end comnmnication. In ~Proceedings of the 30th Symposium of Computer Science. IEEE, New York, pp. 358-363.
• 14: A. Bas-Noy , D. Dolev, Shared-memory vs. message-passing in an asynchronous distributed environment, Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, p.307-318, June 1989, Edmonton, Alberta, Canada [doi>10.1145/72981.73003]
• 15: Michael Ben-Or, Another advantage of free choice (Extended Abstract): Completely asynchronous agreement protocols, Proceedings of the second annual ACM symposium on Principles of distributed computing, p.27-30, August 17-19, 1983, Montreal, Quebec, Canada [doi>10.1145/800221.806707]
• 16: J. E. Burns , G. L. Peterson, The ambiguity of choosing, Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, p.145-157, June 1989, Edmonton, Alberta, Canada [doi>10.1145/72981.72991]
• 17: Benny Chor , Amos Israeli , Ming Li, On processor coordination using asynchronous hardware, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.86-97, August 10-12, 1987, Vancouver, British Columbia, Canada [doi>10.1145/41840.41848]
• 18: Benny Chor , Michael Merritt , David B. Shmoys, Simple constant-time consensus protocols in realistic failure models (extended abstract), Proceedings of the fourth annual ACM symposium on Principles of distributed computing, p.152-162, August 1985, Minaki, Ontario, Canada [doi>10.1145/323596.323610]
• 19: ~CHOR, B., AND MoscovIcI, L. 1989. Solvability in asynchronous environments. In Proceedings ~of the 30th Symposium on Foundations of Computer Science. IEEE, New York, pp. 422-427.
• 20: ~DIJKSTRA, E. W., AND SCHOLTEN, C.S. 1988. Termination detection for diffusing computations. ~Inf. Proc. Lett., 1, i (Aug)., 1-4.
• 21: Danny Dolev , Eli Gafni , Nir Shavit, Toward a non-atomic era: l-exclusion as a test case, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.78-92, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62220]
• 22: ~DOLEV, D., AND SHAVIT, N. 1987. Unpublished manuscript. July. Cited in Awerbuch et al. {1989}.
• 23: D. Dolev , N. Shavit, Bounded concurrrent time-stamp systems are constructible, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.454-466, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73051]
• 24: ~DWORK, C., SHMOYS, D., AND STOCKMEYER, L. 1986. Flipping persuasively in constant expected ~time. In Proceedings of the 27th Symposmm on Foundations of Computer Science, IEEE, New ~York, pp. 222-232.
• 25: ~FELDMAN, J. A., AND NIGAM, m. 1980. A model and proof technique for message-based ~systems. SIAM J. Computing 9, 4 (Nov). 768-784.
• 26: ~FINN, S.G. 1979. Resynch procedures and a fail-safe network protocol. IEEE Trans. Comm. ~COM-27, 840-845.
• 27: Michael J. Fischer , Nancy A. Lynch , Michael S. Paterson, Impossibility of distributed consensus with one faulty process, Journal of the ACM (JACM), v.32 n.2, p.374-382, April 1985 [doi>10.1145/3149.214121]
• 28: Maurice P. Herlihy, Impossibility and universality results for wait-free synchronization, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.276-290, August 15-17, 1988, Toronto, Ontario, Canada [doi>10.1145/62546.62593]
• 29: Maurice Herlihy, Wait-free synchronization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.1, p.124-149, Jan. 1991 [doi>10.1145/114005.102808]
• 30: Amos Israeli , Ming Li, Bounded time-stamps, Distributed Computing, v.6 n.4, p.205-209, July 1993 [doi>10.1007/BF02242708]
• 31: LAMPORT, L. 1986. On interprocess communication: Part I and II. Dist. Comput. 1, 77-101.
• 32: ~LI, M., TROMP, J. AND VITANYI, P. 1989. How to share concurrent wait-free variables. Report ~CS-R8916. CWI, Amsterdam, The Netherlands.
• 33: ~PETERSON, G. L., AND BURNS. J.E. 1987. Concurrent reading while writing II: The multiwriter ~case. In Proceedings of the 28th Symposmm on Foundations of Computer Science. IEEE, New ~York, pp. 383-392.
• 34: ~VISHK~N, U. 1983. A distributed orientation algorithm. IEEE Trans. Inf. Theory (June).
• 35: ~VITANYI, P., AND AWERBUCH, B. 1986. Atomic shared register access by asynchronous hard- ~ware. In Proceedings of the 27th Symposium on Foundations of Computer Science. IEEE, New ~York, pp. 233-243.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.4 Communications Management
          Subjects: Message sending

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Distributed networks
      C.2.4 Distributed Systems

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Concurrency; Multiprocessing/multiprogramming/multitasking; Synchronization

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Relations between models

General Terms:
Algorithms, Reliability, Theory

Keywords:
atomic registers, emulation, fault-tolerance, message passing, processor and link failures, shared memory, wait-freedom