Structured derivations of consensus algorithms for failure detectors

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Structured derivations of consensus algorithms for failure detectors

Full text

Pdf (1.35 MB)

Source

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

Puerto Vallarta, Mexico

Pages: 297 - 306

Year of Publication: 1998

ISBN:0-89791-977-7

Authors

Jiong Yang	Department of Computer Science, University of California at Los Angeles
Gil Neiger	MicroComputer Research Labs, Intel Corporation, Hillsboro, Oregon
Eli Gafni	Department of Computer Science, University of California at Los Angeles

Sponsors

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

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 16, Citation Count: 16

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/277697.277755 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	Hagit Attiya, Efficient and Robust Sharing of Memory in Message-Passing Systems (Extended Abstract), Proceedings of the 10th International Workshop on Distributed Algorithms, p.56-70, October 09-11, 1996
	2	Hagit Attiya , Amotz Bar-Noy , Danny Dolev, Sharing memory robustly in message-passing systems, Journal of the ACM (JACM), v.42 n.1, p.124-142, Jan. 1995 [doi>10.1145/200836.200869]
	3	Rida A. Bazzi , Gil Neiger, Simulating Crash Failures with Many Faulty Processors (Extended Abstract), Proceedings of the 6th International Workshop on Distributed Algorithms, p.166-184, November 02-04, 1992
	4	Elizabeth Borowsky , Eli Gafni, Generalized FLP impossibility result for t-resilient asynchronous computations, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.91-100, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167119]
	5	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 [doi>10.1145/226643.226647]
	6	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]
	7	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]
	8	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]
	9	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]
	10	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 [doi>10.1145/277697.277724]
	11	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
	12	LOUI, M. C., AND ABU-AMARA, H. H. Memory requirements for agreement among unreliable asynchronous processors. In Advances in Computing Research, F. P. Preparata, Ed., vol. 4. JAI Press, 1987, pp. 163-183.
	13	Nancy Lynch , Sergio Rajsbaum, On the Borowsky-Gafni simulation algorithm, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.57, May 23-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/248052.248060]
	14	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 [doi>10.1145/224964.224976]

CITED BY 16

	Fabíola Greve , Michel Hurfin , Raimundo Macêdo , Michel Raynal, Time and message-efficient S-based consensus (brief announcement), Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.332, July 16-19, 2000, Portland, Oregon, United States
	Achour Mostéfaoui , Michel Raynal, k-set agreement with limited accuracy failure detectors, Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.143-152, July 16-19, 2000, Portland, Oregon, United States
	Achour Mostefaoui , Michel Raynal, Randomized k-set agreement, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.291-297, July 2001, Crete Island, Greece
	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
	Romain Boichat , Partha Dutta , Svend Frølund , Rachid Guerraoui, Deconstructing paxos, ACM SIGACT News, v.34 n.1, March 2003
	Achour Mostefaoui , Sergio Rajsbaum , Michel Raynal, The combined power of conditions and failure detectors to solve asynchronous set agreement, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA
	On the Implementation of Unreliable Failure Detectors in Partially Synchronous Systems, IEEE Transactions on Computers, v.53 n.7, p.815-828, July 2004
	E. Anceaume , A. Fernández , A. Mostefaoui , G. Neiger , M. Raynal, A necessary and sufficient condition for transforming limited accuracy failure detectors, Journal of Computer and System Sciences, v.68 n.1, p.123-133, February 2004
	Marcos K. Aguilera , Carole Delporte-Gallet , Hugues Fauconnier , Sam Toueg, Communication-efficient leader election and consensus with limited link synchrony, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada
	M. Hurfin , A. Mostéfaoui , M. Raynal, A Versatile Family of Consensus Protocols Based on Chandra-Toueg's Unreliable Failure Detectors, IEEE Transactions on Computers, v.51 n.4, p.395-408, April 2002
	Maurice Herlihy , Lucia Draque Penso, Tight bounds for k-set agreement with limited-scope failure detectors, Distributed Computing, v.18 n.2, p.157-166, December 2005
	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
	Taisuke Izumi , Akinori Saitoh , Toshimitsu Masuzawa, Adaptive timeliness of consensus in presence of crash and timing faults, Journal of Parallel and Distributed Computing, v.67 n.6, p.648-658, June, 2007
	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
	Yehuda Afek , Israel Nir, Failure detectors in loosely named systems, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, August 18-21, 2008, Toronto, Canada
	Hagit Attiya , Rachid Guerraoui , Danny Hendler , Petr Kuznetsov, The complexity of obstruction-free implementations, Journal of the ACM (JACM), v.56 n.4, p.1-33, June 2009