Universal operations

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Universal operations: unary versus binary

Full text

Pdf (1.08 MB)

Source

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

Philadelphia, Pennsylvania, United States

Pages: 223 - 232

Year of Publication: 1996

ISBN:0-89791-800-2

Authors

Hagit Attiya	Department of Computer Science, The Technion, Haifa 32000, Israel
Eyal Dagan	Department of Computer Science, The Technion, Haifa 32000, Israel

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGOPS: ACM Special Interest Group on Operating Systems

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 0, Downloads (12 Months): 10, 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/248052.248097 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	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]
	2	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]
	3	R. J. Anderson, Primitives for asynchronous list compression, Mathematical Systems Theory, v.27 n.5, p.453-470, Sept./Oct. 1994
	4	Hagit Attiya , Nancy Lynch , Nir Shavit, Are wait-free algorithms fast?, Journal of the ACM (JACM), v.41 n.4, p.725-763, July 1994 [doi>10.1145/179812.179902]
	5	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]
	6	Richard Cole , Uzi Vishkin, Deterministic coin tossing with applications to optimal parallel list ranking, Information and Control, v.70 n.1, p.32-53, July 1986 [doi>10.1016/S0019-9958(86)80023-7]
	7	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]
	8	Maurice Herlihy, A methodology for implementing highly concurrent data objects, ACM Transactions on Programming Languages and Systems (TOPLAS), v.15 n.5, p.745-770, Nov. 1993 [doi>10.1145/161468.161469]
	9	M.P. Herlihy and J.E.B. Moss. Transactional Memory: Arcbiteclural Support for Lock-Free Data Structures, Digital Equipment Corporation Cambridge Research Lab Technical Report 92/7.
	10	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]
	11	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
	12	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 [doi>10.1145/197917.198079]
	13	IBM Corporation, The PowerPC Architecture: A Specification for a New Family of RI$C Processors, Morgan-Kaufman. t994.
	14	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]
	15	N. Linial, "Distributive Graph Algorithms.- Global Solutions from Local Data," FOCS 1987, 1987, pp. 331-335.
	16	H. Massalin and C. Pu, A Lock-Free Mulizprocessot OS Kernel, University of Columbia, Technical Report CUCS-005-91, 1991.
	17	S. Prakash, Y. Lee and T. Johnson. "A Non- Blocking Algorithm for Shared Queues Using Compare-and-Swap." Proceedings 1991 Iniernatzonal Conference on Parallel Processing, volume 2, pages 68-75.
	18	G.H. Pfister and A. Norton. "'Hot spot' contention and combining in multistage interconnection networks," IEEE Transactions on Computers, C-34(11):933-938, November 1985.
	19	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 [doi>10.1145/224964.224987]
	20	Richard L. Sites, Alpha architecture reference manual, Digital Press, Newton, MA, 1992
	21	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 10

	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
	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
	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
	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
	Hagit Attiya , Eyal Dagan, Improved implementations of binary universal operations, Journal of the ACM (JACM), v.48 n.5, p.1013-1037, September 2001
	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
	Ole Agesen , David L. Detlefs , Christine H. Flood , Alexander T. Garthwaite , Paul A. Martin , Nir N. Shavit , Guy L. Steele, Jr., DCAS-based concurrent deques, Proceedings of the twelfth annual ACM symposium on Parallel algorithms and architectures, p.137-146, July 09-13, 2000, Bar Harbor, Maine, United States
	Marcos K. Aguilera , Burkhard Englert , Eli Gafni, On using network attached disks as shared memory, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.315-324, July 13-16, 2003, Boston, Massachusetts
	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
	Burkhard Englert, On the cost of uniform protocols whose memory consumption is adaptive to interval contention, Theoretical Computer Science, v.410 n.6-7, p.533-545, February, 2009