Randomized wait-free concurrent objects (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Randomized wait-free concurrent objects (extended abstract)

Full text

Pdf (1.02 MB)

Source

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

Montreal, Quebec, Canada

Pages: 11 - 21

Year of Publication: 1991

ISBN:0-89791-439-2

Author

Maurice Herlihy

Digital Equipment Corporation, Cambridge Research Laboratory, 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): 12, Citation Count: 20

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/112600.112602 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	Karl Abrahamson, On achieving consensus using a shared memory, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.291-302, August 15-17, 1988, Toronto, Ontario, Canada [doi>10.1145/62546.62594]
	2	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]
	3	J.H. Anderson and M.G. Gouda. The virtue of patience: Concurrent programming with and without waiting. Private Communication.
	4	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]
	5	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]
	6	J. Aspnes , M. Herlihy, Wait-free data structures in the asynchronous PRAM model, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.340-349, July 02-06, 1990, Island of Crete, Greece [doi>10.1145/97444.97701]
	7	H. Attiya , D. Dolev , N. Shavit, Bounded polynomial randomized consensus, Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, p.281-293, June 1989, Edmonton, Alberta, Canada [doi>10.1145/72981.73001]
	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	Michael Ben-Or, Another advantage of free choice (Extended Abstract): Completely asynchronous agreement protocols, Proceedings of the second annual ACM symposium on Principles of distributed computing, p.27-30, August 17-19, 1983, Montreal, Quebec, Canada [doi>10.1145/800221.806707]
	10	James E. Burns , Gary L. Peterson, Constructing multi-reader atomic values from non-atomic values, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.222-231, August 10-12, 1987, Vancouver, British Columbia, Canada [doi>10.1145/41840.41859]
	11	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]
	12	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]
	13	Cynthia Dwork , Nancy Lynch , Larry Stockmeyer, Consensus in the presence of partial synchrony, Journal of the ACM (JACM), v.35 n.2, p.288-323, April 1988 [doi>10.1145/42282.42283]
	14	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]
	15	M. Herlihy, A methodology for implementing highly concurrent data structures, Proceedings of the second ACM SIGPLAN symposium on Principles & practice of parallel programming, p.197-206, March 14-16, 1990, Seattle, Washington, United States
	16	Maurice Herlihy, Impossibility results for asynchronous PRAM (extended abstract), Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.327-336, July 21-24, 1991, Hilton Head, South Carolina, United States [doi>10.1145/113379.113409]
	17	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]
	18	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]
	19	Clyde P Kruskal , Larry Rudolph , Marc Snir, Efficient synchronization of multiprocessors with shared memory, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.218-228, August 11-13, 1986, Calgary, Alberta, Canada [doi>10.1145/10590.10609]
	20	Leslie Lamport, Concurrent reading and writing, Communications of the ACM, v.20 n.11, p.806-811, Nov. 1977 [doi>10.1145/359863.359878]
	21	L. Lamport. On interprocess communication, parts i and it. Distributed Computing, 1'77-101, 1986.
	22	M.C. Lout and H.H. Abu-Amara. Advances in Computing Research, volume 4, chapter Memory Requirements for Agreement Among Unreliable Asynchronous Processes, pages 163-183. JAI Press, 1987.
	23	N.A. Lynch and M.R. Turtle. An introduction to input/output automata. Technical Report MIT/LCS/TM-373, MIT Laboratory for Computer Science, November 1988.
	24	Richard Newman-Wolfe, A protocol for wait-free, atomic, multi-reader shared variables, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.232-248, August 10-12, 1987, Vancouver, British Columbia, Canada [doi>10.1145/41840.41860]
	25	Gary L. Peterson, Concurrent Reading While Writing, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.1, p.46-55, Jan. 1983 [doi>10.1145/357195.357198]
	26	S. A. Plotkin, Sticky bits and universality of consensus, Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, p.159-175, June 1989, Edmonton, Alberta, Canada [doi>10.1145/72981.72992]
	27	Michael Saks , Nir Shavit , Heather Woll, Optimal time randomized consensus—making resilient algorithms fast in practice, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.351-362, January 28-30, 1991, San Francisco, California, United States
	28	Ambuj K. Singh , James H. Anderson , Mohamed G. Gouda, The elusive atomic register revisited, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.206-221, August 10-12, 1987, Vancouver, British Columbia, Canada [doi>10.1145/41840.41858]

