Contention in shared memory algorithms

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Contention in shared memory algorithms

Full text

Pdf (1.06 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-fifth annual ACM symposium on Theory of computing table of contents

San Diego, California, United States

Pages: 174 - 183

Year of Publication: 1993

ISBN:0-89791-591-7

Authors

Cynthia Dwork
Maurice Herlihy
Orli Waarts

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 0, Downloads (12 Months): 18, Citation Count: 22

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/167088.167145 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	Eran Aharonson , Hagit Attiya, Counting networks with arbitrary fan-out, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.104-113, September 1992, Orlando, Florida, United States
	3	T. E. Anderson, The Performance of Spin Lock Alternatives for Shared-Money Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, v.1 n.1, p.6-16, January 1990 [doi>10.1109/71.80120]
	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	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]
	7	J. Aspnes and O. Waarts. Randomized consensus in expected O(n logS n) operations per processor. In Proceedings of the 33rd IEEE Symposium on Foundations of Computer Science, pages 137-146, October 1992.
	8	K.E. Batchero Sorting networks and their applications. In Proceedings of A FIPS Joint Computer Conference, pages 338-334, 1968.
	9	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]
	10	M. Choy and A.K. Singh. Adaptive solutions to the mutual exclusion problem. Manuscript.
	11	MIPS Computer Company. The MIPS RISC architecture.
	12	Stephen Cook , Cynthia Dwork , Ru&duml;ger Reischuk, Upper and lower time bounds for parallel random access machines without simultaneous writes, SIAM Journal on Computing, v.15 n.1, p.87-97, Feb. 1986 [doi>10.1137/0215006]
	13	Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
	14	David Culler , Richard Karp , David Patterson , Abhijit Sahay , Klaus Erik Schauser , Eunice Santos , Ramesh Subramonian , Thorsten von Eicken, LogP: towards a realistic model of parallel computation, Proceedings of the fourth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.1-12, May 19-22, 1993, San Diego, California, United States
	15	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]
	16	Cynthia Dwork , Serge A. Plotkin , Maurice Herlihy , Orli Waarts, Time-lapse snapshots, Symposium proceedings on Theory of computing and systems, p.154-170, June 1992, Haifa, Israel
	17	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]
	18	C. Dwork and O. Waarts. Randomized Snapshot in Linear Time. Manuscript.
	19	Carla Schlatter Ellis , Thomas J. Olson, Algorithms for parallel memory allocation, International Journal of Parallel Programming, v.17 n.4, p.303-345, Aug. 1988 [doi>10.1007/BF01407909]
	20	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]
	21	P.B. Gibbons, Y. Matins, and V. Ramachandran. QRQW: Accounting for concurrency in PRAMs and Asynchronous PRAMs. Technical Report, AT&T Bell Laboratories, Murray Hill, NJ, March 1993.
	22	A. Gottlieb, R. Grishman, C.P. Kruskal, K.P. McAuliffe# L. Rudolph, and M. Snir. The NYU ultracomputer- designing an MIMD parallel computer. IEEE Transactzons on Computers, C-32(2):175-189, February 1984.
	23	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]
	24	Gary Granunke , Shreekant Thakkar, Synchronization Algorithms for Shared-Memory Multiprocessors, Computer, v.23 n.6, p.60-69, June 1990 [doi>10.1109/2.55501]
	25	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]
	26	Maurice Herlihy , Beng-Hong Lim , Nir Shavit, Low contention load balancing on large-scale multiprocessors, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.219-227, June 29-July 01, 1992, San Diego, California, United States [doi>10.1145/140901.140924]
	27	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]
	28	IBM. System/370 principles of operation. Order Number GA22-7000.
	29	Michael Klugerman , C. Greg Plaxton, Small-depth counting networks, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.417-428, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129752]
	30	M. Li, J. Tromp, and P.M.B. Vitanyi. How to share concurrent wait-free variables. C WI Technical Report CS-R8916, 1989.
	31	M.C. Loui and H.H. Abu-Amara. Memory Requirements for Agreement Among Unreliable Asynchronous Processes, volume 4, pages 163-183. JAI Press, 1987.
	32	J. M. Mellor-Crummey , M. L. Scott, Algorithms for Scalable Synchronization on Shared-Memory Multiproceessors, University of Rochester, Rochester, NY, 1990
	33	Robert M. Metcalfe , David R. Boggs, Ethernet: distributed packet switching for local computer networks, Communications of the ACM, v.19 n.7, p.395-404, July 1976 [doi>10.1145/360248.360253]
	34	G.H. Pfister and A. Norton. 'Hot spot' contention and combining in multistage interconnection networks. IEEE Transactzons on Computers, C-34(11):933-938, November 1985.
	35	Larry Rudolph , Zary Segall, Dynamic decentralized cache schemes for mimd parallel processors, Proceedings of the 11th annual international symposium on Computer architecture, p.340-347, January 1984
	36	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]
	37	Richard L. Sites, Alpha architecture reference manual, Digital Press, Newton, MA, 1992

