Algebraic spans

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Algebraic spans

Full text

Pdf (1.04 MB)

Source

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

Ottowa, Ontario, Canada

Pages: 90 - 99

Year of Publication: 1995

ISBN:0-89791-710-3

Authors

Maurice Herlihy	Computer Science Department, Brown University, Providence, RI
Sergio Rajsbaum	Digital Equipment Corporation, Cambridge Research Lab, One Kendall Square, Cambridge, MA

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): 1, Downloads (12 Months): 17, Citation Count: 11

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/224964.224975 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 , 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]
	2	H. Attiya and S. Rajsbaum. A combinatorial topology framework for wait-free computability. Preprint.
	3	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]
	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	E. Borowsky and E. Gafni. The implication of the Borowsky-Gafni simulation on the set consensus hierarchy. Technical Report 930021, UCLA Computer Science Dept., 1993.
	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	S. Chaudhuri, M.P. Herlihy, N. Lynch, and M..R. Tuttle. A tight lower bound for k-set agreement. In Proceedings of the 3Jth IEEE Symposium on Foundations of Computer Science, October 1993.
	9	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]
	10	M. Herlihy , Mark R. Tuttle, Lower bounds for wait-free computation in message-passing systems, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.347-362, August 22-24, 1990, Quebec City, Quebec, Canada [doi>10.1145/93385.93439]
	11	M.P. Herlihy. A tutorial on algebraic topology and distributed computation. http: //www. cs. brown, edu/people/mph/horae, htmZ
	12	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]
	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	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]
	15	J.R. Munkres. Elements Of Algebraic Topology. Addison Wesley, Reading MA, 1984. ISBN 0- 201-04586-9.
	16	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]

CITED BY 11

	Maurice Herlihy , Nir Shavit, The topological structure of asynchronous computability, Journal of the ACM (JACM), v.46 n.6, p.858-923, Nov. 1999
	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
	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
	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
	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
	Eric Goubault, Geometry and concurrency: a user's guide, Mathematical Structures in Computer Science, v.10 n.4, p.411-425, August 2000
	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