Journal of the ACM Bibliography

Preliminary version

A preliminary version of these results was presented in: Prasad Jayanti. On the robustness of Herlihy's hierarchy. In Proceedings of the Twelth Annual ACM Symposium on Principles of Distributed Computing, pages 145-157, Ithaca, New York, USA, 15-18 August 1993.

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 operation; 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; 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, hierarchy, implementation, MIMD, robustness, shared memory, shared objects, synchronization, wait-freedom

Selected references

• Rida A. Bazzi, Gil Neiger, and Gary L. Peterson. On the use of registers in achieving wait-free consensus. In Proceedings of the Thirteenth Annual ACM Symposium on Principles of Distributed Computing, pages 354-362, Los Angeles, California, 14-17 August 1994.

• Elizabeth Borowsky, Eli Gafni, and Yehuda Afek. Consensus power makes (some) sense! (extended abstract). In Proceedings of the Thirteenth Annual ACM Symposium on Principles of Distributed Computing, pages 363-372, Los Angeles, California, 14-17 August 1994.

• Tushar Chandra, Vassos Hadzilacos, Prasad Jayanti, and Sam Toueg. Wait-freedom vs. t-resiliency and the robustness of wait-free hierarchies. In Proceedings of the Thirteenth Annual ACM Symposium on Principles of Distributed Computing, pages 334-343, Los Angeles, California, 14-17 August 1994.

• Benny Chor, Amos Israeli, and Ming Li. On processor coordination using asynchronous hardware. In Proceedings of the Sixth Annual ACM Symposium on Principles of Distributed Computing, pages 86-97, Vancouver, British Columbia, Canada, 10-12 August 1987.

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

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

• Maurice Herlihy and Sergio Rajsbaum. Set consensus using arbitrary objects (preliminary version). In Proceedings of the Thirteenth Annual ACM Symposium on Principles of Distributed Computing, pages 324-333, Los Angeles, California, 14-17 August 1994.

• Maurice Herlihy and Nir Shavit. The asynchronous computability theorem for t-resilient tasks (preliminary version). In Proceedings of the Twenty-Fifth Annual ACM Symposium on the Theory of Computing, pages 111-120, San Diego, California, 16-18 May 1993.

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

• Prasad Jayanti. On the robustness of Herlihy's hierarchy. In Proceedings of the Twelth Annual ACM Symposium on Principles of Distributed Computing, pages 145-157, Ithaca, New York, USA, 15-18 August 1993.

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

• Gary L. Peterson, Rida A. Bazzi, and Gil Neiger. A gap theorem for consensus types (extended abstract). In Proceedings of the Thirteenth Annual ACM Symposium on Principles of Distributed Computing, pages 344-353, Los Angeles, California, 14-17 August 1994.

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

• Michael Saks and Fotios Zaharoglou. Wait-free k-set agreement is impossible: The topology of public knowledge (extended abstract). In Proceedings of the Twenty-Fifth Annual ACM Symposium on the Theory of Computing, pages 101-110, San Diego, California, 16-18 May 1993.

• Eric Schenk. The consensus hierarchy is not robust. In Proceedings of the Sixteenth Annual ACM Symposium on Principles of Distributed Computing, page 279, Santa Barbara, California, 21-24 August 1997.

Shortcuts: