The Taub Faculty of Computer Science Events and Talks

Say we place m balls sequentially into n bins, where each ball is placed by randomly selecting d bins and placing it in the least loaded of them. What is the load of the maximum bin when m>>n? It is well known that when d=1 the maximum load is m/n + \tildeO(sqrt(m/n)), whereas when d>=2 the maximum load is m/n + loglog n. Thus when more than one bin is sampled, the gap between maximum and average does not increase with the number of balls. We investigate a larger family of placement schemes. We focus on the case where each time a ball is placed, with probability half we use d=1 and with probability half we use d=2. We show that the maximum load for this process is m/n + log n. Thus, surprisingly, even though half the balls are thrown using a one-choice scheme, the gap between maximum load and average load does not increase with the number of balls. Along the way we develop new proof techniques which greatly simplify existing proofs and show general conditions under which a placement scheme outputs a balanced allocation.

Joint work with Kunal Talwar and Yuval Peres