Disjoint-access-parallel implementations of strong shared memory primitives

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Disjoint-access-parallel implementations of strong shared memory primitives

Full text

Pdf (923 KB)

Source

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

Los Angeles, California, United States

Pages: 151 - 160

Year of Publication: 1994

ISBN:0-89791-654-9

Authors

Amos Israeli	Faculty of Electrical Engineering, Technion, Israel
Lihu Rappoport	Faculty of Computer Science, Technion, Israel

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): 4, Downloads (12 Months): 45, Citation Count: 30

Additional Information:

references cited by index terms collaborative colleagues peer to peer

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/197917.198079 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.

	AF92	Juan Alemany , Edward W. Felten, Performance issues in non-blocking synchronization on shared-memory multiprocessors, Proceedings of the eleventh annual ACM symposium on Principles of distributed computing, p.125-134, August 10-12, 1992, Vancouver, British Columbia, Canada [doi>10.1145/135419.135446]
	Alpha	DEC, Alpha system reference manual.
	AW91	Richard J. Anderson , Heather Woll, Wait-free parallel algorithms for the union-find problem, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.370-380, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103458]
	AWW93	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 [doi>10.1145/164051.164071]
	Bar93	Greg Barnes, A method for implementing lock-free shared-data structures, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.261-270, June 30-July 02, 1993, Velen, Germany [doi>10.1145/165231.165265]
	Her88	Maurice P. Herlihy, Impossibility and universality results for wait-free synchronization, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.276-290, August 15-17, 1988, Toronto, Ontario, Canada [doi>10.1145/62546.62593]
	Her91	M. P. Herlihy. A methodology for implementing highly concurrent data structures. DEC Cambridge Research Lab Technical report 91/10.
	HM92	M. P. Herlihy, J. E. B. Moss. Transactional Memory: Architectural Support for Lock- Free Data Structures. DEC Cambridge Re~ search Lab Technical report 92/7.
	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]
	IBM	IBM System 370 principles of operation. Order Number GA22-7000.
	IR93	Amos Israeli , Lihu Rappoport, Efficient Wait-Free Implementation of a Concurrent Priority Queue, Proceedings of the 7th International Workshop on Distributed Algorithms, p.1-17, September 27-29, 1993
	LS88	Vladimir Lanin , Dennis Shasha, Concurrent set manipulation without locking, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.211-220, March 1988, Austin, Texas, United States [doi>10.1145/308386.308442]
	Kan89	G. Kane. MIP$ RI$C Archztecture, Prentice Hall, New York, 1989.
	Mot84	CORPORATE MOTOROLA, MC68020 32-BIT microprocessor user's manual, Motorola Inc., Phoenix, AZ, 1991
	Pl89	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]
	PLJ91	S. Prakash, Y. Lee and T. Johnson. A Non- Blocking Algorithm for Shared Queues Using Compare-and-Swap, Proceedings 1991 International Conference on Parallel Processzng, volume 2, pages 68-75.
	ST94	N. Shavit and D. Touitou. Software Transactional Memory. Technical Report 290/94, Tel-Aviv University.
	TSP92	John Turek , Dennis Shasha , Sundeep Prakash, Locking without blocking: making lock based concurrent data structure algorithms nonblocking, Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.212-222, June 02-05, 1992, San Diego, California, United States [doi>10.1145/137097.137873]