CITED BY 20

	Prasad Jayanti , Tushar Deepak Chandra , Sam Toueg, Fault-tolerant wait-free shared objects, Journal of the ACM (JACM), v.45 n.3, p.451-500, May 1998
	Hagit Attiya , Ophir Rachman, Atomic snapshots in O(n log n) operations, Proceedings of the twelfth annual ACM symposium on Principles of distributed computing, p.29-40, August 15-18, 1993, Ithaca, New York, United States
	Yehuda Afek , Eytan Weisberger , Hanan Weisman, A completeness theorem for a class of synchronization objects, Proceedings of the twelfth annual ACM symposium on Principles of distributed computing, p.159-170, August 15-18, 1993, Ithaca, New York, United States
	James Aspnes , Orli Waarts, Modular competitiveness for distributed algorithms, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.237-246, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	Hagit Attiya , Roy Friedman, A correctness condition for high-performance multiprocessors (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.679-690, May 04-06, 1992, Victoria, British Columbia, Canada
	Faith Fich , Maurice Herlihy , Nir Shavit, On the space complexity of randomized synchronization, Journal of the ACM (JACM), v.45 n.5, p.843-862, Sept. 1998
	Z. M. Kedem , K. V. Palem , M. O. Rabin , A. Raghunathan, Efficient program transformations for resilient parallel computation via randomization (preliminary version), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.306-317, May 04-06, 1992, Victoria, British Columbia, Canada
	Panagiota Fatourou , Faith Fich , Eric Ruppert, A tight time lower bound for space-optimal implementations of multi-writer snapshots, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	James Aspnes , William Hurwood, Spreading rumors rapidly despite an adversary, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.143-151, May 23-26, 1996, Philadelphia, Pennsylvania, United States
	L. M. Kirousis , P. Spirakis , P. Tsigas, Reading Many Variables in One Atomic Operation: Solutions with Linear or Sublinear Complexity, IEEE Transactions on Parallel and Distributed Systems, v.5 n.7, p.688-696, July 1994
	Panagiota Fatourou , Faith Fich , Eric Ruppert, Space-optimal multi-writer snapshot objects are slow, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California
	John Tromp , Paul Vitányi, Randomized two-process wait-free test-and-set, Distributed Computing, v.15 n.3, p.127-135, July 2002
	Faith Fich , Maurice Herlihy , Nir Shavit, On the space complexity of randomized synchronization, Proceedings of the twelfth annual ACM symposium on Principles of distributed computing, p.241-249, August 15-18, 1993, Ithaca, New York, United States
	Cynthia Dwork , Maurice Herlihy, Bounded round number, Proceedings of the twelfth annual ACM symposium on Principles of distributed computing, p.53-64, August 15-18, 1993, Ithaca, New York, United States
	Alessandro Panconesi , Marina Papatriantafilou , Philippas Tsigas , Paul Vitányi, Randomized naming using wait-free shared variables, Distributed Computing, v.11 n.3, p.113-124, August 1998
	James Aspnes , Orli Waarts, Compositional competitiveness for distributed algorithms, Journal of Algorithms, v.54 n.2, p.127-151, February 2005
	Hagit Attiya , Maurice Herlihy , Ophir Rachman, Atomic snapshots using lattice agreement, Distributed Computing, v.8 n.3, p.121-132, March 1995
	Phuong Hoai Ha , Philippas Tsigas , Otto J. Anshus, Non-blocking programming on multi-core graphics processors: (extended asbtract), ACM SIGARCH Computer Architecture News, v.36 n.5, December 2008
	Hagit Attiya , Rachid Guerraoui , Eric Ruppert, Partial snapshot objects, Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, June 14-16, 2008, Munich, Germany
	Faith Ellen , Panagiota Fatourou , Eric Ruppert, Time lower bounds for implementations of multi-writer snapshots, Journal of the ACM (JACM), v.54 n.6, p.30-es, December 2007