Geometric generalizations of the power of two choices

ABSTRACT

A well-known paradigm for load balancing in parallel and distributed systems is the "power of two choices," whereby an item is stored at the less loaded of two (or more) random alternative servers. We investigate the power of two choices in natural settings where items and servers reside in a geometric space and each item is associated with the server that is its nearest neighbor. This is the setting for example in the Chord distributed hash table, where the geometric space is determined by clockwise distance on a one-dimensional ring. For example, our analysis shows that when $n$ items are placed at n servers with d choices per item, the maximum load at any server is log log n/ log d + O(1) with high probability, only an additive constant more than when servers are chosen uniformly at random. Our proofs are quite general, showing that the power of two choices works under a variety of distributions, with most geometric constructions having at most an additive O(1) penalty. We also show that these techniques still work under highly unbalanced distributions, and give sharp bounds on the necessary number of choices. Finally, we provide simulation results demonstrating the load balance that results as the system size scales into the millions.

REFERENCES

• 1: 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]
• 2: 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]
• 3: Byers, J., Considine, J., and Mitzenmacher, M. Simple Load Balancing for Distributed Hash Tables. In Proceedings of the 2nd International Peer-to-Peer Symposium, 2003.
• 4: Frank Dabek , M. Frans Kaashoek , David Karger , Robert Morris , Ion Stoica, Wide-area cooperative storage with CFS, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 5: Devdatt Dubhashi , Desh Ranjan, Balls and bins: a study in negative dependence, Random Structures & Algorithms, v.13 n.2, p.99-124, Sept. 1998 [doi>10.1002/(SICI)1098-2418(199809)13:2<99::AID-RSA1>3.0.CO;2-M ]
• 6: Kaashoek, M.F., and Karger, D.R. Koorde: A simple degree-optimal distributed hash table. In Proceedings of the 2nd International Peer-to-Peer Symposium, 2003.
• 7: 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]
• 8: Karger, D.R. and Ruhl, M. Simple Efficient Load Balancing Algorithms for Peer-to-Peer Systems. In Proceedings of the 3rd International Peer-to-Peer Symposium, 2004.
• 9: Dahlia Malkhi , Moni Naor , David Ratajczak, Viceroy: a scalable and dynamic emulation of the butterfly, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California [doi>10.1145/571825.571857]
• 10: Miles, R. E. A synopsis of 'Poisson flats in Euclidean spaces'. In: E. F. Harding and D. G. Kendall (eds), Stochastic Geometry. New York, John Wiley, pp. 202--227, 1974.
• 11: Michael David Mitzenmacher , Alistair Sinclair, The power of two choices in randomized load balancing, 1996
• 12: Mitzenmacher, M., Richa, A., and Sitaraman, R. The Power of Two Choices: A Survey of Techniques and Results. Kluwer Academic Publishers, Norwell, MA, 2001, pp. 255--312. edited by P. Pardalos, S. Rajasekaran, J. Reif, and J. Rolim.
• 13: Moller, J. Random tesselations in Rd. Advances in Applied Probability, 21, pp. 37--73, 1989.
• 14: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 15: 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 [doi>10.1145/777412.777421]
• 16: Sylvia Ratnasamy , Paul Francis , Mark Handley , Richard Karp , Scott Schenker, A scalable content-addressable network, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.161-172, August 2001, San Diego, California, United States
• 17: Sylvia Ratnasamy , Brad Karp , Scott Shenker , Deborah Estrin , Ramesh Govindan , Li Yin , Fang Yu, Data-centric storage in sensornets with GHT, a geographic hash table, Mobile Networks and Applications, v.8 n.4, p.427-442, August 2003 [doi>10.1023/A:1024591915518]
• 18: Antony I. T. Rowstron , Peter Druschel, Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems, Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms Heidelberg, p.329-350, November 12-16, 2001
• 19: Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek , Hari Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.149-160, August 2001, San Diego, California, United States
• 20: Berthold Vöcking, How Asymmetry Helps Load Balancing, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.131, October 17-18, 1999
• 21: Zhao, B. Y., Huang, L., Stribling, J., Rhea, S. C., Joseph, A. D., and Kubiatowicz, J. D. Tapestry: A Resilient Global-scale Overlay for Service Deployment. IEEE Journal on Selected Areas in Communications 22, 1 (2004), 41--53.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

General Terms:
Algorithms, Performance

Keywords:
distributed hash tables, load balancing, two choices