Counting networks and multi-processor coordination

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Counting networks and multi-processor coordination

Full text

Pdf (854 KB)

Source

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

New Orleans, Louisiana, United States

Pages: 348 - 358

Year of Publication: 1991

ISBN:0-89791-397-3

Authors

James Aspnes	Carnegie Mellon University
Maurice Herlihy	Digital Equipment Corporation, Cambridge Research Lab
Nir Shavit	MIT Lab. for Computer Science

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 21, Citation Count: 32

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/103418.103421 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	A. Agarwal , M. Cherian, Adaptive backoff synchronization techniques, Proceedings of the 16th annual international symposium on Computer architecture, p.396-406, April 1989, Jerusalem, Israel
	2	M. Ajtai , J. Komlós , E. Szemerédi, An 0(n log n) sorting network, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.1-9, December 1983 [doi>10.1145/800061.808726]
	3	T.E. Anderson. The performance implications of spin-waiting alternatives for shared-memory multiprocessors. Technical Report 89-04-03, University of Washington, Seattle, WA 98195, April 1989. To appear, IEEE Transactions on Parallel and Distributed Systems.
	4	K.E. Batcher. Sorting networks and their appfications. In Proceedings o} A FIPS Joint Computer Conference, 32:338-334, 1968.
	5	Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
	6	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]
	7	Eric Freudenthal , Allan Gottlieb, Process coordination with fetch-and-increment, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.260-268, April 08-11, 1991, Santa Clara, California, United States
	8	G.H. Pfister et al. The IBM research parallel processor prototype (RP3): introduction and architecture. In International Conference on Parallel Processing, 1985.
	9	D. Gawlick. Processing 'hot spots' in high performance systems. In Proceedings COMP- CON'85, 1985.
	10	James R. Goodman , Mary K. Vernon , Philip J. Woest, Efficient synchronization primitives for large-scale cache-coherent multiprocessors, Proceedings of the third international conference on Architectural support for programming languages and operating systems, p.64-75, April 03-06, 1989, Boston, Massachusetts, United States
	11	A. Gottlieb, R. Grishman, C.P. Kruskal, K.P. McAuliffe, L. Rudolph, and M. Snir. The NYU ultracomputer- designing an mimd parallel computer. 1EEE Transactions on Computers, C-32(2):175-189, February 1984.
	12	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]
	13	D. A. Kranz , R. H. Halstead, Jr. , E. Mohr, Mul-T: a high-performance parallel Lisp, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.81-90, June 19-23, 1989, Portland, Oregon, United States
	14	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]
	15	Leslie Lamport, A new solution of Dijkstra's concurrent programming problem, Communications of the ACM, v.17 n.8, p.453-455, Aug. 1974 [doi>10.1145/361082.361093]
	16	J. M. Mellor-Crummey , M. L. Scott, Algorithms for Scalable Synchronization on Shared-Memory Multiproceessors, University of Rochester, Rochester, NY, 1990
	17	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
	18	D. Peleg and E. Upfal. The token distribution problem. In 27th IEEE Symposium on Foundations of Computer Science, October 1986.
	19	G.H. Pfister and A. Norton. 'hot spot' contention and combining in multistage interconnection networks. IEEE Transactions on Computers, C-34(11):933-938, Novembcr 1985.
	20	H.S. Stone. Database applications of the fetchand-add instruction. IEEE Transactions on Computers, C-33(7):604-612, July 1984.
	21	Uzi Vishkin, A parallel-design distributed-implementation (PDDI) general-purpose computer, Theoretical Computer Science, v.32 n.1-2, p.157-172, July 1984 [doi>10.1016/0304-3975(84)90028-8]

CITED BY 32

	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
	Baruch Awerbuch , Shay Kutten , David Peleg, Competitive distributed job scheduling (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.571-580, May 04-06, 1992, Victoria, British Columbia, Canada
	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
	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
	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
	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
	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
	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
	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
	Bhaskar Ghosh , S. Muthukrishnan, Dynamic load balancing in parallel and distributed networks by random matchings (extended abstract), Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.226-235, June 27-29, 1994, Cape May, New Jersey, United States
	Shlomo Moran , Gadi Taubenfeld, A lower bound on wait-free counting, Proceedings of the twelfth annual ACM symposium on Principles of distributed computing, p.251-259, August 15-18, 1993, Ithaca, New York, United States
	Wilson C. Hsieh , Paul Wang , William E. Weihl, Computation migration: enhancing locality for distributed-memory parallel systems, ACM SIGPLAN Notices, v.28 n.7, p.239-248, July 1993
	Nir Shavit , Asaph Zemach, Diffracting trees, ACM Transactions on Computer Systems (TOCS), v.14 n.4, p.385-428, Nov. 1996
	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
	Beng-Hong Lim , Anant Agarwal, Waiting algorithms for synchronization in large-scale multiprocessors, ACM Transactions on Computer Systems (TOCS), v.11 n.3, p.253-294, Aug. 1993
	William Aiello , Baruch Awerbuch , Bruce Maggs , Satish Rao, Approximate load balancing on dynamic and asynchronous networks, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.632-641, May 16-18, 1993, San Diego, California, United States
	Nir Shavit , Asaph Zemach, Diffracting trees (preliminary version), Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.167-176, June 27-29, 1994, Cape May, New Jersey, United States
	Maurice Herlihy , Beng-Hong Lim , Nir Shavit, Scalable concurrent counting, ACM Transactions on Computer Systems (TOCS), v.13 n.4, p.343-364, Nov. 1995
	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
	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
	S. Haldar , K. Vidyasankar, Constructing 1-writer multireader multivalued atomic variables from regular variables, Journal of the ACM (JACM), v.42 n.1, p.186-203, Jan. 1995
	Shlomo Moran , Gadi Taubenfeld , Irit Yadin, Concurrent counting, Proceedings of the eleventh annual ACM symposium on Principles of distributed computing, p.59-70, August 10-12, 1992, Vancouver, British Columbia, Canada
	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
	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
	James Aspnes , Maurice Herlihy , Nir Shavit, Counting networks, Journal of the ACM (JACM), v.41 n.5, p.1020-1048, Sept. 1994
	Bhaskar Ghosh , F. T. Leighton , Bruce M. Maggs , S. Muthukrishnan , C. Greg Plaxton , R. Rajaraman , Andréa W. Richa , Robert E. Tarjan , David Zuckerman, Tight analyses of two local load balancing algorithms, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.548-558, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Nancy Lynch , Nir Shavit , Alex Shvartsman , Dan Touitou, Counting networks are practically linearizable, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.280-289, May 23-26, 1996, Philadelphia, Pennsylvania, United States
	Cynthia Dwork , Maurice Herlihy , Orli Waarts, Contention in shared memory algorithms, Journal of the ACM (JACM), v.44 n.6, p.779-805, Nov. 1997
	Hagit Brit , Shlomo Moran, Wait-freedom vs. bounded wait-freedom in public data structures (extended abstract), Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.52-60, August 14-17, 1994, Los Angeles, California, United States
	Roger Wattenhofer , Peter Widmayer, The counting pyramid: an adaptive distributed counting scheme, Journal of Parallel and Distributed Computing, v.64 n.4, p.449-460, April 2004
	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 , Marina Papatriantafilou , Philippas Tsigas, Self-tuning reactive diffracting trees, Journal of Parallel and Distributed Computing, v.67 n.6, p.674-694, June, 2007