Disentangling multi-object operations (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Disentangling multi-object operations (extended abstract)

Full text

Pdf (1.11 MB)

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: 111 - 120

Year of Publication: 1997

ISBN:0-89791-952-1

Authors

Yehuda Afek	Computer Science Dept., Tel-Aviv Univ., Israel 69978 and AT&T Labs
Michael Merritt	AT&T Labs, 180 Park Av., Florham park, NJ
Gadi Taubenfeld	The Open Univ., 16 Kiausner st., P.O.B. 39328, Tel-Aviv 61392, Israel and AT&T Labs
Dan Touitou	nSOF Parallel Software, 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): 0, Downloads (12 Months): 9, 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/259380.259431 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.

	AD96	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 [doi>10.1145/248052.248097]
	ADT95	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 [doi>10.1145/225058.225271]
	AM94	James H. Anderson , Mark Moir, Using k-exclusion to implement resilient, scalable shared objects (extended abstract), Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.141-150, August 14-17, 1994, Los Angeles, California, United States [doi>10.1145/197917.198073]
	AM95a	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 [doi>10.1145/224964.224985]
	AM95b	James H. Anderson , Mark Moir, Universal Constructions for Large Objects, Proceedings of the 9th International Workshop on Distributed Algorithms, p.168-182, September 13-15, 1995
	AMT96	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 [doi>10.1145/248052.248096]
	AS90	B. Awerbuch and M. Saks. A dining philosophers algorithm with polynomial response time. In Proc. $1th IEEE Syrup. on Foundations of Compute,' Science, pages 65-74, October 1990.
	AT93	R. Alur and G. Taubenfeld. How to share an object' A fast timing-based solution. In Proceedings of the 5th IEEE Symposium on Parallel and Distributed Processing, pages 470-477, December 1993.
	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]
	CM84	K. M. Chandy , J. Misra, The drinking philosophers problem, ACM Transactions on Programming Languages and Systems (TOPLAS), v.6 n.4, p.632-646, Oct. 1984 [doi>10.1145/1780.1804]
	CS95	Manhoi Choy , Ambuj K. Singh, Efficient fault-tolerant algorithms for distributed resource allocation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.17 n.3, p.535-559, May 1995 [doi>10.1145/203095.203101]
	CS96	Manhoi Choy , Ambuj K. Singh, Localizing Failures in Distributed Synchronization, IEEE Transactions on Parallel and Distributed Systems, v.7 n.7, p.705-716, July 1996 [doi>10.1109/71.508250]
	CV86	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]
	Dij72	E. W. Dijkstra. Hierarchical ordering of sequential processes. In Operating Systems Techniques, 1972. Eds: C. A. R. Hoare and R. H. Perrott, Eds. Academic Press.
	DHW93	Cynthia Dwork , Maurice Herlihy , Orli Waarts, Contention in shared memory algorithms, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.174-183, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167145]
	GC96	Michael Greenwald , David Cheriton, The synergy between non-blocking synchronization and operating system structure, Proceedings of the second USENIX symposium on Operating systems design and implementation, p.123-136, October 29-November 01, 1996, Seattle, Washington, United States
	GPS87	A. Goldberg , S. Plotkin , G. Shannon, Parallel symmetry-breaking in sparse graphs, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.315-324, January 1987, New York, New York, United States [doi>10.1145/28395.28429]
	Her91	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]
	Her93	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]
	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
	IR94	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]
	JT92	Prasad Jayanti , Sam Toueg, Some Results on the Impossibility, Universality, and Decidability of Consensus, Proceedings of the 6th International Workshop on Distributed Algorithms, p.69-84, November 02-04, 1992
	Lyn81	N. A. Lynch. Upper bounds for static resource allocation in a distributed systems. Journal of Computer and System Sciences, 23:254-278, 1981.
	MT94	Michael Merritt , Gadi Taubenfeld, Atomic m-Register Operations (Extended Abstract), Proceedings of the 5th International Workshop on Distributed Algorithms, p.289-294, October 07-09, 1991
	Plo88	S. A. Plotkin. Chapter ~4: Sticker Bits and Universality of Consensus. PhD thesis, M.I.T., August 1988.
	Plo89	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]
	SP88	Eugene Styer , Gary L. Peterson, Improved algorithms for distributed resource allocation, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.105-116, August 15-17, 1988, Toronto, Ontario, Canada [doi>10.1145/62546.62567]
	ST95	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]
	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 11

	Hagit Attiya , Eyal Dagan, Improved implementations of binary universal operations, Journal of the ACM (JACM), v.48 n.5, p.1013-1037, September 2001
	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
	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
	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
	Eric Ruppert, Consensus numbers of multi-objects, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.211-217, June 28-July 02, 1998, Puerto Vallarta, Mexico
	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
	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
	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
	Hagit Attiya, Concurrency and the Principle of Data Locality, IEEE Distributed Systems Online, v.8 n.9, p.3, September 2007
	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
	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