On the analysis of randomized load balancing schemes

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the analysis of randomized load balancing schemes

Full text

Pdf (1.43 MB)

Source

ACM Symposium on Parallel Algorithms and Architectures archive
Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures table of contents

Newport, Rhode Island, United States

Pages: 292 - 301

Year of Publication: 1997

ISBN:0-89791-890-8

Author

Michael Mitzenmacher

Digital Systems Research Center, 130 Lytton Ave., Palo Alto, CA

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 27, Citation Count: 14

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/258492.258521 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	I. J. B. F. Adan, G. van Houtum, and J. van der Wal. Upper and lower bounds for the waiting time in the symmetric shortest queue system. Annals of Operations Research, 48:197-217, 1994.
	2	I. J. B. F. Adan, J. Wessels, and W. H. M. Zijm. Analysis of the symmetric shortest queue problem. Stochastic Models, 6:691-713, 1990.
	3	I. J. B. F. Adan , J. Wessels , W. H. M. Zijm, Analysis of the asymmetric shortest queue problem, Queueing Systems: Theory and Applications, v.8 n.1, p.1-58, Feb. 1991 [doi>10.1007/BF02412240]
	4	Murat Alanyali , Bruce Hajek, Analysis of simple algorithms for dynamic load balancing, Mathematics of Operations Research, v.22 n.4, p.840-871, Nov. 1997 [doi>10.1287/moor.22.4.840]
	5	Yossi Azar , Andrei Z. Broder , Anna R. Karlin , Eli Upfal, Balanced allocations (extended abstract), Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.593-602, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195412]
	6	A. Bestavros. Load profiling in distributed real-time systems. Preprint.
	7	Michael Donald Dahlin , David A. Patterson, Serverless network file systems, 1995
	8	Derek L. Eager , Edward D. Lazowska , John Zahorjan, Adaptive load sharing in homogeneous distributed systems, IEEE Transactions on Software Engineering, v.12 n.5, p.662-675, May 1986
	9	D L Eager , E D Lazowska , J Zahorjan, A comparison of receiver-initiated and sender-initiated adaptive load sharing, Performance Evaluation, v.6 n.1, p.53-68, March 1986 [doi>10.1016/0166-5316(86)90008-8]
	10	D. L. Eager , E. D. Lazowska , J. Zahorjan, The limited performance benefits of migrating active processes for load sharing, Proceedings of the 1988 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.63-72, May 24-27, 1988, Santa Fe, New Mexico, United States
	11	S. N. Ethier and T. G. Kurtz. Markov Processes: Characterization and Convergence. John Wiley and Sons, 1986.
	12	B. Hajek. Asymptotic analysis of an assignment problem arising in a distributed communications protocol. In Proceedings of the 27th Conference on Decision and Control, pages 1455-1459, 1988.
	13	Mor Harchol-Balter , David Wolfe, Bounding delays in packet-routing networks, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.248-257, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225133]
	14	Richard M. Karp , Michael Luby , Friedhelm Meyer auf der Heide, Efficient PRAM simulation on a distributed memory machine, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.318-326, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129743]
	15	R. M. Karp and M. Sipser. Maximum matchings in sparse random graphs. In Proceedings of the 22nd IEEE Symposium on Foundations of Computer Science, pages 364-375, 1981.
	16	R. M. Karp , U. V. Vazirani , V. V. Vazirani, An optimal algorithm for on-line bipartite matching, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.352-358, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100262]
	17	F. P. Kelly. Reversibility and Stochastic Networks. John Wiley and Sons, 1979.
	18	L. Kleinrock. Queuein9 Systems, Volume L" Theory. John Wiley and Sons, 1976.
	19	Thomas Kunz, The Influence of Different Workload Descriptions on a Heuristic Load Balancing Scheme, IEEE Transactions on Software Engineering, v.17 n.7, p.725-730, July 1991 [doi>10.1109/32.83908]
	20	T. G. Kurtz. Solutions of ordinary differential equations as fimits of pure jump Markov processes. Journal of Applied Probability, 7:49-58, 1970.
	21	T. G. Kurtz. Limit theorems for sequences of jump Markov processes approximating ordinary differential processes. Journal of Applied Probability, 8:344-356, 1971.
	22	T. G. Kurtz. Strong approximation theorems for density dependent Markov chains. Stochastic Processes and Applications, 6:223-240, 1978.
	23	T. G. Kurtz. Approximation of Population Processes. CBMS-NSF Regional Con}. Series in Applied Math. SIAM, 1981.
	24	Michael Mitzenmacher, How useful is old information (extended abstract)?, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.83-91, August 21-24, 1997, Santa Barbara, California, United States [doi>10.1145/259380.259426]
	25	Michael Mitzenmacher, Bounds on the greedy routing algorithm for array networks, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.346-353, June 27-29, 1994, Cape May, New Jersey, United States [doi>10.1145/181014.181446]
	26	Michael Mitzenmacher, Constant time per edge is optimal on rooted tree networks, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.162-169, June 24-26, 1996, Padua, Italy [doi>10.1145/237502.237524]
	27	M. Mitzenmacher, Load balancing and density dependent jump Markov processes, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.213, October 14-16, 1996
	28	Michael David Mitzenmacher , Alistair Sinclair, The power of two choices in randomized load balancing, 1996
	29	R. Righter. and J. Shanthikumar. Extremal properties of the FIFO discipline in queueing networks. Journal of Applied Probability, 29:967-978, November 1992.
	30	A. Shwartz and A. Weiss. Large Deviations for Performance Analysis. Chapman & Hall, 1995.
	31	George D. Stamoulis , John N. Tsitsiklis, The efficiency of greedy routing in hypercubes and butterflies, Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.248-259, July 21-24, 1991, Hilton Head, South Carolina, United States [doi>10.1145/113379.113402]
	32	N.D. Vvedenskaya, R. L. Dobrushin, and F. I. Karpelevich. Queueing system with selection of the shortest of two queues: An asymptotic approach. Problems of Information Transmission, 32:15-27, 1996.
	33	S. Zhou, A Trace-Driven Simulation Study of Dynamic Load Balancing, IEEE Transactions on Software Engineering, v.14 n.9, p.1327-1341, September 1988 [doi>10.1109/32.6176]

