The topological structure of asynchronous computability

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The topological structure of asynchronous computability

Full text

Pdf (1.49 MB)

Source

Journal of the ACM (JACM) archive
Volume 46 , Issue 6 (November 1999) table of contents

Pages: 858 - 923

Year of Publication: 1999

ISSN:0004-5411

Authors

Maurice Herlihy	Brown Univ., Providence, RI
Nir Shavit	Tel-Aviv Univ., Tel-Aviv, Israel

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 19, Downloads (12 Months): 117, Citation Count: 30

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/331524.331529 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	AFEK, Y., AND STUPP, G. 1993. Synchronization power depends on the register size (preliminary version). In Proceedings of the 34th Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press, Los Alamitos, Calif. 195-205.
	3	James Anderson, Composite registers, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.15-29, August 22-24, 1990, Quebec City, Quebec, Canada [doi>10.1145/93385.93396]
	4	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]
	5	ATTIYA, H., LYNCH, N., AND SHAVIT, N. 1990. Are wait-free algorithms fast? In Proceedings of the 31st Annual Symposium on the Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif. 55-64.
	6	ATTIYA, n., AND RAJSBAUM, S. 1995. A combinatorial topology framework for wait-free computability. Preprint.
	7	Jennifer L. Welch , Hagit Attiya, Distributed computing: fundamentals, simulations and advanced topics, McGraw-Hill, Inc., Hightstown, NJ, 1998
	8	A. Bas-Noy , D. Dolev, Shared-memory vs. message-passing in an asynchronous distributed environment, Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, p.307-318, June 1989, Edmonton, Alberta, Canada [doi>10.1145/72981.73003]
	9	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]
	10	BOROWSKY, E. 1995. Capturing the power of resiliency and set consensus in distributed systems. Tech. rep., University of California Los Angeles, Los Angeles, Calif.
	11	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]
	12	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]
	13	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]
	14	CHAUDHURI, S., HERLIHY, M. P., LYNCH, N., AND TUTTLE, M.R. 1993. A tight lower bound for k-set agreement. In Proceedings of the 34th IEEE Symposium on Foundations of Computer Science (Oct.). IEEE Computer Society Press, Los Alamitos, Calif., pp. 206-215.
	15	Benny Chor , Amos Israeli , Ming Li, On processor coordination using asynchronous hardware, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.86-97, August 10-12, 1987, Vancouver, British Columbia, Canada [doi>10.1145/41840.41848]
	16	CHOR, B., AND MOSCOVICI, L. 1989. Solvability in asynchronous environments. In IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press, Los Alamitos, Calif., pp. 422-427.
	17	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]
	18	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]
	19	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]
	20	GAFNI, E., AND KOUTSOUPIAS, E. 1996. Three-processor tasks are undecidable, http://daphne.cs.ucla.edu/eli/undec.ps.
	21	GLASER, L. C. 1970. Geometrical Combinatorial Topology, Vol. 1. Van Nostrand Reinhold, New York.
	22	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]
	23	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 [doi>10.1145/197917.198119]
	24	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 [doi>10.1145/224964.224975]
	25	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 [doi>10.1145/258533.258652]
	26	Maurice Herlihy , Sergio Rajsbaum, A Wait-Free Classification of Loop Agreement Tasks, Proceedings of the 12th International Symposium on Distributed Computing, p.175-185, September 24-26, 1998
	27	HERLIHY, M. P., RAJSBAUM, S., AND TUTTLE, M.R. 1998. Unifying synchronous and asynchronous message-passing models. In Proceedings of the 12th International Symposium on Distributed Computing (Sept.).
	28	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]
	29	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 [doi>10.1145/195058.195144]
	30	Maurice P. Herlihy , Jeannette M. Wing, Linearizability: a correctness condition for concurrent objects, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.3, p.463-492, July 1990 [doi>10.1145/78969.78972]
	31	HOEST, G. 1997. Towards a Topological Characterization of Asynchronous Complexity. Ph.D. dissertation. Mass. Institute of Technology, Cambridge, Mass.
	32	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 [doi>10.1145/259380.259440]
	33	LEFSCHETZ, S. 1949. Introduction to Topology. Princeton University Press, Princeton, N.J.
	34	LouI, M. C., AND ABU-AMARA, H.H. 1987. Memory Requirements for Agreement Among Unreliable Asynchronous Processes, vol. 4. JAI Press, Greenwich, Conn., pp. 163-183.
	35	Nancy A. Lynch, Distributed Algorithms, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
	36	LYNCH, N. A., AND TUTTLE, M.R. 1988. An introduction to input/output automata. Tech. Rep. MIT/LCS/TM-373. HIT Laboratory for Computer Science, Cambridge, Mass.
	37	MUNKaES, J. R. 1984. Elements of Algebraic Topology. Addison-Wesley, Reading, Mass. ISBN 0-201-04586-9.
	38	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]
	39	SPANIER, E.H. 1966. Algebraic Topology. Springer-Verlag, New York.

