Journal of the ACM Bibliography

Categories and Subject Descriptors: B.3.2 [Memory Structures]: Design Styles -- shared memory; B.4.3 [Input/Output and Data Communications]: Interconnections (subsystems) -- asynchronous/synchronous operations; C.1.2 [Processor Architectures]: Multiple Data Stream Architectures (Multiprocessors); D.1.3 [Programming Techniques]: Concurrent Programming; D.3.3 [Programming Languages]: Language Constructs and Features -- abstract data types; D.4.1 [Operating Systems]: Process Management; D.4.7 [Operating Systems]: Organization and Design -- distributed systems

General Terms: Algorithms, Reliability, Theory

Additional Key Words and Phrases: Asynchronous computing, fault-tolerance, implementation, MIMD, shared memory, shared objects, synchronization

Selected references

• Yehuda Afek, David S. Greenberg, Michael Merritt, and Gadi Taubenfeld. Computing with faulty shared memory (extended abstract). In Proceedings of the Eleventh Annual ACM Symposium on Principles of Distributed Computing, pages 47-58, Vancouver, British Columbia, Canada, 10-12 August 1992.

• Yehuda Afek, David S. Greenberg, Michael Merritt, and Gadi Taubenfeld. Computing with faulty shared ojects. Journal of the ACM, 42(6):1231-1274, November 1995.

• James Aspnes. Time- and space-efficient randomized consensus. In Proceedings of the Ninth Annual ACM Symposium on Principles of Distributed Computing, pages 325-331, Quebec City, Quebec, Canada, 22-24 August 1990.

• Piotr Berman, Juan A. Garay, and Kenneth J. Perry. Towards optimal distributed consensus (extended abstract). In 30th Annual Symposium on Foundations of Computer Science, pages 410-415, Research Triangle Park, North Carolina, 30 October-1 November 1989. IEEE.

• Bard Bloom. Constructing two-writer atomic registers. In Proceedings of the Sixth Annual ACM Symposium on Principles of Distributed Computing, pages 249-259, Vancouver, British Columbia, Canada, 10-12 August 1987.

• James E. Burns and Gary L. Peterson. Constructing multi-reader atomic values from non-atomic values. In Proceedings of the Sixth Annual ACM Symposium on Principles of Distributed Computing, pages 222-231, Vancouver, British Columbia, Canada, 10-12 August 1987.

• Brian A. Coan and Jennifer L. Welch. Modular construction of a Byzantine agreement protocol with optimal message bit complexity. Information and Computation, 97(1):61-85, March 1992.

• P. J. Courtois, F. Heymans, and D. L. Parnas. Concurrent control with `readers' and `writers'. Communications of the ACM, 14(10):667-668, October 1971.

• Danny Dolev, Cynthia Dwork, and Larry Stockmeyer. On the minimal synchronism needed for distributed consensus. Journal of the ACM, 34(1):77-97, January 1987.

• Danny Dolev, Ruediger Reischuk, and H. Raymond Strong. Early stopping in Byzantine agreement. Journal of the ACM, 37(4):720-741, October 1990.

• Michael J. Fischer, Nancy A. Lynch, and Michael Merritt. Easy impossibility proofs for distributed consensus problems. Distributed Computing, 1(1):26-39, 1986.

• 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.

• Maurice Herlihy. Impossibility and universality results for wait-free synchronization. In Proceedings of the Seventh Annual ACM Symposium on Principles of Distributed Computing, pages 276-290, Toronto, Ontario, Canada, 15-17 August 1988.

• Maurice Herlihy. Randomized wait-free concurrent objects (extended abstract). In Proceedings of the Tenth Annual ACM Symposium on Principles of Distributed Computing, pages 11-21, Montreal, Quebec, Canada, 19-21 August 1991.

• Maurice Herlihy. Wait-free synchronization. ACM Transactions on Programming Languages and Systems, 13(1):124-149, January 1991.

• Maurice Herlihy and Jeannette M. Wing. Linearizability: A correctness condition for concurrent objects. ACM Transactions on Programming Languages and Systems, 12(3):463-492, July 1990.

• Jon Kleinberg and Sendhil Mullainathan. Resource bounds and combinations of consensus objects. In Proceedings of the Twelth Annual ACM Symposium on Principles of Distributed Computing, pages 133-143, Ithaca, New York, USA, 15-18 August 1993.

• Leslie Lamport. Concurrent reading and writing. Communications of the ACM, 20(11):806-811, November 1977.

• Leslie Lamport. On interprocess communication. Part II: Algorithms. Distributed Computing, 1(2):86-101, 1986.

• Leslie Lamport, Robert E. Shostak, and Marshall C. Pease. The Byzantine generals problem. ACM Transactions on Programming Languages and Systems, 4(3):382-401, July 1982.

• Richard Newman-Wolfe. A protocol for wait-free, atomic, multi-reader shared variables. In Proceedings of the Sixth Annual ACM Symposium on Principles of Distributed Computing, pages 232-248, Vancouver, British Columbia, Canada, 10-12 August 1987.

• M. Pease, R. Shostak, and L. Lamport. Reaching agreement in the presence of faults. Journal of the ACM, 27(2):228-234, April 1980.

• Gary L. Peterson. A new solution to Lamport's concurrent programming problem using small shared variables. ACM Transactions on Programming Languages and Systems, 5(1):56-65, January 1983.

• 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.

• Serge A. Plotkin. Sticky bits and universality of consensus. In Proceedings of the Eighth Annual ACM Symposium on Principles of Distributed Computing, pages 159-175, Edmonton, Alberta, Canada, 14-16 August 1989.

• Fred B. Schneider. Implementing fault-tolerant services using the state machine approach: A tutorial. ACM Computing Surveys, 22(4):299-319, December 1990.

• Ambuj K. Singh, James H. Anderson, and Mohamed G. Gouda. The elusive atomic register revisited. In Proceedings of the Sixth Annual ACM Symposium on Principles of Distributed Computing, pages 206-221, Vancouver, British Columbia, Canada, 10-12 August 1987.

• T. K. Srikanth and Sam Toueg. Simulating authenticated broadcasts to derive simple fault-tolerant algorithms. Distributed Computing, 2(2):80-94, 1987.

• K. Vidyasankar. Converting Lamport's regular register to atomic register. Information Processing Letters, 28(6):287-290, 29 August 1988.

• K. Vidyasankar. An elegant 1-writer multireader multivalued atomic register. Information Processing Letters, 30(5):221-223, 13 March 1989.

• 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.

Shortcuts: