Failure detectors and the wait-free hierarchy (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Failure detectors and the wait-free hierarchy (extended abstract)

Full text

Pdf (1.26 MB)

Source

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

Ottowa, Ontario, Canada

Pages: 100 - 109

Year of Publication: 1995

ISBN:0-89791-710-3

Author

Gil Neiger

Software Technology Lab, Intel Corporation, JF3-206, 2111 N.E. 25th Avenue, Hillsboro, Oregon

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

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

	1	Yehuda Afek , David S. Greenberg , Michael Merritt , Gadi Taubenfeld, Computing with faulty shared memory, Proceedings of the eleventh annual ACM symposium on Principles of distributed computing, p.47-58, August 10-12, 1992, Vancouver, British Columbia, Canada [doi>10.1145/135419.135431]
	2	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 [doi>10.1145/197917.197947]
	3	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]
	4	Yair Amir , Danny Dolev , Shlomo Kramer , Dalia Malki, Membership Algorithms for Multicast Communication Groups, Proceedings of the 6th International Workshop on Distributed Algorithms, p.292-312, November 02-04, 1992
	5	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 [doi>10.1007/s004460050029]
	6	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]
	7	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]
	8	Tushar Deepak Chandra , Vassos Hadzilacos , Sam Toueg, The weakest failure detector for solving consensus, Proceedings of the eleventh annual ACM symposium on Principles of distributed computing, p.147-158, August 10-12, 1992, Vancouver, British Columbia, Canada [doi>10.1145/135419.135451]
	9	Tushar Deepak Chandra , Sam Toueg, Unreliable failure detectors for asynchronous systems (preliminary version), Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.325-340, August 19-21, 1991, Montreal, Quebec, Canada [doi>10.1145/112600.112627]
	10	Benny Chor , Amos Israeli , Ming Li, Wait-Free Consensus Using Asynchronous Hardware, SIAM Journal on Computing, v.23 n.4, p.701-712, Aug. 1994 [doi>10.1137/S0097539790192635]
	11	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]
	12	D. Dolev , N. Shavit, Bounded concurrrent time-stamp systems are constructible, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.454-466, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73051]
	13	Cynthia Dwork , Orli Waarts, Simple and efficient bounded concurrent timestamping or bounded concurrent timestamp systems are comprehensible!, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.655-666, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129776]
	14	Faith Fich , Maurice Herlihy , Nir Shavit, On the space complexity of randomized synchronization, Proceedings of the twelfth annual ACM symposium on Principles of distributed computing, p.241-249, August 15-18, 1993, Ithaca, New York, United States [doi>10.1145/164051.164078]
	15	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]
	16	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]
	17	Amos Israeli , Ming Li, Bounded time-stamps, Distributed Computing, v.6 n.4, p.205-209, July 1993 [doi>10.1007/BF02242708]
	18	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]
	19	JAYANTI, P., CHANDRA, T. D., AND TOUEG, S. Faulttolerant wait-free shared objects. In Proceedings of the Thirty-Third Symposium on Foundations of Computer Science (Oct. 1992), IEEE Computer Society Press, pp. 157-166.
	20	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
	21	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]
	22	Wai-Kau Lo , Vassos Hadzilacos, Using Failure Detectors to Solve Consensus in Asynchronous Sharde-Memory Systems (Extended Abstract), Proceedings of the 8th International Workshop on Distributed Algorithms, p.280-295, September 29-October 01, 1994
	23	Loui, M. C., AND ABU-AMARA, H. H. Memory requirements for ~greement among unreliable asynchronous processors. In Advances in Computi~;ig Research, F. P. Preparata, Ed., vol. 4. JAI Press, 1987, pp. 163-183.
	24	Dalia Malki , Ken Birman , Aleta Ricciardi , André Schiper, Uniform actions in asynchronous distributed systems, Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.274-283, August 14-17, 1994, Los Angeles, California, United States [doi>10.1145/197917.198108]
	25	NEIGER, G. Wait-free algorithms and K5nig's Lemma. Unpublished manuscript, Feb. 1995.
	26	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]
	27	PETERSON, G. L., AND BURNS, J. E. Concurrent reading while writing II: The multi-writer case. In Proceedings of the Twenty-Eighth Symposium on Foundations of Computer Science (Oct. 1987), IEEE Computer Society Press, pp. 383-392.
	28	Aleta Marie Ricciardi, The group membership problem in asynchronous systems, Cornell University, Ithaca, NY, 1993
	29	Aleta M. Ricciardi , Kenneth P. Birman, Using process groups to implement failure detection in asynchronous environments, Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.341-353, August 19-21, 1991, Montreal, Quebec, Canada [doi>10.1145/112600.112628]
	30	André Schiper , Alain Sandoz, Primary Partition "Virtually-Synchronous Communication" harder than Consensus, Proceedings of the 8th International Workshop on Distributed Algorithms, p.39-52, September 29-October 01, 1994

CITED BY 9

	Jiong Yang , Gil Neiger , Eli Gafni, Structured derivations of consensus algorithms for failure detectors, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.297-306, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Eli Gafni, Round-by-round fault detectors (extended abstract): unifying synchrony and asynchrony, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.143-152, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Tushar Deepak Chandra , Sam Toueg, Unreliable failure detectors for reliable distributed systems, Journal of the ACM (JACM), v.43 n.2, p.225-267, March 1996
	Achour Mostefaoui , Sergio Rajsbaum , Michel Raynal , Corentin Travers, Irreducibility and additivity of set agreement-oriented failure detector classes, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA
	Tiejun Ma , Jane Hillston , Stuart Anderson, Evaluation of the QoS of crash-recovery failure detection, Proceedings of the 2007 ACM symposium on Applied computing, March 11-15, 2007, Seoul, Korea
	Rachid Guerraoui , Petr Kuznetsov, The gap in circumventing the impossibility of consensus, Journal of Computer and System Sciences, v.74 n.5, p.823-830, August, 2008
	Carole Delporte-Gallet , Hugues Fauconnier , Rachid Guerraoui, Sharing is harder than agreeing, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, August 18-21, 2008, Toronto, Canada
	Rachid Guerraoui , Maurice Herlihy , Petr Kouznetsov , Nancy Lynch , Calvin Newport, On the weakest failure detector ever, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA
	Alejandro Cornejo , Sergio Rajsbaum , Michel Raynal , Corentin Travers, Failure detectors are schedulers, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA