A completeness theorem for a class of synchronization objects

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A completeness theorem for a class of synchronization objects

Full text

Pdf (1.27 MB)

Source

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

Ithaca, New York, United States

Pages: 159 - 170

Year of Publication: 1993

ISBN:0-89791-613-1

Authors

Yehuda Afek
Eytan Weisberger
Hanan Weisman

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): 15, 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/164051.164071 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.

	AAD+90	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]
	ADS89	Hagit Attiya, Danny Dolev, and Nir Shavit. Bounded polynomiM randomized consensus. Extended Abstract, January 1989.
	AGM+92	Yehuda Afek , David S. Greenberg , Michael Merritt , Gadi Taubenfeld, Computing with faulty shared memory, Proceedings of the eleventh annual ACM symposium on Principles of distributed computing, p.47-58, August 10-12, 1992, Vancouver, British Columbia, Canada [doi>10.1145/135419.135431]
	AGTV92	Yehuda Afek , Eli Gafni , John Tromp , Paul M. B. Vitányi, Wait-free Test-and-Set (Extended Abstract), Proceedings of the 6th International Workshop on Distributed Algorithms, p.85-94, November 02-04, 1992
	AH90	James Aspnes , M. Herlihy, Fast randomized consensus using shared memory, Journal of Algorithms, v.11 n.3, p.441-461, Sep. 1990 [doi>10.1016/0196-6774(90)90021-6]
	AHS91	James Aspnes , Maurice Herlihy , Nir Shavit, Counting networks and multi-processor coordination, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.348-358, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103421]
	Asp90	James Aspnes, Time-and space-efficient randomized consensus, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.325-331, August 22-24, 1990, Quebec City, Quebec, Canada [doi>10.1145/93385.93433]
	Ber91	B. N. Bershad. Practical considerations for lock-free concurrent objects. Technical Report CMU-CS-91-183, Carnegie Mellon University, September 1991.
	DS89	D. Dolev , N. Shavit, Bounded concurrrent time-stamp systems are constructible, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.454-466, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73051]
	GLR83	Allan Gottlieb , Boris D. Lubachevsky , Larry Rudolph, Basic Techniques for the Efficient Coordination of Very Large Numbers of Cooperating Sequential Processors, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.2, p.164-189, April 1983 [doi>10.1145/69624.357206]
	Her91a	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]
	Her91b	Maurice Herlihy, Randomized wait-free concurrent objects (extended abstract), Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.11-21, August 19-21, 1991, Montreal, Quebec, Canada [doi>10.1145/112600.112602]
	HSW91	Maurice Herlihy , Nir Shavit , Orli Waarts, Low contention linearizable counting, Proceedings of the 32nd annual symposium on Foundations of computer science, p.526-537, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185415]
	HW90	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]
	JCT92	P. Jayanti, T. Chandra, , and S. Toueg. Fault-tolerant wait-free shared objects. In Proc. of the 33rd IEEE Annual Syrup. on Foundation of Computer Science, October 1992.
	PF77	Gary L. Peterson , Michael J. Fischer, Economical solutions for the critical section problem in a distributed system (Extended Abstract), Proceedings of the ninth annual ACM symposium on Theory of computing, p.91-97, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803398]
	Plo88	S. A. Plotkin. Chapter 4: Sticky Bits and Universality of Consensus. PhD thesis, M.I.T., August 1988.
	PS85	James L. Peterson , Abraham Silberschatz, Operating system concepts (2nd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1985
	SSW90	M. Saks, N. Shavit, and H. Woll. Optimal time randomized consensus - making resilient algoritluns fast in practice. In Proc. of SODA 90, December 1990.

CITED BY 11

	Amos Israeli , Lihu Rappoport, Disjoint-access-parallel implementations of strong shared memory primitives, Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.151-160, August 14-17, 1994, Los Angeles, California, United States
	Gil Neiger, Failure detectors and the wait-free hierarchy (extended abstract), Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.100-109, August 20-23, 1995, Ottowa, Ontario, Canada
	Yehuda Afek , David S. Greenberg , Michael Merritt , Gadi Taubenfeld, Computing with faulty shared objects, Journal of the ACM (JACM), v.42 n.6, p.1231-1274, Nov. 1995
	Tushar Deepak Chandra , Prasad Jayanti , King Tan, A polylog time wait-free construction for closed objects, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.287-296, June 28-July 02, 1998, Puerto Vallarta, Mexico
	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
	Yehuda Afek , Michael Merritt , Gadi Taubenfeld, The power of multi-objects (extended abstract), Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.213-222, May 23-26, 1996, Philadelphia, Pennsylvania, United States
	Rida A. Bazzi , Gil Neiger , Gary L. Peterson, On the use of registers in achieving wait-free consensus, Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.354-362, August 14-17, 1994, Los Angeles, California, United States
	Matei David, Brief announcement: a single enqueuer wait-free queue implementation, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada
	Rida A. Bazzi , Gil Neiger , Gary L. Peterson, On the use of registers in achieving wait-free consensus, Distributed Computing, v.10 n.3, p.117-127, April 1997
	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
	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