CITED BY 22

	Matthew I. Frank , Anant Agarwal , Mary K. Vernon, LoPC: modeling contention in parallel algorithms, ACM SIGPLAN Notices, v.32 n.7, p.276-287, July 1997
	Nir Shavit , Asaph Zemach, Diffracting trees, ACM Transactions on Computer Systems (TOCS), v.14 n.4, p.385-428, Nov. 1996
	Leonidas Hadjimitsis , Marios Mavronicolas, Contention in balancing networks resolved (extended abstract), Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.41-50, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Manhoi Choy , Ambuj K. Singh, Adaptive solutions to the mutual exclusion problem, Distributed Computing, v.8 n.1, p.1-17, August 1994
	Sarantos Kapidakis , Marios Mavronicolas, Load balancing networks, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.275, August 20-23, 1995, Ottowa, Ontario, Canada
	Costas Busch , Marios Mavronicolas, A combinatorial treatment of balancing networks, Journal of the ACM (JACM), v.43 n.5, p.794-839, Sept. 1996
	Phillip B. Gibbons , Yossi Matias , Vijaya Ramachandran, Asynchrony versus bulk-synchrony in QRQW PRAM models, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.176, May 23-26, 1996, Philadelphia, Pennsylvania, United States
	Nir Shavit , Eli Upfal , Asaph Zemach, A wait-free sorting algorithm, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.121-128, August 21-24, 1997, Santa Barbara, California, United States
	William Aiello , Ramarathnam Venkatesan , Moti Yung, Coins, weights and contention in balancing networks, Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.193-205, August 14-17, 1994, Los Angeles, California, United States
	Roger Wattenhofer , Peter Widmayer, An inherent bottleneck in distributed counting, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.159-167, August 21-24, 1997, Santa Barbara, California, United States
	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
	Costas Busch , Nikos Hardavellas , Marios Mavronicolas, Contention in counting networks, Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.404, August 14-17, 1994, Los Angeles, California, United States
	Manhoi Choy , Ambuj K. Singh, Adaptive solutions to the mutual exclusion problem, Proceedings of the twelfth annual ACM symposium on Principles of distributed computing, p.183-194, August 15-18, 1993, Ithaca, New York, United States
	Costas Busch , Marios Mavronicolas, A logarithmic depth counting network, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.274, August 20-23, 1995, Ottowa, Ontario, Canada
	Rajeev Alur , Gadi Taubenfeld, Contention—free complexity of shared memory algorithms, Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.61-70, August 14-17, 1994, Los Angeles, California, United States
	Jae-Heon Yang , James H. Anderson, Time bounds for mutual exclusion and related problems, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.224-233, May 23-25, 1994, Montreal, Quebec, Canada
	Phillip B. Gibbons , Yossi Matias , Vijaya Ramachandran, The QRQW PRAM: accounting for contention in parallel algorithms, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.638-648, January 23-25, 1994, Arlington, Virginia, United States
	Nir Shavit , Eli Upfal , Asaph Zemach, A steady state analysis of diffracting trees (extended abstract), Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.33-41, June 24-26, 1996, Padua, Italy
	Lars Lundberg , Håkan Lennerstad, Bounding the gain of changing the number of memory modules in shared memory multiprocessors, Nordic Journal of Computing, v.4 n.3, p.233-258, Fall 1997
	Costas Busch , Marios Mavronicolas, A combinatorial treatment of balancing networks, Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.206-215, August 14-17, 1994, Los Angeles, California, United States
	Maurice Herlihy , Nir Shavit , Orli Waarts, Linearizable counting networks, Distributed Computing, v.9 n.4, p.193-203, February 1996
	Michael T. Goodrich, Parallel algorithms column 1: models of computation, ACM SIGACT News, v.24 n.4, p.16-21, Dec. 1993