A gap theorem for consensus types extended abstract

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A gap theorem for consensus types extended abstract

Full text

Pdf (1.18 MB)

Source

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

Los Angeles, California, United States

Pages: 344 - 353

Year of Publication: 1994

ISBN:0-89791-654-9

Authors

Gary L. Peterson	Computer Science Department, PO Box 333, Spelman College, 350 Spelman Ln SW, Atlanta, GA
Rida A. Bazzi	College of Computing, Georgia Institute of Technology, Atlanta, GA
Gil Neiger	College of Computing, Georgia Institute of Technology, Atlanta, GA

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): 7, Citation Count: 8

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/197917.198123 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.

	AWW93	Yehuda Afek , Eytan Weisberger , Hanan Weisman, A completeness theorem for a class of synchronization objects, Proceedings of the twelfth annual ACM symposium on Principles of distributed computing, p.159-170, August 15-18, 1993, Ithaca, New York, United States [doi>10.1145/164051.164071]
	BNP94	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 [doi>10.1145/197917.198124]
	Cha93	Soma Chaudhuri, More choices allow more faults: set consensus problems in totally asynchronous systems, Information and Computation, v.105 n.1, p.132-158, July 1993 [doi>10.1006/inco.1993.1043]
	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]
	HS94	Maurice Herlihy , Nir Shavit, A simple constructive computability theorem for wait-free computation, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.243-252, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195144]
	Jay93	Prasad Jayanti, On the robustness of Herlihy's hierarchy, Proceedings of the twelfth annual ACM symposium on Principles of distributed computing, p.145-157, August 15-18, 1993, Ithaca, New York, United States [doi>10.1145/164051.164070]
	KM93	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]
	LA87	Michael C. Loui and Hosame H. Abu-Amara. 'Memory requirements for agreement among unreliable asynchronous processors." In Franco P. Preparata, editor, Advances ~n Computing Research, volume 4, pages 163-183. JAI Press, 1987.
	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]
	PR79	John Reif and Gary L. Peterson. "Multipleperson ~lternation." In Proc. 20th IEEE Symp. on Foundations of Computer Science, 1979, 348-363.

CITED BY 8

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