Generalized FLP impossibility result for t-resilient asynchronous computations

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Generalized FLP impossibility result for t-resilient asynchronous computations

Full text

Pdf (981 KB)

Source

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

San Diego, California, United States

Pages: 91 - 100

Year of Publication: 1993

ISBN:0-89791-591-7

Authors

Elizabeth Borowsky
Eli Gafni

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 10, Downloads (12 Months): 55, Citation Count: 57

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/167088.167119 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 , Danny Dolev , Hagit Attiya , Eli Gafni , Michael Merritt , Nir Shavit, Atomic snapshots of shared memory, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.1-13, August 22-24, 1990, Quebec City, Quebec, Canada [doi>10.1145/93385.93394]
	2	Hagit Attiya , Amotz Bar-Noy , Danny Dolev, Sharing memory robustly in message-passing systems, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.363-375, August 22-24, 1990, Quebec City, Quebec, Canada [doi>10.1145/93385.93441]
	3	H. Attiya, A. Bar-Noy, D. Dolev, D. Koller, D. Peleg, and R. Reischuk, "Achievable Cases in an Asynchronous Environment", Proc. 28th IEEE Symp. on Foundations of Computer Science, pages 337-346, 1987.
	4	Ofer Biran , Shlomo Moran , Shmuel Zaks, A combinatorial characterization of the distributed tasks which are solvable in the presence of one faulty processor, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.263-275, August 15-17, 1988, Toronto, Ontario, Canada [doi>10.1145/62546.62590]
	5	Soma Chaudhuri, Agreement is harder than consensus: set consensus problems in totally asynchronous systems, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.311-324, August 22-24, 1990, Quebec City, Quebec, Canada [doi>10.1145/93385.93431]
	6	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]
	7	Greg N. Frederickson , Nancy A. Lynch, Electing a leader in a synchronous ring, Journal of the ACM (JACM), v.34 n.1, p.98-115, Jan. 1987 [doi>10.1145/7531.7919]
	8	Maurice P. Herlihy, Impossibility and universality results for wait-free synchronization, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.276-290, August 15-17, 1988, Toronto, Ontario, Canada [doi>10.1145/62546.62593]
	9	L. Lamport, "On Interprocess Communica.- tion, Parts I and II", Distributed Computing, Vol. 1, pages 77-101, 1986.
	10	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]
	11	Yehuda Afek , Danny Dolev , Eli Gafni , Michael Merritt , Nir Shavit, A bound first-in, first-enabled solution to the 1-exclusion problem, Proceedings of the 4th international workshop on Distributed algorithms, p.422-432, June 1991, Bari, Italy
	12	F. Zaha.roglou and M. Saks," Wait-Free kset Agreement is impossible: The Topology of Public Knowledge", This Proceedings.
	13	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]
	14	P. Jayanti and S. Toueg, "Some Results on the Impossibility, Universality and Decidability of Consensus", private communication.

