Consistent load balancing via spread minimization

ABSTRACT

Motivated by applications to web caching and other distributed server architectures, we analyze load balancing algorithms from the standpoint of spread, which measures the number of different assignments an item receives across multiple iterations of the algorithm on varying load distributions. Minimizing spread while balancing load is important in order to make efficient use of server resources such as memory and in order to minimize service latency. In the paper, we consider both on-line and off-line versions of the problem. Most importantly, we describe on-line load balancing algorithms with very low spread, which means that the assignments made for most items do not change even when the loads associated with the items do change. This means that load balancing is an example of a problem for which it is possible to find highly stable (or, consistent) on-line algorithms --- i.e. algorithms for which the output changes only slightly (with high probability) even if the inputs change dramatically.This paper is dedicated to the memory of Danny Lewin, who pioneered the notion of consistent hashing and its applications to load balancing and content distribution on the Internet. Danny's ideas furnished many of the underpinnings for the problem and algorithms studied herein.

REFERENCES

• 1: Beck, J. and Fiala, T. "Integer-making" theorems, Discrete Appl. Math.3, 1--8.
• 2: József Beck , Vera T. Sós, Discrepancy theory, Handbook of combinatorics (vol. 2), MIT Press, Cambridge, MA, 1996
• 3: E. G. Coffman, Jr. , M. R. Garey , D. S. Johnson, Approximation algorithms for bin packing: a survey, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 4: Leslie A. Hall, Approximation algorithms for scheduling, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 5: David Karger , Eric Lehman , Tom Leighton , Rina Panigrahy , Matthew Levine , Daniel Lewin, Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the World Wide Web, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.654-663, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258660]
• 6: Lewin, D. Consistent hashing and random trees: Algorithms for caching in distributed networks. Master's thesis, Department of EECS, MIT, 1998. Available at the MIT Library, http://thesis.mit.edu/.
• 7: J. K. Lenstra , D. B. Shmoys , É. Tardos, Approximation algorithms for scheduling unrelated parallel machines, Mathematical Programming: Series A and B, v.46 n.3, p.259-271, Apr. 1990 [doi>10.1007/BF01585745]
• 8: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 9: Spencer, J. Six standard deviations suffice, Trans. Amer. Math. Soc. 289, 679--706.
• 10: David B. Shmoys , Éva Tardos, An approximation algorithm for the generalized assignment problem, Mathematical Programming: Series A and B, v.62 n.3, p.461-474, Dec. 8, 1993 [doi>10.1007/BF01585178]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms, Theory

Keywords:
load balancing, on-line algorithms, randomized algorithms