CITED BY 14

	Petra Berenbrink , Tom Friedetzky , Ernst W. Mayr, Parallel continuous randomized load balancing (extended abstract), Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.192-201, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Michael Mitzenmacher, Analyses of load stealing models based on differential equations, Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.212-221, 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
	Petra Berenbrink , Tom Friedetzky , Angelika Steger, Randomized and adversarial load balancing, Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures, p.175-184, June 27-30, 1999, Saint Malo, France
	Petra Berenbrink , Marco Riedel , Christian Scheideler, Simple competitive request scheduling strategies, Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures, p.33-42, June 27-30, 1999, Saint Malo, France
	Michael Mitzenmacher, How useful is old information (extended abstract)?, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.83-91, August 21-24, 1997, Santa Barbara, California, United States
	Artur Czumaj, Recovery time of dynamic allocation processes, Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.202-211, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Lingkun Chu , Hong Tang , Tao Yang , Kai Shen, Optimizing data aggregation for cluster-based internet services, ACM SIGPLAN Notices, v.38 n.10, October 2003
	Changxun Wu , Randal Burns, Tunable randomization for load management in shared-disk clusters, ACM Transactions on Storage (TOS), v.1 n.1, p.108-131, February 2005
	Aris Anagnostopoulos , Ioannis Kontoyiannis , Eli Upfal, Steady state analysis of balanced-allocation routing, Random Structures & Algorithms, v.26 n.4, p.446-467, July 2005
	Christopher Stewart , Kai Shen, Performance modeling and system management for multi-component online services, Proceedings of the 2nd conference on Symposium on Networked Systems Design & Implementation, p.71-84, May 02-04, 2005
	Changxun Wu , Randal Burns, Handling Heterogeneity in Shared-Disk File Systems, Proceedings of the 2003 ACM/IEEE conference on Supercomputing, p.7, November 15-21, 2003
	Haiying Shen , Cheng-Zhong Xu, Hash-based proximity clustering for efficient load balancing in heterogeneous DHT networks, Journal of Parallel and Distributed Computing, v.68 n.5, p.686-702, May, 2008
	Haiying Shen , Cheng-Zhong Xu, Locality-Aware and Churn-Resilient Load-Balancing Algorithms in Structured Peer-to-Peer Networks, IEEE Transactions on Parallel and Distributed Systems, v.18 n.6, p.849-862, June 2007