Towards a topological characterization of asynchronous complexity

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Towards a topological characterization of asynchronous complexity

Full text

Pdf (1.14 MB)

Source

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

Santa Barbara, California, United States

Pages: 199 - 208

Year of Publication: 1997

ISBN:0-89791-952-1

Authors

Gunnar Hoest	M.I.T.
Nir Shavit	Tel-Aviv University and M.I.T.

Sponsors

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

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 12, Citation Count: 8

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/259380.259440 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	James H. Anderson, Composite registers, Distributed Computing, v.6 n.3, p.141-154, April 1993 [doi>10.1007/BF02242703]
	2	Mark Moir , James H. Anderson, Wait-free algorithms for fast, long-lived renaming, Science of Computer Programming, v.25 n.1, p.1-39, Oct. 1995 [doi>10.1016/0167-6423(95)00009-H]
	3	J. ABpnes, M. P. HerUhy, Wait-Free Data Structures in the Asynchronous PRAM Model. Proceedings of the $rd Annual A CM 5~nposium on PrincipleJ of Distributed Computing, pages 377-408, July 1991. Also appeared as technical report.
	4	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]
	5	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]
	6	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]
	7	Hagit Attiya , Nancy Lynch , Nir Shavit, Are wait-free algorithms fast?, Journal of the ACM (JACM), v.41 n.4, p.725-763, July 1994 [doi>10.1145/179812.179902]
	8	H. Attiya and S. Rajsbaum. A combinatorial topology framework for wait-free computability. Preprint, 1995.
	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	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]
	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, 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]
	13	91. Borowsky and B. Gafni. The set consensus hierarchy. Unpublished manuscript, November 1993.
	14	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]
	15	S. Chaudhuri, M.P. Herlihy, N. Lynch, and M. Tuttis. Tight Bounds for k-Set Agreement. In Proceedings of the S$rd A CM Symposium on Foundations of Computer Science, October 1993.
	16	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]
	17	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]
	18	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 [doi>10.1145/224964.225009]
	19	R. Gawlick, CONCURRENT TIMESTAMPING MADE SIMPLE, Massachusetts Institute of Technology, Cambridge, MA, 1992
	20	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]
	21	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]
	22	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]
	23	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]
	24	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]
	25	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]
	26	Maurice Herlihy , Nir Shavit, The Topological Structure of Asynchronous Computability, Brown University, Providence, RI, 1996
	27	L. Lamport, On interprocess communication, Part II: Algorithms. Distributed Computing (lilt, pages 86-101, April 1986.
	28	Nancy A. Lynch, Distributed Algorithms, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
	29	N.A. Lynch And M.R. TUttis. An Introduction To Input/Output Automata. MIT/LCS/TM-3?3, MIT Labor~ tory For Computer Science, Nov 1988.
	30	Nancy Lynch and Sergio Rajsbaum. On the Borowsky-GeaCni simulation algorithm. In Proceedings of the Fourth ISTC5 Israel $~nposium on Tkeor~ ot Computing a~d $1tstems, pages 4-15, jerusalem, Israel, June 1996. I91EE Computer Society.
	31	J.R. Munkres. Elements of Algebraic TopoioF~. Addison- Wesley, Cambridge, 1996.
	32	Gil Neiger, Set-linearizability, Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.396, August 14-17, 1994, Los Angeles, California, United States [doi>10.1145/197917.198176]
	33	Paul M. B. Vitlnyi and Baruch Awerbuch, Atomic Shared Register Access by Asynchronous Hardware. t7th Annual IEEE $1/mposium on Foundation, oJ Computer Science, pages 233-243, Toronto, Ontario, Canada October 1986.
	34	Eric Schenk , Faith Fich, Computability and complexity results for agreement problems in shared-memory distributed systems, 1996
	35	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]
	36	E.H. Spanier. Algebraic Topoioglt. Springer-Verlag, New York, 1966.

CITED BY 8

	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 , 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
	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
	Faith Fich , Eric Ruppert, Hundreds of impossibility results for distributed computing, Distributed Computing, v.16 n.2-3, p.121-163, September 2003
	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
	Stefan Sokołowski, Investigation of concurrent processes by means of homotopy functors, Mathematical Structures in Computer Science, v.12 n.5, p.665-699, October 2002
	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