CITED BY 30

	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
	Eli Gafni , Michael Merritt , Gadi Taubenfeld, The concurrency hierarchy, and algorithms for unbounded concurrency, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.161-169, August 2001, Newport, Rhode Island, United States
	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
	John Tromp , Paul Vitányi, Randomized two-process wait-free test-and-set, Distributed Computing, v.15 n.3, p.127-135, July 2002
	Achour Mostefaoui , Sergio Rajsbaum , Michel Raynal, Conditions on input vectors for consensus solvability in asynchronous distributed systems, Journal of the ACM (JACM), v.50 n.6, p.922-954, November 2003
	Faith Fich , Eric Ruppert, Hundreds of impossibility results for distributed computing, Distributed Computing, v.16 n.2-3, p.121-163, September 2003
	Marcos K. Aguilera, A pleasant stroll through the land of infinitely many creatures, ACM SIGACT News, v.35 n.2, June 2004
	Xingwu Liu, Evaluation of the capability of interaction, ACM SIGGROUP Bulletin, v.24 n.3, December 2003
	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
	Michel Raynal, Wait-free computing: an introductory lecture, Future Generation Computer Systems, v.21 n.5, p.655-663, May 2005
	Maurice Herlihy , Lucia Draque Penso, tight bounds for k-set agreement with limited-scope failure detectors, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.221-221, July 13-16, 2003, Boston, Massachusetts
	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
	Maurice Herlihy , Sergio Rajsbaum, Algebraic spans, Mathematical Structures in Computer Science, v.10 n.4, p.549-573, August 2000
	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
	Yehuda Afek , Eli Gafni , Adam Morrison, Common2 extended to stacks and unbounded concurrency, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA
	Michel Raynal , Gadi Taubenfeld, The notion of a timed register and its application to indulgent synchronization, Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, June 09-11, 2007, San Diego, California, USA
	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
	Sergio Rajsbaum , Michel Raynal , Corentin Travers, An impossibility about failure detectors in the iterated immediate snapshot model, Information Processing Letters, v.108 n.3, p.160-164, October, 2008
	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
	Bogdan S. Chlebus , Dariusz R. Kowalski, Asynchronous exclusive selection, 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 , Bastian Pochon, The Complexity of Early Deciding Set Agreement: How can Topology help?, Electronic Notes in Theoretical Computer Science (ENTCS), 230, p.71-78, 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
	Luigi Santocanale, Topological Properties of Event Structures, Electronic Notes in Theoretical Computer Science (ENTCS), 230, p.149-160, March, 2009
	Viorica Sofronie-Stokkermans, Sheaves and Geometric Logic and Applications to Modular Verification of Complex Systems, Electronic Notes in Theoretical Computer Science (ENTCS), 230, p.161-187, 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