Coins, weights and contention in balancing networks

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Coins, weights and contention in balancing networks

Full text

Pdf (1.22 MB)

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: 193 - 205

Year of Publication: 1994

ISBN:0-89791-654-9

Authors

William Aiello	Bellcore, 445 South St, Morristown, NJ
Ramarathnam Venkatesan	Bellcore, 445 South St, Morristown, NJ
Moti Yung	IBM, T.J. Watson Research Center, Yorktown Heights, NY

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): 3, Downloads (12 Months): 13, 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/197917.198090 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	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
	2	W. Aiello, R. Venkatesan and M. Yung, Approximate Counting Networks, Manuscript.
	3	M. Ajtai , J. Komlós , E. Szemerédi, Sorting in c log n parallel steps, Combinatorica, v.3 n.1, p.1-19, Jan. 1983 [doi>10.1007/BF02579338]
	4	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]
	5	K.E. Batcher, Sorting Networks and their Applications, In Proc. of the AFIPS Spring Joint Computer Conference, vol 32, pp 307-314,1968.
	6	V. Chv~tal, Lecture Notes on New AKS Sorting Network, DIMACS report, 92-29, 1992.
	7	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]
	8	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]
	9	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]
	10	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]
	11	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]
	12	M.R. Klugerman, personal communication.
	13	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 [doi>10.1145/164051.164079]
	14	N. Shavit, A. Zemach, Diffracting Trees, Proc, ACM SPAA, 1994.

CITED BY 11

	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
	Nir Shavit , Asaph Zemach, Diffracting trees, ACM Transactions on Computer Systems (TOCS), v.14 n.4, p.385-428, Nov. 1996
	Marios Mavronicolas , Michael Merritt , Gadi Taubenfeld, Sequentially consistent versus linearizable counting networks, Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing, p.133-142, May 04-06, 1999, Atlanta, Georgia, United States
	Costas Busch , Marios Mavronicolas, A combinatorial treatment of balancing networks, Journal of the ACM (JACM), v.43 n.5, p.794-839, Sept. 1996
	Hagit Brit , Shlomo Moran , Gadi Taubenfeld, Public data structures: counters as a special case, Theoretical Computer Science, v.289 n.1, p.401-423, 23 October 2002
	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
	Maurice Herlihy , Nir Shavit , Orli Waarts, Linearizable counting networks, Distributed Computing, v.9 n.4, p.193-203, February 1996
	Maurice Herlihy , Srikanta Tirthapura, Randomized smoothing networks, Journal of Parallel and Distributed Computing, v.66 n.5, p.626-632, May 2006
	Marios Mavronicolas , Thomas Sauerwald, The impact of randomization in smoothing networks, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, August 18-21, 2008, Toronto, Canada
	Marios Mavronicolas , Thomas Sauerwald, A randomized, o(log w)-depth 2 smoothing network, Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures, August 11-13, 2009, Calgary, AB, Canada