A simple algorithmically reasoned characterization of wait-free computation (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A simple algorithmically reasoned characterization of wait-free computation (extended abstract)

Full text

Pdf (957 KB)

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: 189 - 198

Year of Publication: 1997

ISBN:0-89791-952-1

Authors

Elizabeth Borowsky	Computer Science Department, University of California, Los Angeles, Los Angeles, CA
Eli Gafni	Computer Science Department, University of California, Los Angeles, Los Angeles, CA

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): 2, Downloads (12 Months): 19, Citation Count: 10

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.259439 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	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]
	3	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]
	4	Soma Chaudhuri, More choices allow more faults: set consensus problems in totally asynchronous systems, Information and Computation, v.105 n.1, p.132-158, July 1993 [doi>10.1006/inco.1993.1043]
	5	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]
	6	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]
	7	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]
	8	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]
	9	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]
	10	E. Borowsky, "Capturing the Power of Resiliency and Set Consensus in Distributed Systems,'' tech. rep., University of California, Los Angeles, Oct 15, 1995.
	11	E. Gafni and E. Koutsoupias, "New characterization of resiliency and consensus,"
	12	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]
	13	Hagit Attiya , Sergio Rajsbaum, The Combinatorial Structure of Wait-free Solvable Tasks (Extended Abstract), Proceedings of the 10th International Workshop on Distributed Algorithms, p.322-343, October 09-11, 1996
	14	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 [doi>10.1145/248052.248108]
	15	C. P. Rourke and B. J. Sanderson, Introduction to Piecewise-Linear Topology. Springer Verlag, 1982.
	16	M. Herlihy and N. Shavit, "Th,~ topological structure of asynchronous computability," preprint, January 1996. stoc93, stoc94 of authors, long-awaited-new-improved.

CITED BY 10

	Maurice Herlihy, On beyond registers: wait-free readable objects, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.26-42, August 2001, Newport, Rhode Island, 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
	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
	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
	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
	Alejandro Cornejo , Sergio Rajsbaum , Michel Raynal , Corentin Travers, Failure detectors are schedulers, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA
	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