Computing with faulty shared memory

ABSTRACT

This paper addresses problems which arise in the synchronization and coordination of distributed systems which employ unreliable shared memory. We present algorithms which solve the consensus problem, and which simulate reliable shared-memory objects, despite the fact that the available memory objects (e.g. read/write registers, test-and-set registers, read-modify-write registers) may be faulty.

REFERENCES

• AAD+90: Yehuda Afek , Danny Dolev , Hagit Attiya , Eli Gafni , Michael Merritt , Nir Shavit, Atomic snapshots of shared memory, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.1-13, August 22-24, 1990, Quebec City, Quebec, Canada [doi>10.1145/93385.93394]
• Abr88: 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]
• Blo87: Bard Bloom, Constructing two-writer atomic registers, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.249-259, August 10-12, 1987, Vancouver, British Columbia, Canada [doi>10.1145/41840.41861]
• BP87: James E. Burns , Gary L. Peterson, Constructing multi-reader atomic values from non-atomic values, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.222-231, August 10-12, 1987, Vancouver, British Columbia, Canada [doi>10.1145/41840.41859]
• CIL87: 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]
• Dij74: Edsger W. Dijkstra, Self-stabilizing systems in spite of distributed control, Communications of the ACM, v.17 n.11, p.643-644, Nov. 1974 [doi>10.1145/361179.361202]
• Fis83: Michael J. Fischer, The Consensus Problem in Unreliable Distributed Systems (A Brief Survey), Proceedings of the 1983 International FCT-Conference on Fundamentals of Computation Theory, p.127-140, August 21-27, 1983
• FLM86: Michael J. Fischer , Nancy A. Lynch , Michael Merritt, Easy impossibility proofs for distributed consensus problems, Distributed Computing, v.1 n.1, p.26-39, Jan. 1986 [doi>10.1007/BF01843568]
• FLP85: 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]
• FMRT90: M. J. Fischer , S. Moran , R. Rudich , G. Taubenfeld, The wakeup problem, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.106-116, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100228]
• FMT91: M.J. Fischer, S. Moran, and G. Taubenfeld. Spaceefficient asynchronous consensus without shared memory initialization. Submitted for publication, 1991.
• Her91: 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]
• HW90: Maurice P. Herlihy , Jeannette M. Wing, Linearizability: a correctness condition for concurrent objects, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.3, p.463-492, July 1990 [doi>10.1145/78969.78972]
• Lam86: L. Lamport. On interprocessor communication, parts I and II. Distributed Computing, 1:77-101, 1986.
• LA87: C. M. Lout and H. Abu-Amara. Memory requirements for agreement among unreliable asynchronous processors. Advances in Computing Research, 4:163-183, 1987.
• LTV89: M. Li, J. Tromp, and P. M.B. Vitanyi. How to share concurrent wait-free variables. In ICALP, 1989. Expanded vetsign: Report CS-R8916, CWI, Amsterdam, April 1989.
• LT87: Nancy A. Lynch , Mark R. Tuttle, Hierarchical correctness proofs for distributed algorithms, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.137-151, August 10-12, 1987, Vancouver, British Columbia, Canada [doi>10.1145/41840.41852]
• MTY92: Shlomo Moran , Gadi Taubenfeld , Irit Yadin, Concurrent counting, Proceedings of the eleventh annual ACM symposium on Principles of distributed computing, p.59-70, August 10-12, 1992, Vancouver, British Columbia, Canada [doi>10.1145/135419.135434]
• NW87: Richard Newman-Wolfe, A protocol for wait-free, atomic, multi-reader shared variables, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.232-248, August 10-12, 1987, Vancouver, British Columbia, Canada [doi>10.1145/41840.41860]
• Pet83: Gary L. Peterson, Concurrent Reading While Writing, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.1, p.46-55, Jan. 1983 [doi>10.1145/357195.357198]
• PF77: Gary L. Peterson , Michael J. Fischer, Economical solutions for the critical section problem in a distributed system (Extended Abstract), Proceedings of the ninth annual ACM symposium on Theory of computing, p.91-97, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803398]
• PB87: G. L. Peterson and Burns J. E. Concurrent reading while writing II: The multi-writer case. In Proc. 28th IEEE Syrup. on Foundations of Computer Science, 383-392, 1987.
• Plo88: S. A. Plotkin. Chapter J: Sticky Bits and Universality of Consensus. PhD thesis, M.I.T., August 1988. Ph.D. Thesis.
• Rab82: M. 0. Rabin. N-processor mutual exclusion with bounded waiting by 41ogr~ shared variables. Journal of Compurer and Systems Sciences, 25:66-75, 1982.
• SAG87: Ambuj K. Singh , James H. Anderson , Mohamed G. Gouda, The elusive atomic register revisited, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.206-221, August 10-12, 1987, Vancouver, British Columbia, Canada [doi>10.1145/41840.41858]
• Smi82: Alan Jay Smith, Cache Memories, ACM Computing Surveys (CSUR), v.14 n.3, p.473-530, Sept. 1982 [doi>10.1145/356887.356892]
• Tro89: John Tromp, How to Construct an Atomic Variable (Extended Abstract), Proceedings of the 3rd International Workshop on Distributed Algorithms, p.292-302, September 26-28, 1989
• TC84: R. Turpin and B. Coan. Extending binary byzantine agreement to multivalued byzantine agreement. Information Processing Letters, 18(2):73-76, 1984.
• VA86: P. M. B. Vitanyi and B. Awerbuch. Atomic shared register access by asynchronous hardware. In Proc. 2Tth iEEE Syrup. on Foundations of Computer Science, 223-243, 1986. Errata, Ibid., 1987.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Shared memory
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION

General Terms:
Algorithms, Reliability, Theory