All of us are smarter than any of us

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

All of us are smarter than any of us: wait-free hierarchies are not robust

Full text

Pdf (1.31 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-ninth annual ACM symposium on Theory of computing table of contents

El Paso, Texas, United States

Pages: 579 - 588

Year of Publication: 1997

ISBN:0-89791-888-6

Authors

Wai-Kau Lo	Department of Computer Science, University of Toronto, 6 King's College Rd., Toronto, Ontario, Canada, M5S 3G4
Vassos Hadzilacos	Department of Computer Science, University of Toronto, 6 King's College Rd., Toronto, Ontario, Canada, M5S 3G4

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 14, Citation Count: 4

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

	BGA94	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 [doi>10.1145/197917.198126]
	CHJT94	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 [doi>10.1145/197917.198121]
	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]
	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]
	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]
	HW92	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	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]
	LAA87	Michael Loui and Hosame Abu-Amara. Memory requirements for agreement among unreliable asynchronous processes. In Advances in Computer Research, volume 4, pages 163-183. JAI Press Inc., 1987.
	LG86	Barbara Liskov , John Guttag, Abstraction and specification in program development, MIT Press, Cambridge, MA, 1986
	LH96a	Wa.i-Kau Lo and Vassos Hadzilacos. All of us are smarter than any of us: more on the robustness of the Consensus hierarchy (Part I). Technical Report CSRI-348, University of Toronto, Toronto, Ontario, Canada, June 1996. Available at ftp://ftp.cs, utoronto.ca/pub/reports/csri/348.
	LH96b	Wai-Kau Lo and Vassos Hadzilacos. All of us are smarter than any of us: more on the robustness of the Consensus hierarchy (Part II). Technical Report CSRI-351, University of Toronto, Toronto, Ontario, Canada, October 1996. Available at ftp://ftp.cs.utoronto, ca/pub/reports/csri/351.
	MR96	Shlomo Moran , Lihu Rappoport, On the Robustness of h^r_m, Proceedings of the 10th International Workshop on Distributed Algorithms, p.344-361, October 09-11, 1996
	PBN94	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 [doi>10.1145/197917.198123]
	Sch96	Eric Schenk , Faith Fich, Computability and complexity results for agreement problems in shared-memory distributed systems, 1996

CITED BY 4

	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
	Prasad Jayanti, Robust wait-free hierarchies, Journal of the ACM (JACM), v.44 n.4, p.592-614, July 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