On the robustness of Herlihy's hierarchy

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the robustness of Herlihy's hierarchy

Full text

Pdf (1.14 MB)

Source

Annual ACM Symposium on Principles of Distributed Computing archive
Proceedings of the twelfth annual ACM symposium on Principles of distributed computing table of contents

Ithaca, New York, United States

Pages: 145 - 157

Year of Publication: 1993

ISBN:0-89791-613-1

Author

Prasad Jayanti

Sponsors

SIGOPS: ACM Special Interest Group on Operating Systems
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 0, Downloads (12 Months): 14, Citation Count: 21

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/164051.164070 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	AGTV92	Yehuda Afek , Eli Gafni , John Tromp , Paul M. B. Vitányi, Wait-free Test-and-Set (Extended Abstract), Proceedings of the 6th International Workshop on Distributed Algorithms, p.85-94, November 02-04, 1992
	AR92	Y. Aumann and M.O. Rabin. Clock construction in fully asynchronous parallel systems and pram simulation. In Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, October 1992.
	CHP71	P. J. Courtois , F. Heymans , D. L. Parnas, Concurrent control with “readers” and “writers”, Communications of the ACM, v.14 n.10, p.667-668, Oct. 1971 [doi>10.1145/362759.362813]
	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]
	DDS87	Danny Dolev , Cynthia Dwork , Larry Stockmeyer, On the minimal synchronism needed for distributed consensus, Journal of the ACM (JACM), v.34 n.1, p.77-97, Jan. 1987 [doi>10.1145/7531.7533]
	Her91a	Maurice Herlihy, Impossibility results for asynchronous PRAM (extended abstract), Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.327-336, July 21-24, 1991, Hilton Head, South Carolina, United States [doi>10.1145/113379.113409]
	Her91b	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]
	Jay93	P. Jayanti. On the robustness of herlihy's hierarchy. Technical Report TR 93- 1332, CorneI1 University, Dept. of Computer Science, Cornell University, Ithaca, NY 14853, March 1993.
	JT92	Prasad Jayanti , Sam Toueg, Some Results on the Impossibility, Universality, and Decidability of Consensus, Proceedings of the 6th International Workshop on Distributed Algorithms, p.69-84, November 02-04, 1992
	KM	Jon Kleinberg , Sendhil Mullainathan, Resource bounds and combinations of consensus objects, Proceedings of the twelfth annual ACM symposium on Principles of distributed computing, p.133-143, August 15-18, 1993, Ithaca, New York, United States [doi>10.1145/164051.164069]
	LAA87	M.C. Loui and Abu-Amara. Memory requirements for agreement among unreliable asynchronous processes. Advances in computing research, 4:163-183, 1987.
	Lam77	Leslie Lamport, Concurrent reading and writing, Communications of the ACM, v.20 n.11, p.806-811, Nov. 1977 [doi>10.1145/359863.359878]
	Plo89	S. A. Plotkin, Sticky bits and universality of consensus, Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, p.159-175, June 1989, Edmonton, Alberta, Canada [doi>10.1145/72981.72992]

CITED BY 21

	Wai-Kau Lo , Vassos Hadzilacos, All of us are smarter than any of us: wait-free hierarchies are not robust, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.579-588, May 04-06, 1997, El Paso, Texas, United States
	Tushar Chandra , Vassos Hadzilacos , Prasad Jayanti , Sam Toueg, Wait-freedom vs. t-resiliency and the robustness of wait-free hierarchies (extended abstract), Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.334-343, August 14-17, 1994, Los Angeles, California, United States
	Elizabeth Borowsky , Eli Gafni , Yehuda Afek, Consensus power makes (some) sense! (extended abstract), Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.363-372, August 14-17, 1994, Los Angeles, California, United States
	Yehuda Afek , Gideon Stupp, Delimiting the power of bounded size synchronization objects (extended abstract), Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.42-51, August 14-17, 1994, Los Angeles, California, United States
	Yehuda Afek , Michael Merritt , Gadi Taubenfeld, The power of multi-objects (extended abstract), Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.213-222, May 23-26, 1996, Philadelphia, Pennsylvania, United States
	Gil Neiger, Failure detectors and the wait-free hierarchy (extended abstract), Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.100-109, August 20-23, 1995, Ottowa, Ontario, Canada
	Jon Kleinberg , Sendhil Mullainathan, Resource bounds and combinations of consensus objects, Proceedings of the twelfth annual ACM symposium on Principles of distributed computing, p.133-143, August 15-18, 1993, Ithaca, New York, United States
	Eric Ruppert, Determining consensus numbers, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.93-99, August 21-24, 1997, Santa Barbara, California, United States
	Wai-Kau Lo , Vassos Hadziolacos, On the power of shared object types to implement one-resilient Consensus, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.101-110, August 21-24, 1997, Santa Barbara, California, United States
	Wai-Kau Lo, More on t-resilience vs. wait-freedom (extended abstract), Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.110-119, August 20-23, 1995, Ottowa, Ontario, Canada
	Eric Shenk, The consensus hierarchy is not robust, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.279, August 21-24, 1997, Santa Barbara, California, United States
	Gary L. Peterson, Properties of a family of booster types, Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing, p.281, May 04-06, 1999, Atlanta, Georgia, United States
	Wai-Kau Lo , Vassos Hadzilacos, On the power of shared object types to implement one-resilient Consensus, Distributed Computing, v.13 n.4, p.219-238, November 2000
	Maurice Herlihy, On beyond registers: wait-free readable objects, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.26-42, August 2001, Newport, Rhode Island, United States
	Prasad Jayanti, Robust wait-free hierarchies, Journal of the ACM (JACM), v.44 n.4, p.592-614, July 1997
	Rida A. Bazzi , Gil Neiger , Gary L. Peterson, On the use of registers in achieving wait-free consensus, Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.354-362, August 14-17, 1994, Los Angeles, California, United States
	Rida A. Bazzi , Gil Neiger , Gary L. Peterson, On the use of registers in achieving wait-free consensus, Distributed Computing, v.10 n.3, p.117-127, April 1997
	Maurice Herlihy , Sergio Rajsbaum, A classification of wait-free loop agreement tasks, Theoretical Computer Science, v.291 n.1, p.55-77, 4 January 2003
	Eric Goubault, Geometry and concurrency: a user's guide, Mathematical Structures in Computer Science, v.10 n.4, p.411-425, August 2000
	Gary L. Peterson , Rida A. Bazzi , Gil Neiger, A gap theorem for consensus types extended abstract, Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.344-353, August 14-17, 1994, Los Angeles, California, United States
	Lisbeth Fajstrup , Martin Raußen , Eric Goubault, Algebraic topology and concurrency, Theoretical Computer Science, v.357 n.1, p.241-278, 25 July 2006