CITED BY 30

	John D. Valois, Space bounds for transactional synchronization, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.243, May 23-26, 1996, Philadelphia, Pennsylvania, United States
	Håkan Sundell , Philippas Tsigas, Lock-free deques and doubly linked lists, Journal of Parallel and Distributed Computing, v.68 n.7, p.1008-1020, July, 2008
	Mark Moir, Laziness pays! using lazy synchronization mechanisms to improve non-blocking constructions, Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.61-70, July 16-19, 2000, Portland, Oregon, United States
	Phuong Hoai Ha , Philippas Tsigas , Mirjam Wattenhofer , Roger Wattenhofer, Efficient multi-word locking using randomization, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA
	James H. Anderson , Mark Moir, Universal constructions for multi-object operations, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.184-193, August 20-23, 1995, Ottowa, Ontario, Canada
	James H. Anderson , Srikanth Ramamurthy , Rohit Jain, Implementing wait-free objects on priority-based systems, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.229-238, August 21-24, 1997, Santa Barbara, California, United States
	Christopher Cole , Maurice Herlihy, Snapshots and software transactional memory, Science of Computer Programming, v.58 n.3, p.310-324, December 2005
	Hagit Attiya , Eshcar Hillel, The power of DCAS: highly-concurrent software transactional memory, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA
	James H. Anderson , Mark Moir, Universal Constructions for Large Objects, IEEE Transactions on Parallel and Distributed Systems, v.10 n.12, p.1317-1332, December 1999
	Maurice Herlihy , Victor Luchangco , Mark Moir , William N. Scherer, III, Software transactional memory for dynamic-sized data structures, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.92-101, July 13-16, 2003, Boston, Massachusetts
	Mark Moir, Practical implementations of non-blocking synchronization primitives, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.219-228, August 21-24, 1997, Santa Barbara, California, United States
	Maged M. Michael, High performance dynamic lock-free hash tables and list-based sets, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada
	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
	Amitabha Roy , Steven Hand , Tim Harris, A runtime system for software lock elision, Proceedings of the fourth ACM european conference on Computer systems, April 01-03, 2009, Nuremberg, Germany
	Virendra J. Marathe , William N. Scherer , Michael L. Scott, Design tradeoffs in modern software transactional memory systems, Proceedings of the 7th workshop on Workshop on languages, compilers, and run-time support for scalable systems, p.1-7, October 22-23, 2004, Houston, Texas
	Rachid Guerraoui , Maurice Herlihy , Bastian Pochon, Toward a theory of transactional contention managers, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA
	Tim Harris , Simon Marlow , Simon Peyton-Jones , Maurice Herlihy, Composable memory transactions, Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming, June 15-17, 2005, Chicago, IL, USA
	Hagit Attiya , Eyal Dagan, Universal operations: unary versus binary, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.223-232, May 23-26, 1996, Philadelphia, Pennsylvania, United States
	Maged M. Michael, Safe memory reclamation for dynamic lock-free objects using atomic reads and writes, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California
	Maurice Herlihy , Victor Luchangco , Mark Moir, A flexible framework for implementing software transactional memory, ACM SIGPLAN Notices, v.41 n.10, October 2006
	Prasad Jayanti, A lower bound on the local time complexity of universal constructions, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.183-192, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Hagit Attiya , Eyal Dagan, Improved implementations of binary universal operations, Journal of the ACM (JACM), v.48 n.5, p.1013-1037, September 2001
	Yehuda Afek , Dalia Dauber , Dan Touitou, Wait-free made fast, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.538-547, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Victor Luchangco , Mark Moir , Nir Shavit, Nonblocking k-compare-single-swap, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA
	Nir Shavit , Dan Touitou, Software transactional memory, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.204-213, August 20-23, 1995, Ottowa, Ontario, Canada
	Yehuda Afek , Michael Merritt , Gadi Taubenfeld , Dan Touitou, Disentangling multi-object operations (extended abstract), Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.111-120, August 21-24, 1997, Santa Barbara, California, United States
	Prasad Jayanti, A time complexity lower bound for randomized implementations of some shared objects, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.201-210, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Rachid Guerraoui , Michal Kapalka, On obstruction-free transactions, Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, June 14-16, 2008, Munich, Germany
	Keir Fraser , Tim Harris, Concurrent programming without locks, ACM Transactions on Computer Systems (TOCS), v.25 n.2, p.5-es, May 2007
	Maurice Herlihy , Victor Luchangco, Distributed computing and the multicore revolution, ACM SIGACT News, v.39 n.1, March 2008