A simple constructive computability theorem for wait-free computation

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A simple constructive computability theorem for wait-free computation

Full text

Pdf (849 KB)

Source

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

Montreal, Quebec, Canada

Pages: 243 - 252

Year of Publication: 1994

ISBN:0-89791-663-8

Authors

Maurice Herlihy	Digital Equipment Corporation, Cambridge Research Laboratory
Nir Shavit	Computer Science Department, Tel-Aviv University

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): 13, Citation Count: 17

Additional Information:

references cited by index terms collaborative colleagues peer to peer

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/195058.195144 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 , 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]
	2	H. Attiya, N. Lynch, and N. Shavit. Are waitfree algorithms fast? In P'roceed'zngs of the 31st Annual Symposium on the Foundations of Computer Cocience, October 1990.
	3	Hagit Attiya , Amotz Bar-Noy , Danny Dolev , David Peleg , Rüdiger Reischuk, Renaming in an asynchronous environment, Journal of the ACM (JACM), v.37 n.3, p.524-548, July 1990 [doi>10.1145/79147.79158]
	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	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]
	6	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 [doi>10.1145/164051.164056]
	7	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]
	8	Danny Dolev , Nancy A. Lynch , Shlomit S. Pinter , Eugene W. Stark , William E. Weihl, Reaching approximate agreement in the presence of faults, Journal of the ACM (JACM), v.33 n.3, p.499-516, July 1986 [doi>10.1145/5925.5931]
	9	A D Fekete, Asymptotically optimal algorithms for approximate agreement, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.73-87, August 11-13, 1986, Calgary, Alberta, Canada [doi>10.1145/10590.10597]
	10	Maurice Herlihy, Impossibility results for asynchronous PRAM (extended abstract), Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.327-336, July 21-24, 1991, Hilton Head, South Carolina, United States [doi>10.1145/113379.113409]
	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	Stephen R. Mahaney , Fred B. Schneider, Inexact agreement: accuracy, precision, and graceful degradation, Proceedings of the fourth annual ACM symposium on Principles of distributed computing, p.237-249, August 1985, Minaki, Ontario, Canada [doi>10.1145/323596.323618]
	13	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]
	14	E.H. Spanier. Algebraic Topology. Springer- Verlag, New York, 1966.

CITED BY 17

	Eli Gafni, A proof of a theorem in algebraic-topology by a distributed algorithm, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.276, May 23-26, 1996, Philadelphia, Pennsylvania, United States
	Eli Gafni , Elias Koutsoupias, 3-processor tasks are undecidable, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.271, August 20-23, 1995, Ottowa, Ontario, Canada
	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
	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
	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
	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
	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, Algebraic spans, Mathematical Structures in Computer Science, v.10 n.4, p.549-573, August 2000
	Eric Goubault, Schedulers as abstract interpretations of higher-dimensional automata, Proceedings of the 1995 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.134-145, June 21-23, 1995, La Jolla, California, United States
	Philippe Gaucher, Homotopy invariants of higher dimensional categories and concurrency in computer science, Mathematical Structures in Computer Science, v.10 n.4, p.481-524, August 2000
	John Havlicek, Computable obstructions to wait-free computability, Distributed Computing, v.13 n.2, p.59-83, April 2000
	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
	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
	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
	Maurice Herlihy , Nir Shavit, The topological structure of asynchronous computability, Journal of the ACM (JACM), v.46 n.6, p.858-923, Nov. 1999
	Eric Goubault, Geometry and concurrency: a user's guide, Mathematical Structures in Computer Science, v.10 n.4, p.411-425, 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