How asymmetry helps load balancing

ABSTRACT

This article deals with randomized allocation processes placing sequentially n balls into n bins. We consider multiple-choice algorithms that choose d locations (bins) for each ball at random, inspect the content of these locations, and then place the ball into one of them, for example, in a location with minimum number of balls. The goal is to achieve a good load balancing. This objective is measured in terms of the maximum load, that is, the maximum number of balls in the same bin.Multiple-choice algorithms have been studied extensively in the past. Previous analyses typically assume that the d locations for each ball are drawn uniformly and independently from the set of all bins. We investigate whether a nonuniform or dependent selection of the d locations of a ball may lead to a better load balancing. Three types of selection, resulting in three classes of algorithms, are distinguished: (1) uniform and independent, (2) nonuniform and independent, and (3) nonuniform and dependent.Our first result shows that the well-studied uniform greedy algorithm (class 1) does not obtain the smallest possible maximum load. In particular, we introduce a nonuniform algorithm (class 2) that obtains a better load balancing. Surprisingly, this algorithm uses an unfair tie-breaking mechanism, called Always-Go-Left, resulting in an asymmetric assignment of the balls to the bins. Our second result is a lower bound showing that a dependent allocation (class 3) cannot yield significant further improvement.Our upper and lower bounds on the maximum load are tight up to additive constants, proving that the Always-Go-Left algorithm achieves an almost optimal load balancing among all sequential multiple-choice algorithm. Furthermore, we show that the results for the Always-Go-Left algorithm can be generalized to allocation processes with more balls than bins and even to infinite processes in which balls are inserted and deleted by an oblivious adversary.

REFERENCES

• 1: Micah Adler , Soumen Chakrabarti , Michael Mitzenmacher , Lars Rasmussen, Parallel randomized load balancing, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.238-247, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225131]
• 2: 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]
• 3: Yossi Azar , Andrei Z. Broder , Anna R. Karlin , Eli Upfal, Balanced Allocations, SIAM Journal on Computing, v.29 n.1, p.180-200, Feb. 2000 [doi>10.1137/S0097539795288490]
• 4: Petra Berenbrink , Artur Czumaj , Angelika Steger , Berthold Vöcking, Balanced allocations: the heavily loaded case, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.745-754, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335411]
• 5: Berenbrink, P., Meyer auf der Heide, F., and Schröder, K. 1999. Allocating weighted jobs in parallel. ACM Trans. Comput. Syst. 32, 3, 1703--1739.
• 6: Richard Cole , Bruce M. Maggs , Friedhelm Meyer auf der Heide , Michael Mitzenmacher , Andréa W. Richa , Klaus Schröder , Ramesh K. Sitaraman , Berthold Vöcking, Randomized protocols for low-congestion circuit routing in multistage interconnection networks, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.378-388, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276790]
• 7: Richard Cole , Alan M. Frieze , Bruce M. Maggs , Michael Mitzenmacher , Andréa W. Richa , Ramesh K. Sitaraman , Eli Upfal, On Balls and Bins with Deletions, Proceedings of the Second International Workshop on Randomization and Approximation Techniques in Computer Science, p.145-158, October 08-10, 1998
• 8: Artur Czumaj , Friedhelm Meyerauf der, Contention Resolution in Hashing Based Shared Memory Simulations, SIAM Journal on Computing, v.29 n.5, p.1703-1739, March 2000 [doi>10.1137/S009753979529564X]
• 9: Martin Dietzfelbinger , Friedhelm Meyer auf der Heide, Simple, efficient shared memory simulations, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.110-119, June 30-July 02, 1993, Velen, Germany [doi>10.1145/165231.165246]
• 10: 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]
• 11: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 12: Malwina J Luczak , Eli Upfal, Reducing Network Congestion and Blocking Probability through Balanced Allocation, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.587, October 17-18, 1999
• 13: Friedhelm Meyer auf der Heide , Christian Scheideler , Volker Stemann, Exploiting storage redundancy to speed up randomized shared memory simulations, Theoretical Computer Science, v.162 n.2, p.245-281, Aug. 20, 1996 [doi>10.1016/0304-3975(96)00032-1]
• 14: Friedhelm Meyer auf der Heide , Klaus Schröder , Frank Schwarze, Routing on Networks of Optical Crossbars (Extended Abstract), Proceedings of the Second International Euro-Par Conference on Parallel Processing, p.299-306, August 26-29, 1996
• 15: 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
• 16: Michael David Mitzenmacher , Alistair Sinclair, The power of two choices in randomized load balancing, 1996
• 17: Mitzenmacher, M., Richa, A., and Sitaraman, R. 2001. Handbook of Randomized Computing. "The power of two random choices: A survey of the techniques and results." Kluwer Press.
• 18: Volker Stemann, Parallel balanced allocations, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.261-269, June 24-26, 1996, Padua, Italy [doi>10.1145/237502.237565]
• 19: Vvedenskaya, N. D., Dobrushin, R. L., and Karpelevich, F. I. 1996. Queueing system with selection of the shortest of two queues: An assymptotic approach.Prob. Inf. Trans. 32, 1, 15--27.

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

General Terms:
Algorithms

Keywords:
Randomized algorithms, balls and bins processes, probabilistic analysis