Approximate load balancing on dynamic and asynchronous networks

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Approximate load balancing on dynamic and asynchronous networks

Full text

Pdf (973 KB)

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: 632 - 641

Year of Publication: 1993

ISBN:0-89791-591-7

Authors

William Aiello
Baruch Awerbuch
Bruce Maggs
Satish Rao

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 20, Citation Count: 17

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.167250 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.

	AB92	Yonatan Aumann , Michael Ben-Or, Computing with faulty arrays, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.162-169, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129729]
	AD87	David Aldous , Persi Diaconis, Strong uniform times and finite random walks, Advances in Applied Mathematics, v.8 n.1, p.69-97, March 1987 [doi>10.1016/0196-8858(87)90006-6]
	AGR92	Yehuda Afek , Eli Gafni , Adi Rosén, The slide mechanism with applications in dynamic networks, Proceedings of the eleventh annual ACM symposium on Principles of distributed computing, p.35-46, August 10-12, 1992, Vancouver, British Columbia, Canada [doi>10.1145/135419.135430]
	AHS91	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]
	AL91	Bill Aiello , Tom Leighton, Coding theory, hypercube embeddings, and fault tolerance, Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.125-136, July 21-24, 1991, Hilton Head, South Carolina, United States [doi>10.1145/113379.113391]
	Ald83	D. Aldous. Random walks on finite groups and rapidly mixing markov chains. Seminaire de Probabilities XVII Lecture Notes in Mathematics, 986, 1983.
	Ald87	D. Aldous. On the markov chain simulation method for uniform combinatorial distributions and simulated annealing. Probability in Eng. and Inf. Sci., 1:33-46, 1987.
	Alo86	N Alon, Eigen values and expanders, Combinatorica, v.6 n.2, p.83-96, 1986 [doi>10.1007/BF02579166]
	AMS89	Baruch Awerbuch, Yishay Mansour, and Nir Shavit. End-to-end communication with polynomial overhead. In Proc. 30th IEEE Symp. on Foundations of Computer Science, pages 358-363, October 1989.
	APV91	Baruch Awerbuch , Boaz Patt-Shamir , George Varghese, Self-stabilization by local checking and correction (extended abstract), Proceedings of the 32nd annual symposium on Foundations of computer science, p.268-277, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185378]
	HLN87	J. Hastad , T. Leighton , M. Newman, Reconfiguring a hypercube in the presence of faults, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.274-284, January 1987, New York, New York, United States [doi>10.1145/28395.28425]
	HLN89	J. Hastad , T. Leighton, Fast computation using faulty hypercubes, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.251-263, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73031]
	HLS92	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]
	HSW91	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]
	JS88	Mark Jerrum , Alistair Sinclair, Conductance and the rapid mixing property for Markov chains: the approximation of permanent resolved, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.235-244, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62234]
	KKL+90	C. Kaklamanis, A. R. Karlin, E T. Leighton. V. Milenkovic. P. Raghavan. S. Rao, C. Thomborson, and A. Tsantilas. Asymptotically tight bounds for computing with faulty arrays of processors. In Proceedings of the 31 st Annual Symposium on Foundations of Computer Science, pages 285-296, October 1990.
	KP92	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]
	Lei92	F. Thomson Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
	LM89	T. Leighton and B. Maggs. Expanders might be practical: Fast algorithms for routing around faults in multibutterflies. In Proceedings of the 30th Annual Symposium on Foundations of Computer Science, pages 384-389, October 1989.
	LMS92	T. Leighton, B. Maggs, and R. Sitaraman. On the fault tolerance of some popular bounded-degree networks. In Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, pages 542-552, October 1992.
	Lyu90	Y.-D. Lyuu, Fast-fault-tolerant parallel communication and on-line maintenance using information dispersal, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.378-387, July 02-06, 1990, Island of Crete, Greece [doi>10.1145/97444.97705]
	Mih89	Milena Mihail. Conductance and convergence of markov chains - a combinatorial treatment of expanders. In Proc. 30th IEEE Syrup. on Foundations of Computer Science, pages 526-531, October 1989.
	PU89	David Peleg , Eli Upfal, The token distribution problem, SIAM Journal on Computing, v.18 n.2, p.229-243, April 1989 [doi>10.1137/0218015]
	PV76	Nicholas Pippenger , Leslie G. Valiant, Shifting Graphs and Their Applications, Journal of the ACM (JACM), v.23 n.3, p.423-432, July 1976 [doi>10.1145/321958.321962]
	Rab89	Michael O. Rabin, Efficient dispersal of information for security, load balancing, and fault tolerance, Journal of the ACM (JACM), v.36 n.2, p.335-348, April 1989 [doi>10.1145/62044.62050]

CITED BY 17

	Robert Garmann, Maintaining dynamic geometric objects on parallel processors, Proceedings of the IEEE symposium on Parallel rendering, p.31-38, October 20-21, 1997, Phoenix, Arizona, United States
	S. Muthukrishnan , Rajmohan Rajaraman, An adversarial model for distributed dynamic load balancing, Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.47-54, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Elliot Anshelevich , David Kempe , Jon Kleinberg, Stability of load balancing algorithms in dynamic adversarial systems, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	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
	Bhaskar Ghosh , S. Muthukrishnan , Martin H. Schultz, First and second order diffusive methods for rapid, coarse, distributed load balancing (extended abstract), Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.72-81, June 24-26, 1996, Padua, Italy
	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
	Baruch Awerbuch , Tom Leighton, Improved approximation algorithms for the multi-commodity flow problem and local competitive routing in dynamic networks, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.487-496, May 23-25, 1994, Montreal, Quebec, Canada
	Lujun Jia , Rajmohan Rajaraman , Christian Scheideler, On local algorithms for topology control and routing in ad hoc networks, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA
	Moni Naor , Udi Wieder, Novel architectures for P2P applications: the continuous-discrete approach, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA
	Perry Fizzano , David Karger , Clifford Stein , Joel Wein, Job scheduling in rings, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.210-219, June 27-29, 1994, Cape May, New Jersey, United States
	Rajmohan Rajaraman, Topology control and routing in ad hoc networks: a survey, ACM SIGACT News, v.33 n.2, June 2002
	Jacques Bahi , Raphaël Couturier , Flavien Vernier, Synchronous distributed load balancing on dynamic networks, Journal of Parallel and Distributed Computing, v.65 n.11, p.1397-1405, November 2005
	William Aiello , Eyal Kushilevitz , Rafail Ostrovsky , Adi Rosén, Adaptive packet routing for bursty adversarial traffic, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.359-368, May 24-26, 1998, Dallas, Texas, United States
	Kay Dörnemann , Jörg Prenzer , Bernd Freisleben, A peer-to-peer meta-scheduler for service-oriented grid environments, Proceedings of the first international conference on Networks for grid applications, October 17-19, 2007, Lyon, France
	Moni Naor , Udi Wieder, Novel architectures for P2P applications: The continuous-discrete approach, ACM Transactions on Algorithms (TALG), v.3 n.3, p.34-es, August 2007
	Tobias Friedrich , Thomas Sauerwald, Near-perfect load balancing by randomized rounding, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA
	Abderrahmane Sider , Raphaël Couturier, Fast load balancing with the most to least loaded policy in dynamic networks, The Journal of Supercomputing, v.49 n.3, p.291-317, September 2009