CITED BY 57

	Soma Chaudhuri , Maurice Erlihy , Nancy A. Lynch , Mark R. Tuttle, Tight bounds for k-set agreement, Journal of the ACM (JACM), v.47 n.5, p.912-943, Sept. 2000
	Maurice Herlihy , Sergio Rajsbaum, The decidability of distributed decision tasks (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.589-598, May 04-06, 1997, El Paso, Texas, United States
	Elizabeth Borowsky , Eli Gafni, Immediate atomic snapshots and fast renaming, Proceedings of the twelfth annual ACM symposium on Principles of distributed computing, p.41-51, August 15-18, 1993, Ithaca, New York, United States
	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
	Wai-Kau Lo , Vassos Hadziolacos, On the power of shared object types to implement one-resilient Consensus, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.101-110, August 21-24, 1997, Santa Barbara, California, United States
	Maurice Herlihy , Sergio Rajsbaum, Algebraic spans, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.90-99, August 20-23, 1995, Ottowa, Ontario, Canada
	Maurice Herlihy , Sergio Rajsbaum, Set consensus using arbitrary objects (preliminary version), Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.324-333, August 14-17, 1994, Los Angeles, California, United States
	Benny Chor , Lee-Bath Nelson, Resilience of general interactive tasks, Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.173-182, August 14-17, 1994, Los Angeles, California, United States
	Gunnar Hoest , Nir Shavit, Towards a topological characterization of asynchronous complexity, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.199-208, August 21-24, 1997, Santa Barbara, California, 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
	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
	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
	Hagit Attiya, A direct lower bound for k-set consensus, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.314, June 28-July 02, 1998, Puerto Vallarta, Mexico
	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
	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
	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
	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
	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
	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
	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
	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
	Yehuda Afek , Hagit Attiya , Arie Fouren , Gideon Stupp , Dan Touitou, Long-lived renaming made adaptive, Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing, p.91-103, May 04-06, 1999, Atlanta, Georgia, United States
	Maurice Herlihy , Nir Shavit, The topological structure of asynchronous computability, Journal of the ACM (JACM), v.46 n.6, p.858-923, Nov. 1999
	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
	Marios Mavronicolas, Wait-free solvability via combinatorial topology, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.277, May 23-26, 1996, Philadelphia, Pennsylvania, United States
	Dimitris Michailidis, Fast set agreement in the presence of timing uncertainty, Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing, p.249-256, May 04-06, 1999, Atlanta, Georgia, United States
	Roberto De Prisco , Dahlia Malkhi , Michael K. Reiter, On k-set consensus problems in asynchronous systems, Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing, p.257-265, May 04-06, 1999, Atlanta, Georgia, United States
	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
	Hagit Attiya , Arie Fouren, Algorithms adapting to point contention, Journal of the ACM (JACM), v.50 n.4, p.444-468, July 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
	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
	Wai-Kau Lo , Vassos Hadzilacos, On the power of shared object types to implement one-resilient Consensus, Distributed Computing, v.13 n.4, p.219-238, November 2000
	Faith Fich , Eric Ruppert, Hundreds of impossibility results for distributed computing, Distributed Computing, v.16 n.2-3, p.121-163, September 2003
	Hagit Attiya , Arie Fouren , Eli Gafni, An adaptive collect algorithm with applications, Distributed Computing, v.15 n.2, p.87-96, April 2002
	John Havlicek, Computable obstructions to wait-free computability, Distributed Computing, v.13 n.2, p.59-83, April 2000
	Roberto de Prisco , Dahlia Malkhi , Michael Reiter, On k-Set Consensus Problems in Asynchronous Systems, IEEE Transactions on Parallel and Distributed Systems, v.12 n.1, p.7-21, January 2001
	Ronit Lubitch , Shlomo Moran, Closed schedulers: a novel technique for analyzing asynchronous protocols, Distributed Computing, v.8 n.4, p.203-210, June 1995
	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 , 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
	Eric Goubault, Geometry and concurrency: a user's guide, Mathematical Structures in Computer Science, v.10 n.4, p.411-425, August 2000
	Maurice Herlihy , Sergio Rajsbaum, Algebraic spans, Mathematical Structures in Computer Science, v.10 n.4, p.549-573, August 2000
	Lisbeth Fajstrup , Martin Raußen , Eric Goubault, Algebraic topology and concurrency, Theoretical Computer Science, v.357 n.1, p.241-278, 25 July 2006
	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
	Phuong Hoai Ha , Philippas Tsigas , Otto J. Anshus, Non-blocking programming on multi-core graphics processors: (extended asbtract), ACM SIGARCH Computer Architecture News, v.36 n.5, December 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
	Armando Castañeda , Sergio Rajsbaum, New combinatorial topology upper and lower bounds for renaming, 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
	Piotr Zielinski, Anti-Ω: the weakest failure detector for set agreement, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, August 18-21, 2008, Toronto, Canada
	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
	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
	Xingwu Liu , Zhiwei Xu , Jianzhong Pan, Classifying rendezvous tasks of arbitrary dimension, Theoretical Computer Science, v.410 n.21-23, p.2162-2173, May, 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
	Carole Delporte-Gallet , Hugues Fauconnier , Rachid Guerraoui , Andreas Tielmann, The disagreement power of an adversary: extended abstract, Proceedings of the 28th ACM symposium on Principles of distributed computing, August 10-12, 2009, Calgary, AB, Canada
	Antonio Fernandez Anta , Sergio Rajsbaum , Corentin Travers, Brief announcement: weakest failure detectors via an egg-laying simulation, Proceedings of the 28th ACM symposium on Principles of distributed computing, August 10-12, 2009, Calgary, AB, Canada
	Eli Gafni , Petr Kuznetsov, The weakest failure detector for solving k-set agreement, Proceedings of the 28th ACM symposium on Principles of distributed computing, August 10-12, 2009, Calgary, AB, Canada