Round-by-round fault detectors (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Round-by-round fault detectors (extended abstract): unifying synchrony and asynchrony

Full text

Pdf (1.19 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: 143 - 152

Year of Publication: 1998

ISBN:0-89791-977-7

Author

Eli Gafni

Computer Science Department, University of California, Los Angeles, Los Angeles, CA

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): 3, Downloads (12 Months): 32, Citation Count: 22

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.277724 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	T. E. Elrad and N. Francez. Decomposition of distributed programs into communication-closed layers. Science of Computer Programming, Vol. 2(3). 1982.
	2	Gabriel Bracha, Asynchronous byzantine agreement protocols, Information and Computation, v.75 n.2, p.130-143, November 1, 1987 [doi>10.1016/0890-5401(87)90054-X]
	3	B. A. Coan, A Compiler that Increases the Fault Tolerance of Asynchronous Protocols, IEEE Transactions on Computers, v.37 n.12, p.1541-1553, December 1988 [doi>10.1109/12.9732]
	4	Elizabeth Borowsky , Eli Gafni, A simple algorithmically reasoned characterization of wait-free computation (extended abstract), Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.189-198, August 21-24, 1997, Santa Barbara, California, United States [doi>10.1145/259380.259439]
	5	Tushar Deepak Chandra , Vassos Hadzilacos , Sam Toueg, The weakest failure detector for solving consensus, Journal of the ACM (JACM), v.43 n.4, p.685-722, July 1996 [doi>10.1145/234533.234549]
	6	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]
	7	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
	8	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]
	9	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]
	10	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]
	11	Maurice Herlihy , Nir Shavit, The asynchronous computability theorem for t-resilient tasks, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.111-120, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167125]
	12	Michael Saks , Fotios Zaharoglou, Wait-free k-set agreement is impossible: the topology of public knowledge, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.101-110, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167122]
	13	Soma Chaudhuri, Maurice Herlihy, Nancy Lynch, and Mark R. Tuttle. A tight lower bound for k-set agreement. In Proceedings of the Thirty-Fourth Symposium on Foundations of Computer Science, pages 206-215. IEEE Computer Society Press, November 1993.
	14	Michael J. Fischer and Nancy A. Lynch. A lower bound for the time to assure interactive consistency. Information Processing Letters, 14:183- 186, 1982.
	15	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]
	16	Gil Neiger , Sam Toueg, Automatically increasing the fault-tolerance of distributed algorithms, Journal of Algorithms, v.11 n.3, p.374-419, Sep. 1990 [doi>10.1016/0196-6774(90)90019-B]
	17	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 [doi>10.1145/277697.277755]
	18	Baruch Awerbuch, Complexity of network synchronization, Journal of the ACM (JACM), v.32 n.4, p.804-823, Oct. 1985 [doi>10.1145/4221.4227]
	19	Maurice Herlihy , Sergio Rajsbaum , Mark R. Tuttle, Unifying synchronous and asynchronous message-passing models, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.133-142, June 28-July 02, 1998, Puerto Vallarta, Mexico [doi>10.1145/277697.277722]
	20	Hagit Attiya , Cynthia Dwork , Nancy Lynch , Larry Stockmeyer, Bounds on the time to reach agreement in the presence of timing uncertainty, Journal of the ACM (JACM), v.41 n.1, p.122-152, Jan. 1994 [doi>10.1145/174644.174649]
	21	Ching Tsun Chou , Eli Gafni, Understanding and verifying distributed algorithms using stratified decomposition, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.44-65, August 15-17, 1988, Toronto, Ontario, Canada [doi>10.1145/62546.62556]
	22	Yehuda Afek , Hagit Attiya , Danny Dolev , Eli Gafni , Michael Merritt , Nir Shavit, Atomic snapshots of shared memory, Journal of the ACM (JACM), v.40 n.4, p.873-890, Sept. 1993 [doi>10.1145/153724.153741]
	23	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]
	24	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]

CITED BY 22

	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
	Yoram Moses , Sergio Rajsbaum, The unified structure of consensus: a layered analysis approach, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.123-132, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Maurice Herlihy , Sergio Rajsbaum , Mark R. Tuttle, Unifying synchronous and asynchronous message-passing models, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.133-142, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Partha Dutta , Rachid Guerraoui, The inherent price of indulgence, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California
	Bernadette Charron-Bost , André Schiper, Uniform consensus is harder than consensus, Journal of Algorithms, v.51 n.1, p.15-37, 1 April 2004
	Faith Fich , Eric Ruppert, Hundreds of impossibility results for distributed computing, Distributed Computing, v.16 n.2-3, p.121-163, September 2003
	Rachid Guerraoui , Michel Raynal, The Information Structure of Indulgent Consensus, IEEE Transactions on Computers, v.53 n.4, p.453-466, April 2004
	Eli Gafni , Rachid Guerraoui , Bastian Pochon, From a static impossibility to an adaptive lower bound: the complexity of early deciding set agreement, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	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
	Idit Keidar , Alexander Shraer, Timeliness, failure-detectors, and consensus performance, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA
	Partha Dutta , Rachid Guerraoui, The inherent price of indulgence, Distributed Computing, v.18 n.1, p.85-98, July 2005
	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
	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
	Marco Aurélio Spohn , J. J. Garcia-Luna-Aceves, Bounded-distance multi-clusterhead formation in wireless ad hoc networks, Ad Hoc Networks, v.5 n.4, p.504-530, May, 2007
	Bernadette Charron-Bost , André Schiper, Harmful dogmas in fault tolerant distributed computing, ACM SIGACT News, v.38 n.1, March 2007
	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
	Martin Biely , Josef Widder , Bernadette Charron-Bost , Antoine Gaillard , Martin Hutle , André Schiper, Tolerating corrupted communication, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA
	Maurice Herlihy , Sergio Rajsbaum , Mark Tuttle, An Axiomatic Approach to Computing the Connectivity of Synchronous and Asynchronous Systems, Electronic Notes in Theoretical Computer Science (ENTCS), 230, p.79-102, March, 2009
	Rachid Guerraoui , Maurice Herlihy , Bastian Pochon, A topological treatment of early-deciding set-agreement, Theoretical Computer Science, v.410 n.6-7, p.570-580, February, 2009
	Eli Gafni , Achour Mostéfaoui , Michel Raynal , Corentin Travers, From adaptive renaming to set agreement, Theoretical Computer Science, v.410 n.14, p.1328-1335, March, 2009
	Eli Gafni, The extended BG-simulation and the characterization of t-resiliency, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA
	Marcos K. Aguilera , Carole Delporte-Gallet , Hugues Fauconnier , Sam Toueg, Partial synchrony based on set timeliness, Proceedings of the 28th ACM symposium on Principles of distributed computing, August 10-12, 2009, Calgary, AB, Canada