BALANCED ALLOCATION: PATIENCE IS NOT A VIRTUE∗

arXiv:1602.08298v2 [] 22 Jan 2018

JOHN AUGUSTINE† , WILLIAM K. MOSES JR.‡ , AMANDA REDLICH§ , AND ELI UPFAL¶
Abstract.
Load balancing is a well-studied problem, with balls-in-bins being the primary framework. The
greedy algorithm Greedy[d] of Azar et al. places each ball by probing d > 1 random bins and placing
the ball in the least loaded of them. With high probability, the maximum load under Greedy[d]
is exponentially lower than the result when balls are placed uniformly randomly. Vöcking showed
that a slightly asymmetric variant, Left[d], provides a further significant improvement. However, this
improvement comes at an additional computational cost of imposing structure on the bins.
Here, we present a fully decentralized and easy-to-implement algorithm called FirstDiff[d] that
combines the simplicity of Greedy[d] and the improved balance of Left[d]. The key idea in FirstDiff[d]
is to probe until a different bin size from the first observation is located, then place the ball. Although
the number of probes could be quite large for some of the balls, we show that FirstDiff[d] requires
only at most d probes on average per ball (in both the standard and the heavily-loaded settings).
Thus the number of probes is no greater than either that of Greedy[d] or Left[d]. More importantly,
we show that FirstDiff[d] closely matches the improved maximum load ensured by Left[d] in both the
standard and heavily-loaded settings. We further provide a tight lower bound on the maximum load
up to O(log log log n) terms. We additionally give experimental data that FirstDiff[d] is indeed as
good as Left[d], if not better, in practice.
Key words.
allocation

Load balancing, FirstDiff, Balanced allocation, Randomized algorithms, Task

AMS subject classifications. 60C05, 60J10, 68R05

1. Introduction. Load balancing is the study of distributing loads across multiple entities such that the load is minimized across all the entities. This problem
arises naturally in many settings, including the distribution of requests across multiple servers, in peer-to-peer networks when requests need to be spread out amongst
the participating nodes, and in hashing. Much research has focused on practical
implementations of solutions to these problems [12, 6, 13].
Our work builds on several classic algorithms in the theoretical balls-in-bins
model. In this model, m balls are to be placed sequentially into n bins and each
ball probes the load in random bins in order to make its choice. Here we give a new
algorithm, FirstDiff[d], which performs as well as the best known algorithm, Left[d],
while being significantly easier to implement.
The allocation time for a ball is the number of probes made to different bins before
placement. The challenge is to balance the allocation time versus the maximum bin
load. For example, using one probe per ball, i.e. placing each ball uniformly at
∗ An earlier version of this paper appeared in [1]. The previous version had only expectation
upper bounds for average number of probes and no lower bounds. This version has lower bounds on
maximum load and high probability upper bounds for average number of probes, as well as cleaner
proofs for the same.
† Department of Computer Science & Engineering, Indian Institute of Technology Madras, Chennai, India. (augustine@iitm.ac.in). Supported by the IIT Madras New Faculty Seed Grant, the
IIT Madras Exploratory Research Project, and the Indo-German Max Planck Center for Computer
Science (IMPECS).
‡ Department of Computer Science & Engineering, Indian Institute of Technology Madras, Chennai, India. (wkmjr3@gmail.com).
§ Department of Mathematics, Bowdoin College, ME, USA (aredlich@bowdoin.edu). This material
is based upon work supported by the National Science Foundation under Grant No. DMS-0931908
while the author was in residence at the Institute for Computational and Experimental Research in
Mathematics in Providence, RI, during the Spring 2014 semester.
¶ Department of Computer Science, Brown University, RI, USA (eli@cs.brown.edu).

1

2

J. AUGUSTINE, W. K. MOSES JR., A. REDLICH, AND E. UPFAL

random, the maximum load of any bin when m = n will be lnlnlnnn (1 + o(1)) (with high
probability1 ) and total allocation time of n probes [11]. On the other hand, using d
probes per ball and placing the ball in the lightest bin, i.e. Greedy[d], first studied by
Azar et. al [2], decreases the maximum load to lnlnlndn + O(1) with allocation time of
nd. In other words, using d ≥ 2 choices improves the maximum load exponentially,
at a linear allocation cost.
Vöcking [15] introduced a slightly asymmetric algorithm, Left[d], which quite
surprisingly guaranteed (w.h.p.) a maximum load of dlnlnlnφnd + O(1) (where φd is a
constant between 1.61 and 2 when d ≥ 2) using the same allocation time of nd probes
as Greedy[d] when m = n. This analysis of maximum load for Greedy[d] and Left[d]
was extended to the heavily-loaded case (when m ≫ n) by Berenbrink et al. [3].
However, Left[d] in [15] and [3] utilizes additional processing. Bins are initially sorted
into groups and treated differently according to group membership. Thus practical
implementation, especially in distributed settings, requires significant computational
effort in addition to the probes themselves.
Our Contribution. We present a new algorithm, FirstDiff[d]. This algorithm requires no pre-sorting of bins; instead FirstDiff[d] uses real-time feedback to adjust its
number of probes for each ball2 .
The natural comparison is with the classic Greedy[d] algorithm; FirstDiff[d] uses
the same number of probes, on average, as Greedy[d] but produces a significantly
smaller maximum load. In fact, we show that the maximum load is as small as that of
Left[d] when m = n. Furthermore, it is comparable to Left[d] when heavily loaded. For
both the m = n and heavily loaded cases, FirstDiff[d] has much lower computational
overhead than Left[d].
This simpler implementation makes FirstDiff[d] especially suitable for practical
applications; it is amenable to parallelization, for example, and requires no central
control or underlying structure. Some applications have a target maximum load and
aim to minimize the necessary number of probes. From this perspective, our algorithm
again improves on Greedy[d]: the maximum load of FirstDiff[ln d] is comparable to that
of Greedy[d], and uses exponentially fewer probes per ball.
Theorem 3.1 Use FirstDiff[d], where maximum number of probes allowed per ball is
22d/3 , to allocate n balls into n bins. The average number of probes required per ball
is at most d on expectation and w.h.p. Furthermore, the maximum load of any bin is
log n
at most log
n ≥ max(2, n0 ), where
0.66d + O(1) with high probability when d ≥ 4 and 
4
log n
≤ n12 .
n0 is the smallest value of n such that for all n > n0 , 36 log n 72e5n

Theorem 4.1 Use FirstDiff[d], where maximum number of probes allowed per ball
is 2d/2.17 , to allocate m balls into n bins. When m ≥ 72(nλ log n + n) where λ is
taken from Lemma 4.5, n ≥ n0 where n0 is the smallest value of n that satisfies
0.00332n(λ log n + 1)d/2d/2.17 ≥ log n, and d ≥ 6, it takes at most d probes on average
to place every ball on expectation and with high probability. Furthermore, for an
absolute constant c,

Pr Max. load of any bin >

m
n

+

log log n
0.46d

+ c log log log n ≤ c(log log n)−4 .

Our technique for proving that the average number of probes is bounded is novel
1 We use the phrase “with high probability” (or w.h.p. in short) to denote probability of the form
1 − O(n−c ) for some suitable c > 0. Furthermore, every log in this paper is to base 2 unless otherwise
mentioned.
2 Thus we are concerned with the average number of probes per ball throughout this paper.

BALANCED ALLOCATION: PATIENCE IS NOT A VIRTUE

3

to the best of our knowledge. As the number of probes required by each ball is
dependent on the configuration of the balls-in-bins at the time the ball is placed,
the naive approach to computing its expected value quickly becomes too conditional.
Instead, we show that this conditioning can be eliminated by carefully overcounting
the number of probes required for each configuration, leading to a proof that is then
quite simple. The heavily-loaded case is significantly more complex than the m = n
case; however the basic ideas remain the same.
The upper bound on the maximum load is proved using the layered induction
technique. However, because FirstDiff[d] is a dynamic algorithm, the standard recursion used in layered induction must be altered. We use coupling and some more
complex analysis to adjust the standard layered induction to this context.
We furthermore provide a tight lower bound on the maximum load for a broad
class of algorithms which use variable probing.
Theorem 5.1 Let Alg[k] be any algorithm that places m balls into n bins, where
m ≥ n, sequentially one by one and satisfies the following conditions:
1. At most k probes are used to place each ball.
2. For each ball, each probe is made uniformly at random to one of the n bins.
3. For each ball, each probe is independent of every other probe.
The maximum load of any bin after placing all m balls using Alg[k] is at least m
n +
ln ln n
ln k − Θ(1) with high probability.
We use the above theorem to provide a lower bound on the maximum load of
FirstDiff[d], which is tight up to O(log log log n) terms.
Theorem 5.2 The maximum load of any bin after placing m balls into n bins using
FirstDiff[d], where maximum number of probes allowed per ball is 2Θ(d) , is at least
ln ln n
m
n + Θ(d) − Θ(1) with high probability.
Related Work. Several other algorithms in which the number of probes performed
by each ball is adaptive in nature have emerged in the past, such as work done by
Czumaj and Stemann [5] and by Berenbrink et al. [4].
Czumaj and Stemann [5] present an interesting “threshold” algorithm. First they
define a process Adaptive-Allocation-Process, where each load value has an associated
threshold and a ball is placed when the number of probes that were made to find a bin
of a particular load exceeded the associated threshold. Then, by carefully selecting the
thresholds for the load values, they develop M-Threshold, where each ball probes bins
until it finds one whose load is within some predetermined threshold. The bounds
on maximum load and on average allocation time are better than our algorithm’s,
but the trade-off is that computing the required threshold value often depends on the
knowledge (typically unavailable in practical applications) of the total number of balls
that will ever be placed. Furthermore their proofs are for m = n and don’t extend
easily to when m > n.
More recently, Berenbrink et al. [4] develop a new threshold algorithm, Adaptive,
which is similar to M-Threshold but where the threshold value used for a given ball
being placed depends on the number of balls placed thus far. They analyze this algorithm when m ≥ n and also extend the analysis of M-Threshold from [5] to the
m ≥ n case. They show that both algorithms have good bounds on maximum load
and average allocation time, but again this comes at the trade-off of requiring some
sort of global knowledge when placing the balls. In the case of Adaptive, each ball
must know what its order in the global placement of balls is, and in the case of M-

4

J. AUGUSTINE, W. K. MOSES JR., A. REDLICH, AND E. UPFAL

Threshold, each ball must know the total number of balls that will ever be placed.
Our algorithm is unique in that it requires no such global knowledge at all; it is able
to make decisions based on the probed bins’ load values alone.
Definitions. In the course of this paper we will use several terms from probability
theory, which we define below for convenience.
Consider two Markov chains At and Bt over time t ≥ 0 with state spaces S1 and
S2 respectively. A coupling (cf. [8]) of At and Bt is a Markov chain (At , Bt ) over time
t ≥ 0 with state space S1 × S2 such that At and Bt maintain their original transition
probabilities.
Consider two vectors u, v ∈ Zn . Let u′ and v ′ be permutations of u and v
′
respectively such that u′i ≥ u′i+1 and vi′ ≥ vi+1
for all 1 ≤ i ≤ n − 1. We say u
majorizes v (or v is majorized by u) when
i
i
P
P
u′j ≥
vj′ , ∀1 ≤ i ≤ n.
j=1

j=1

For a given allocation algorithm C which places balls into n bins, we define the load
vector ut ∈ (Z∗ )n of that process after t balls have been placed as follows: the ith
index of ut denotes the load of the ith bin (we can assume a total order on the bins
according to their IDs). Note that ut , t ≥ 0, is a Markov chain.
Consider two allocation algorithms C and D that allocate m balls. Let the load
vectors for C and D after t balls have been placed using the respective algorithms be
ut and v t respectively. We say that C majorizes D (or D is majorized by C) if there
is a coupling between C and D such that ut majorizes v t for all 0 ≤ t ≤ m.
Berenbrink et al. [3] provide an illustration of the above ideas being applied in
the load balancing context.

We also use Theorem 2.1 from Janson [7] in order to achieve high probability
concentration bounds on geometric random variables. We first set up the terms in
the theorem and then restate it below. Let X1 , . . . , Xn be n ≥ 1 geometric random
n
P
Xi ,
variables with parameters p1 , . . . , pn respectively. Define p∗ = mini pi , X =
and µ = E[X] =

n
P

i=1

i=1

1
pi .

Now we have the following lemma.

Lemma 1.1 (Theorem 2.1 in [7]).
P r(X ≥ Λµ) ≤ e−p∗ µ(Λ−1−ln Λ) .

For any p1 , . . . , pn ∈ (0, 1] and any Λ ≥ 1,

Organization of Paper. The structure of this paper is as follows. In Section 2, we
define the model formally and present the FirstDiff[d] algorithm. We then analyze the
algorithm when m = n in Section 3 and give a proof that the total number of probes
used by FirstDiff[d] to place n balls is nd with high probability, while the maximum
log n
bin load is still upper bounded by log
0.66d + O(1) with high probability. We provide
the analysis of the algorithm when m > n in Section 4, namely that the number
of probes is on average d per ball with high probability and the maximum bin load
log log n
is upper bounded by m
n + 0.46d + O(log log log n) with probability close to 1. We
provide a matching lower bound for maximum bin load tight up to the O(log log log n)
term for algorithms with variable number of probes and FirstDiff[d] in particular in
Section 5. In Section 6, we give experimental evidence that our FirstDiff[d] algorithm
indeed results in a maximum load that is comparable to Left[d] when m = n. Finally,
we provide some concluding remarks and scope for future work in Section 7.

BALANCED ALLOCATION: PATIENCE IS NOT A VIRTUE

5

2. The FirstDiff[d] Algorithm. The idea behind this algorithm is to use probes
more efficiently. In the standard d-choice model, effort is wasted in some phases. For
example, early on in the distribution, most bins have size 0 and there is no need to
search before placing a ball. On the other hand, more effort in other phases would
lead to significant improvement. For example, if .9n balls have been distributed, most
bins already have size at least 1 and thus it is harder to avoid creating a bin of size
2. FirstDiff[d] takes this variation into account by probing until it finds a difference,
then making its decision.
This algorithm uses probes more efficiently than other, fixed-choice algorithms,
while still having a balanced outcome. Each ball probes at most 2Θ(d) bins (where
d ≥ 6 and by extension 2Θ(d) > 2) uniformly at random until it has found two bins
with different loads (or a bin with zero load) and places the ball in the least loaded of
the probed bins (or the zero loaded bin). If all 2Θ(d) probed bins are equally loaded,
the ball is placed (without loss of generality) in the last probed bin. The pseudocode
for FirstDiff[d] is below. Note that we use the Θ() to hide a constant value. The exact
values are different for m = n and m ≫ n and are 2/3 and 1/2.17 respectively.
Algorithm 1 FirstDiff[d]
(Assume 2Θ(d) > 2. The following algorithm is executed for each ball.)
1: Repeat 2Θ(d) times
2:
Probe a new bin chosen uniformly at random
3:
if The probed bin has zero load then
4:
Place the ball in the probed bin and exit
5:
if The probed bin has load that is different from those probed before then
6:
Place the ball in the least loaded bin (breaking ties arbitrarily) and exit
7: Place the ball in the last probed bin
As we can see, the manner in which a ball can be placed using FirstDiff[d] can be
classified as follows:
1. The first probe was made to a bin with load zero.
2. All probes were made to bins of the same load.
3. One or more probes were made to bins of larger load followed by a probe to
a bin of lesser load.
4. One or more probes were made to bins of lesser load followed by a probe to
a bin of larger load.
3. Analysis of FirstDiff[d] when m = n.
Theorem 3.1. Use FirstDiff[d], where maximum number of probes allowed per
ball is 22d/3 , to allocate n balls into n bins. The average number of probes required per
ball is at most d on expectation and w.h.p. Furthermore, the maximum load of any
log n
bin is at most log
n0 ),
0.66d + O(1) with high probability when d ≥ 4 and n ≥ max(2,
4
72e log n
≤ n12 .
where n0 is the smallest value of n such that for all n > n0 , 36 log n
5n
Proof. First, we show that an upper bound on the average number of probes per
ball is d on expectation and w.h.p. Subsequently, we show that the maximum load at
the end of placing all n balls is as desired w.h.p.

6

J. AUGUSTINE, W. K. MOSES JR., A. REDLICH, AND E. UPFAL

3.1. Proof of Number of Probes.

Lemma 3.2. The number of probes required to place m = n balls into n bins using
FirstDiff[d], where maximum number of probes allowed per ball is 22d/3 , is at most nd
on expectation and with high probability when d ≥ 4.

Proof. Let k be the maximum number of probes allowed to be used by FirstDiff[d]
per ball, i.e. k = 22d/3 . We show that the total number of probes required to place
all balls does not exceed 1.5n log k w.h.p. and thus nd probes are required to place
all balls.
Let the balls be indexed from 1 to n in the order in which they are placed. Our
analysis proceeds in two phases. For a value of T that will be fixed subsequently, the
first T + 1 balls are analyzed in the first phase and remaining balls are analyzed in
the second. Consider the ball indexed by t, 1 ≤ t ≤ n. Let Xt be the random variable
denoting the number of probes it takes for FirstDiff[d] to place ball t.
Phase One: t ≤ T + 1. We couple FirstDiff[d] with the related process that probes
until it finds a difference in bin loads or runs out of probes, without treating empty
bins as special; in other words, the FirstDiff[d] algorithm without lines 3 and 4. One
additional rule for the related process is that if an empty bin is probed first, then after
the process finishes probing, the ball will be placed in that first probed bin, i.e. the
empty bin. Note that this is a valid coupling; if an empty bin is probed then under
both FirstDiff[d] and this process the ball is placed in an empty bin, and if no empty
bin is probed the two processes are exactly the same. Let Yt be the number of probes
required by this related process to place ball t in the configuration where there are
t − 1 bins of load 1 and n − t + 1 bins of load 0. Notice that for any configuration
of balls in bins, Xt ≤ Yt ; furthermore, the configuration after placement under both
FirstDiff[d] and this new process is the same. You can see this by a simple sequence
of couplings.
First, choose some arbitrary configuration with nαi bins of size i for i = 0, 1, 2, . . ..
That configuration will be probed until bins of two different sizes are discovered,
i.e. until the set probed
Pn intersects two distinct αi and αj . Couple this with the
configuration that has i=1 nαi bins of size 1 and the rest of size 0. This configuration
requires more probes than the original configuration; it continues until the set probed
intersects α0 and α6=0 . Second, note that the configuration with t − 1 bins of size 1
and n − t + 1 bins of size 0 requires even more probes than this one. This is because
restricting the bins to size 1 can only decrease the number of empty bins. Finally,
note that the ball’s placement under either FirstDiff[d] or this new process leads to
the same configuration at time t + 1 (up to isomorphism); if FirstDiff[d] places a ball
in an empty bin, so does this process.
We first derive the expected value of Yt . The expected number of probes used
by FirstDiff[d] is upper bounded by the expected number of probes until a size-0 bin
appears, i.e. the expected number of probes used by the FirstDiff[d] algorithm without
line 1. This is of course n/(n − t + 1). The overall expected number of probes for the

BALANCED ALLOCATION: PATIENCE IS NOT A VIRTUE

7

first T + 1 steps is
E[Y ] = E[

T
+1
X

Yt ]

t=1

=

T
+1
X

E[Yt ]

t=1

≤

T
+1
X
t=1

=n

n
n−t+1

n
X
1
i

i=n−T

∼ n(log n − log(n − T ))


n
= n log
.
n−T
Now we will find T such that the expected number of probes in phase one, E[Y ],
is n log k, i.e.


n
= n log k.
n log
n−T
Solving, we get T = n(1 − 1/k). Now, recall that we want a high probability bound
on the number of probes required to place each ball in Phase One when running
Pn(1−1/k)
FirstDiff[d], i.e.
Xt . Recall that Xt ≤ Yt , and as such a high probability
t=0
Pn(1−1/k)
Yt suffices. We can now use Lemma 1.1 with Λ = 1.01, µ =
bound on t=0
n log k, and p∗ = k1 .




n(1−1/k)
n(1−1/k)
X
X
Pr 
Xt ≥ 1.01n log k  ≤ P r 
Yt ≥ 1.01n log k 
t=0

t=0

≤e

1
·(n log k)·(1.01−1−ln 1.01)
−k

 
1
since k << n
≤O
n
Phase Two: t > T + 1. Rather than analyzing in detail, we use the fact that the
number of probes for each ball is bounded by k, i.e. Xt ≤ k, ∀t > T + 1. So the
number of probes overall in this phase is at most
k(n − T − 1) = k(n − n(1 − 1/k) − 1) = n − k.
So the total number of probes w.h.p. is 1.01n log k + n − k ≤ 1.5n log k (when
k = 22d/3 and d ≥ 4). When k = 22d/3 , an upper bound on the number of probes to
place all n balls is nd probes on expectation and w.h.p., as desired.
3.2. Proof of Maximum Load.
Lemma 3.3. The maximum load in any bin after using FirstDiff[d], where maximum number of probes allowed per ball is 22d/3 , to allocate n balls into n bins is at
log n
n ≥ max(2, n0 ), where n0
most log
0.66d + O(1) with high probability when d ≥ 4 and 
4
log n
is the smallest value of n such that for all n > n0 , 36 log n 72e5n
≤ n12 .

8

J. AUGUSTINE, W. K. MOSES JR., A. REDLICH, AND E. UPFAL

Proof. While the proof follows along the lines of the standard layered induction
argument [8, 14], we have to make a few non-trivial adaptations to fit our context
where the number of probes is not fixed.
Let k be the maximum number of probes allowed to be used by FirstDiff[d] per
ball, i.e. k = 22d/3 . Define vi as the fraction of bins of load at least i after n balls are
placed. Define ui as the number of balls of height at least i after n balls are placed.
It is clear that vi ∗ n ≤ ui .
We wish to show that the Pr(Max. load ≥ logloglogk n + γ) ≤ n1c for some constants
γ ≥ 1 and c ≥ 1. Set i∗ = logloglogk n + 11 and γ = 15. Equivalently, we wish to show
that Pr(vi∗ +4 > 0) ≤ n1c for some constant c ≥ 1.
In order to aid us in this proof, let us define a non-increasing series of numbers
1
.
β11 , β12 , . . . , βi∗ as upper bounds on v11 , v12 , . . . vi∗ . Let us set β11 = 11
Now,
Pr(vi∗ +4 > 0) = Pr(vi∗ +4 > 0|vi∗ ≤ βi∗ )Pr(vi∗ ≤ βi∗ )
+ Pr(vi∗ +4 > 0|vi∗ > βi∗ )Pr(vi∗ > βi∗ )
≤ Pr(vi∗ +4 > 0|vi∗ ≤ βi∗ ) + Pr(vi∗ > βi∗ )
= Pr(vi∗ +4 > 0|vi∗ ≤ βi∗ )
+ Pr(vi∗ > βi∗ |vi∗ −1 ≤ βi∗ −1 )Pr(vi∗ −1 ≤ βi∗ −1 )
+ Pr(vi∗ > βi∗ |vi∗ −1 > βi∗ −1 )Pr(vi∗ −1 > βi∗ −1 )
≤ Pr(vi∗ +4 > 0|vi∗ ≤ βi∗ )
∗

(1)

+

i
X

Pr(vi > βi |vi−1 ≤ βi−1 ) + Pr(v11 > β11 )

i=12

Here, Pr(v11 > β11 ) = 0. It remains to find upper bounds for the remaining two
terms in the above equation.
We now derive a recursive relationship between the βi ’s for i ≥ 11. βi+1 acts as
an upper bound for the fraction of bins of height at least i + 1 after n balls are placed.
In order for a ball placed to land up at height at least i + 1, one of 3 conditions must
occur:
• All k probes are made to bins of height at least i.
• Several probes are made to bins of height at least i and one is made to a bin
of height at least i + 1.
• One probe is made to a bin of height at least i and several probes are made
to bins of height at least i + 1.
Thus the probability that a ball is placed at height at least i + 1, conditioning on
vj ≤ βj for j ≤ i + 1 at that time, is

≤ βik + βi βi+1 1 + βi + βi2 + . . . + βik−2

k−2
2
+ . . . + βi+1
+ βi βi+1 1 + βi+1 + βi+1
!
k−1
1 − βi+1
1 − βik−1
k
+
≤ βi + βi βi+1
1 − βi
1 − βi+1


1
≤ βik + β11 βi+1 2 ∗
1 − β11
2β
i+1
≤ βik +
10

BALANCED ALLOCATION: PATIENCE IS NOT A VIRTUE

9

Let vi+1 (t) be the fraction of bins with load at least i + 1 after the 1 ≤ t ≤ n ball
is placed in a bin.
Let t∗ = min[arg mint vi+1 (t) > βi+1 , n], i.e. t∗ is the first t such that vi+1 (t) >
βi+1 or n if there is no such t. The probability that t∗ < n is bounded by the
i+1
) is greater than βi+1 n.
probability that a binomial random variable B(n, βik + 2β10
Fix βi+1 =

10 k
3 βi

≥

2n(βik +
n

2βi+1
10

)

. Then using a Chernoff bound, we can say that

with high probability, t∗ = n or vi+1 ≤ βi+1 , so long as e
some constant c ≥ 1.


n
, e−
Now, so long as βi+1 ≥ 18 log
n
18 log n
. This
the value of βi dips below
n
log β11 = − log 11 and log βi+1 = log( 10
3 )

log βi∗ = log



10
3



βik +



2βi+1
βik +
10
−
3

= O( n1c ) for

2βi+1
10
3

= O( n1c ). Notice that at i = i∗ ,
can be seen by solving the recurrence with
+ k log βi .

(1 + k + k 2 + . . . + k logk log n−1 )

+ k logk logn (− log 11)
   log log n

10
k k
−1
= log
− (log n)(log 11)
3
k−1

  
10
− log 11
≤ (log n) log
3

≤ −1.7 log n
Therefore, as it is, βi∗ ≤
n
, we set
βi at least at 18 log
n
(2)

1
n1.7

≤

18 log n
n

βi+1 = max



when n ≥ 2. In order to keep the value of

10 k 18 log n
β ,
3 i
n



With the values of βi defined, we proceed to bound Pr(vi > βi |vi−1 ≤ βi−1 ), ∀12 ≤
i ≤ i∗ . For a given i,
Pr(vi > βi |vi−1 ≤ βi−1 ) = Pr(nvi > nβi |vi−1 ≤ βi−1 )
≤ Pr(ui > nβi |vi−1 ≤ βi−1 )
We upper bound the above inequality using the following idea. Let Yr be an
indicator variable set to 1 when the following 2 conditions are met: (i) the rth ball
placed is of height at least i and (ii) vi−1 ≤ βi−1 . Yr is set to 0 otherwise. Now
2
k
βi ≤
for all 1 ≤ r ≤ n, the probability that Yr = 1 is upper bounded by βi−1
+ 10
βi
3
2
β
+
β
≤
.
Therefore,
the
probability
that
the
number
of
balls
of
height
at
10 i
10 i
2
βi
least i exceeds βi is upper bounded by Pr(B(n, 2 ) > nβi ), where B(·, ·) is a binomial
random variable with given parameters.
µδ2
Recall the Chernoff bound, for 0 < δ ≤ 1, Pr(X ≥ (1 + δ)µ) ≤ e− 3 , where X is
the sum of independent Poisson trials and µ is the expectation of X. If we set δ = 1,
then we have

10

J. AUGUSTINE, W. K. MOSES JR., A. REDLICH, AND E. UPFAL

βi
) > nβi )
2
n · ( β2i )
−
3
≤e

Pr(vi > βi |vi−1 ≤ βi−1 ) ≤ Pr(B(n,

n
n · ( 18 log
)
n
18 log n
6
, ∀i ≤ i∗ )
≤e
(since βi ≥
n
1
≤ 3
n
−

Thus we have
∗

i
X

Pr(vj > βj |vj−1 ≤ βj−1 ) ≤

j=12

log log n
n3

∗

(3)

=⇒

i
X

j=l+1

Pr(vj > βj |vj−1 ≤ βj−1 ) ≤

1
(since n ≥ 2)
2n2

Finally, we need to upper bound Pr(vi∗ +4 > 0|vi∗ ≤ βi∗ ). Consider a particular bin
of load at least i∗ . Now the probability that a ball will fall into that bin is
!!
1
1
+ 2βi∗ +1
≤ · βik−1
∗
n
1 − βik∗ +1



1
1
≤ · βik−1
+ 2βi∗ +1
∗
n
1 − β11


22
1
+ βi∗ (since βi is a non-increasing function)
≤ · βik−1
∗
n
10
1 32
≤ ·
· βi∗ (since k ≥ 2 and βi∗ ≤ 1)
n 10
Now, we upper bound the probability that 4 balls fall into a given bin of load at
least i∗ and then use a union bound over all the bins of load at least i∗ to show that
the probability that the fraction of bins of load at least βi∗ +4 exceeds 0 is negligible.
First, the probability that 4 balls fall into a given bin of load at least βi∗ is
1 32
≤ Pr(B(n, ( ·
∗ βi∗ )) ≥ 4)
n 10
4
 
n
1 32
·
· βi∗
≤
n 10
4
 4


1
1 32
·
· βi∗ ·
≤ e·n·
n 10
4
4

32 eβi∗
·
≤
10
4
Taking the union bound across all possible βi∗ n bins, we have the following inequality

BALANCED ALLOCATION: PATIENCE IS NOT A VIRTUE

Pr(vi∗ +4 > 0|vi∗
=⇒ Pr(vi∗ +4 > 0|vi∗
=⇒ Pr(vi∗ +4 > 0|vi∗

(4)

11

4
32 eβi∗
≤ βi∗ ) ≤ (βi∗ n) ·
·
10
4
4

32 18e log n
·
≤ βi∗ ) ≤ (18 log n) ·
10
4n
1
≤ βi∗ ) ≤
(since n ≥ n0 )
2n2


Putting together equations 1, 3, and 4, we get
1
1
+ 2
2n2
2n
1
≤ 2
n

Pr(vi∗ +4 > 0) ≤

Thus


log log n
Pr Max. Load ≥
+ 15 = Pr(vi∗ +4 > 0)
log k
1
≤ 2
n
From Lemma 3.2 and Lemma 3.3, we immediately arrive at Theorem 3.1.
4. Analysis of FirstDiff[d] when m ≫ n.
Theorem 4.1. Use FirstDiff[d], where maximum number of probes allowed per
ball is 2d/2.17 , to allocate m balls into n bins. When m ≥ 72(nλ log n + n) where λ
is taken from Lemma 4.5, n ≥ n0 where n0 is the smallest value of n that satisfies
0.00332n(λ log n + 1)d/2d/2.17 ≥ log n, and d ≥ 6, it takes at most d probes on average
to place every ball on expectation and with high probability. Furthermore, for an
absolute constant c,

Pr Max. load of any bin >

m
n

+

log log n
0.46d

+ c log log log n ≤ c(log log n)−4 .

Proof. First we show that the average number of probes per ball is at most d on
expectation and w.h.p. We then show the maximum load bound holds w.h.p.
4.1. Proof of Number of Probes.
Remark: The earlier version of this paper [1] had a different proof in this subsection.
The overall idea of overcounting the number of probes remains the same but the
specific argument of how to justify and go about such an overcounting is changed and
cleaner now. More specifically, we have replaced Lemmas 4.2, 4.3, and 4.4 with the
argument that follows the header “Overcounting method” and concludes at the header
“Expectation bound”. Also note that Lemma 4.6 from our earlier version is no longer
required due to the way we’ve constructed our argument.
The main difficulty with analyzing the number of probes comes from the fact that
the number of probes needed for each ball depends on where each of the previous balls
were placed. Intuitively, if all the previous balls were placed such that each bin has
the same number of balls, the number of probes will be 2d/2.17 . On the other hand, if a
significant number of bins are at different load levels, then, the ball will be placed with
very few probes. One might hope to prove that the system always displays a variety of

12

J. AUGUSTINE, W. K. MOSES JR., A. REDLICH, AND E. UPFAL

loads, but unfortunately, the system (as we verified experimentally) oscillates between
being very evenly loaded and otherwise. Therefore, we have to take a slightly more
nuanced approach that takes into account that the number of probes cycles between
high (i.e. as high as 2d/2.17 ) when the loads are even and as low as 2 when there is
more variety in the load.
Lemma 4.2. When m ≥ 72(nλ log n + n) where λ is taken from Lemma 4.5, n ≥
n0 where n0 is the smallest value of n that satisfies 0.00332n(λ log n + 1)d/2d/2.17 ≥
log n, and d ≥ 6, using FirstDiff[d], where maximum number of probes allowed per ball
is 2d/2.17 , takes at most md probes on expectation and with high probability to place
the m balls in n bins.
Proof. Let the maximum number of probes allowed per ball using FirstDiff[d] be
k, i.e. k = 2d/2.17 . Throughout this proof, we will assume that the maximum load
of any bin is at most m/n + λ log n, which holds with high probability owing to
Lemma 4.5. The low probability event that the maximum load exceeds m/n + λ log n
will contribute very little to the overall number of probes because the probability
that any ball exceeds a height of m/n + λ log n will be an arbitrarily small inverse
polynomial in n. Therefore, such a ball will contribute o(1) probes to the overall
number of probes even when we liberally account k probes for each such ball (as long
as k ≪ n). Let m balls be placed into n bins; we assume m ≥ 72(nλ log n + n).
In order to prove the lemma, we proceed in three stages. In the first stage, we
consider an arbitrary sequence of placing m balls into the n bins. We develop a
method that allows us to overcount the number of probes required to place the ball at
each step of this placement. In the second stage, we proceed to calculate the expected
number of probes required to place the balls. Finally in the third stage, we show how
to get a high probability bound on the number of probes required to place each ball.
Overcounting method
First, we couple the process of FirstDiff[d] with a similar process where the zero bin
condition to place balls is not used. In this similar process, if a zero bin is probed first,
more probes are made until either a bin with a different load is probed or until all k
probes are made. Then, the ball is placed in the first bin probed (the zero bin). In
case the first bin probed is not a zero bin, then the process acts exactly as FirstDiff[d].
It is clear that this process will take more probes than FirstDiff[d] while still making
the same placements as FirstDiff[d]. Thus, any upper bounds on number of probes
obtained for this process apply to FirstDiff[d]. For the remainder of this proof, we
analyze this process.
Now we describe the method we use to overcount the number of probes. Consider
an arbitrary sequence of placing m balls into n bins. We will describe a method
to associate each configuration that arises from such a placement with a “canonical”
configuration, which we define later in this proof. Each such canonical configuration
requires more probes to place the ball than the actual configuration. We ensure
that the mapping of actual configurations to canonical configurations is a one-to-one
mapping. Thus, by counting the number of probes required to place a ball in every
possible canonical configuration, we overcount the number of probes required to place
every ball.
Imagine coupling according to probe sequences. That is, consider all [n]k × [n]k ×
. . . × [n]k = [n]km possible sequences of probes. Each timestep corresponds to a
particular length-k sequence of bin labels [n], which direct the bins to be probed.
Note that the probe sequences are each equally likely, and that they fully determine

BALANCED ALLOCATION: PATIENCE IS NOT A VIRTUE

13

the placement.
For each probe sequence S, let X S be the sequence of configurations generated by
S. Let xS be the sequence of numbers-of-probes-used at each timestep of X S . (Note
that S gives k potential probes at each timestep, but the entries of xS are often less
than k, as often the ball is placed without using the maximum number of probes.)
For convenience, we drop the superscript S subsequently and use X and x to refer to
the vectors.
Now we give a few definitions. Consider a particular bin with balls placed in
it, one on top of another. If exactly ℓ − 1 balls are placed below a given ball, we
say that ball is at height ℓ or level ℓ. Balls of the same height are said to be of the
same level. We say a level contains b balls if there are b balls at that level. A level
containing n balls is said to be complete. A level containing at least one ball but less
than n balls is said to be incomplete. For a given configuration, consider the highest
complete level ℓ. For the given configuration, we define a plateau as any level ≥ ℓ
with at least one ball at that level. Intuitively, the plateaus for the configuration are
the highest complete level and any higher incomplete levels. Notice that it is possible
that a given configuration may only have one plateau when there are no incomplete
levels. Further, notice that for a given configuration if two plateaus exist at levels ℓ
and ℓ + 2 with number of balls b1 and b2 , it implies that there exists a plateau at level
ℓ + 1 with number of balls in [b2 , b1 ].
Consider a particular configuration Xi in the sequence X. Call its number of
plateaus p. Consider the plateaus in increasing order of their levels and call them
ℓ1 , ℓ2 , . . . ℓp . Call the number of balls at each level ℓi , bi .
We now define the canonical configuration Cℓ,b . This is the configuration with no
balls at level greater than ℓ, b balls at level ℓ, and n balls at every level less than ℓ.
We will associate each configuration Xi with a set of canonical configurations Ci .
For each plateau of Xi at level ℓj , include the canonical configuration Cℓj ,bj in the
set.
Note that for any probe sequence (not just the specific sequence S), the number of
probes utilized by Xi (e.g. xi for the sequence S) is less than or equal to the number
of probes utilized by any of the configurations in Ci . Therefore the expected number
of probes used to place a ball in configuration Xi is less than or equal to the expected
number of probes used to place a ball in any of the configurations in Ci . We now
describe a way to select one particular configuration out of Ci to associate with each
configuration Xi . We choose this configuration such that the mapping between all
configurations Xi , 1 ≤ i ≤ m, and the selected canonical configurations will be a oneto-one mapping. Furthermore, we show that every selected canonical configurations
will be unique from the others and thus the set of all selected canonical configurations
will not be a multiset. Thus, by counting the number of probes required to place balls
in every possible canonical configuration, we overcount the number of probes required
to place balls in any sequence S.
Look at the canonical configurations associated with configurations Xi , 1 ≤ i ≤ m
over some entire sequence. Let C0 refer to the set of canonical configurations before
any ball is placed and let it be the empty set. The set of canonical configurations Ci−1
differs from Ci in at most three configurations. Consider that i − 1 balls have been
placed and there are now p plateaus with levels ℓi , 1 ≤ i ≤ p and corresponding bi ,
1 ≤ i ≤ p values.
• If the ith ball is placed at level ℓj , level ℓj+1 exists (≥ 1 balls are present at
level ℓj+1 ), and bj+1 6= n − 1, then Ci = (Ci−1 \{Cℓj+1 ,bj+1 }) ∪ {Cℓj+1 ,bj+1 +1 }.
• If level ℓj+1 exists and bj+1 = n − 1, then Ci = (Ci−1 \{Cℓj ,bj , Cℓj+1 ,bj+1 }) ∪

14

J. AUGUSTINE, W. K. MOSES JR., A. REDLICH, AND E. UPFAL

{Cℓj+1 ,n }.
• If level ℓj+1 does not exist, then Ci = Ci−1 ∪ {Cℓj +1,1 }.
Notice that in every scenario, there is exactly one configuration that is added to
Ci−1 to get Ci . We denote the newly-added configuration as the selected canonical
configuration of Ci .
Now, for a given sequence of configurations Xi , 1 ≤ i ≤ m it is clear that each
selected canonical configuration is uniquely chosen. We show in the following lemma,
Lemma 4.3, that every selected canonical configuration in the sequence is unique and
different from the other selected canonical configurations. In other words, the set of
selected canonical configurations will not be a multiset. Furthermore, it has earlier
been established that for any configuration and one of its canonical configurations, it
takes at least as many probes to place a ball in the latter as it does in the former.
Thus, by calculating the S
number of probes it would take to place balls in all possible
m
canonical configurations i=1 Ci , we can overcount the number of probes required to
place all balls into bins.
Lemma 4.3. The set of selected canonical configurations for any sequence of configurations Xi , 1 ≤ i ≤ m will not be a multiset.
Proof. Consider an arbitrary sequence and within it an arbitrary configuration Xi
for some 1 ≤ i ≤ m. To reach this configuration, a ball was placed previously in some
level ℓ − 1 and extended level ℓ from b balls to b + 1 balls, 0 ≤ b ≤ n − 1. The selected
canonical configuration for Xi will be Cℓ,b+1 . Since balls can only be added and never
deleted, once a level is extended to some b + 1 number of balls, placing another ball
can never extend that same level to b + 1 balls. That level can only be henceforth
extended to a larger number of balls up to n balls. Thus a given configuration Cℓ,b+1
will never appear twice in the set of selected canonical configurations.

Expectation bound
As mentioned earlier, we assume the maximum load of any bin is m/n+ λ log n. Thus,
for any given sequence of placements, the final configuration never has any balls at
level m/n + λ log n + 1. Thus, when calculating the number of probes taken to place
all balls, we need only consider the number of probes required to place a ball in every
canonical configuration Cℓ,b , 0 ≤ ℓ ≤ m/n + λ log n, 0 ≤ b ≤ n − 1.
For a given canonical configuration Cℓ,b let Yℓ,b be a random variable denoting
the number of probes required to place the ball using FirstDiff[d] without the zero
bin condition. Let Y be a random variable denoting the total number of probes
required to place a ball in each of the possible canonical configurations. Thus Y =
Pm/n+λ log n Pn−1
ℓ=1
b=0 Yℓ,b .
For a given configuration Cℓ,b , a ball is placed when either it first hits bins of level
ℓ several times and then a bin of level ℓ − 1, it hits bins of level ℓ − 1 several times and
then a bin of level ℓ, or it makes k probes. Thus, using geometric random variables,
we see that E[Yℓ,b ] = min(b/(n − b) + (n − b)/b, k). For the first nk and last nk − 1
canonical configurations for a given level, let us give away the maximum number of
probes, i.e. Yℓ,b = k for any ℓ and for 0 ≤ b ≤ nk − 1 and n − nk + 1 ≤ b ≤ n − 1.
We now want to calculate the expected number of probes for the middle canonical
configurations.
Therefore

15

BALANCED ALLOCATION: PATIENCE IS NOT A VIRTUE

m
n +λ log n

n− n
k

X

X

b= n
k

ℓ=0


n
X n − b n−
Xk b

E[Yℓ,b ] =
+ λ log n + 1 
+
n
b
n
n n − b
b= k
b= k


n
n
n−
n− n
n− n
n−

m
Xk 1
Xk b
Xk 1
Xk n − b

+ λ log n + 1 n
−
+n
−
=
n
n b
n b
n n − b
n n − b
b= k
b= k
b= k
b= k


n
n
n−
k

m
Xk 1
X
4n 
1
+ λ log n + 1 n
+n
− 2n +
=
n
b
y
k
b= n
y=n− n
k
k

  n
n− k
m

X 1
2
=
+ λ log n + 1 2n 
− 1 + 
n
b
k
n
b= k

 
n
2
n
− log
−1+
≈ 2 (m + nλ log n + n) log n −
k
k
k


2
= 2 (m + nλ log n + n) log(k − 1) − 1 +
k
m





n− n
k

High probability bound
Now, we may apply Lemma 1.1 with Λ = 1.01, µ taken from above, and p∗ = k1 .
m
n

Pr 
≤e

+λ log n n− n
k

X
ℓ=0

X

b= n
k

1
·2(m+nλ log
−k

≤O

Yℓ,b > 2.02(m + nλ log n + n)(log(k − 1) − 1 +

2
n+n)(log(k−1)−1+ k
)·(1.01−1−ln 1.01)



2 
)
k

 
1
(since k > 2 and n ≥ n0 )
n

Therefore, with high probability, the total number of probes
m
n +λ log n

Y =

X

n−1
X

X

X

ℓ=0

Yℓ,b

b=0

m
n
n +λ log n k −1

≤

ℓ=0

b=0

m
n +λ log

Yℓ,b +

X
ℓ=0

n n− n
k

X

m
n +λ log n

(Yℓ,b ) +

b= n
k

X
ℓ=0

n−1
X

Yℓ,b

b=n− n
k +1

 

 n
 n

m
2
+
+ λ log n + 1 k + 2.02 (m + nλ log n + n) log(k − 1) − 1 +
+ λ log n + 1 k
−1
n
k
k
n
k
≤ 2.14(m + nλ log n + n) log k
≤

m

≤ 2.17m log k (since m ≥ 72(nλ log n + n))
Thus when m balls are placed into n bins, an upper bound on both the expected
total probes and the total probes with high probability is 2.17m log k. Therefore on
expectation and with high probability, the number of probes per ball is at most d
since k = 2d/2.17 .

16

J. AUGUSTINE, W. K. MOSES JR., A. REDLICH, AND E. UPFAL

4.2. Proof of Maximum Load.
Lemma 4.4. Use FirstDiff[d], where maximum number of probes allowed per ball
is 2d/2.17 , to allocate m balls into n bins. For any m, for an absolute constant c,
Pr Max. load of any bin >

m
n

+

log log n
0.46d

+ c log log log n ≤ c(log log n)−4 .

Proof. This proof follows along the lines of that of Theorem 2 from [14]. In order
to prove Lemma 4.4, we make use of a theorem from [10] which gives us an initial,
loose, bound on the gap Gt between the maximum load and average load for an
arbitrary m. We then use a lemma to tighten this gap. We use one final lemma to
show that if this bound on the gap holds after all m balls are placed, then it will hold
at any time prior to that.
First, we establish some notation. Let k be the maximum number of probes
permitted to be made per ball by FirstDiff[d], i.e. k = 2d/2.17 . After placing nt
balls, let us define the load vector X t as representing the difference between the load
of each bin and the average load (as in [3, 10]). Without loss of generality we order the individual values of the vector in non-increasing order of load difference, i.e.
X1t ≥ X2t ≥ . . . ≥ Xnt . So Xit is the load in the ith most loaded bin minus t. For
convenience, denote X1t (i.e. the gap between the heaviest load and the average) as Gt .
Initial bound on gap
We now give an upper bound for the gap between the maximum loaded bin and the
average load after placing some arbitrary number of balls nt. In other words, we show
Pr(Gt ≥ x) is negligible for some x. This x will be our initial bound on the gap Gt .
Lemma 4.5. For arbitrary constant c, after placing an arbitrary nt balls into bins
n
bn
under FirstDiff[d], there exist some constants a and b such that Pr(Gt ≥ c log
a ) ≤ nc .
1
t
Thus there exists a constant λ that gives Pr(G ≥ λ log n) ≤ nc for a desired c value.
In order to prove Lemma 4.5, we need two additional facts. The first is the following
basic observation:
Lemma 4.6. FirstDiff[d] is majorized by Greedy[2] when d ≥ 2.
Proof. Let the load vectors for FirstDiff[d] and Greedy[2] after t balls have been
placed using the respective algorithms be ut and v t respectively. Now we follow
the standard coupling argument (refer to Section 5 in [3] for an example). Couple
FirstDiff[d] with Greedy[2] by letting the bins probed by Greedy[2] be the first 2 bins
probed by FirstDiff[d]. We know that FirstDiff[d] makes at least 2 probes when d ≥ 2.
It is clear that FirstDiff[d] will always place a ball in a bin with load less than or equal
to that of the bin chosen by Greedy[2]. This ensures that if majorization was preserved
prior to the placement of the ball, then the new load vectors will continue to preserve
majorization; again, see [3] for a detailed example. Initially, u0 is majorized by v 0
since both vectors are the same. Using induction, it can be seen that if ut is majorized
by v t at the time the tth ball was placed, it would continue to be majorized at time
t + 1, 0 ≤ t ≤ m − 1. Therefore, FirstDiff[d] is majorized by Greedy[2] when d ≥ 2.
The other fact is the following theorem about Greedy[d] taken from [10] (used
similarly in [14] as Theorem 3).
Theorem 4.7. [10] Let Y t be the load vector generated by Greedy[d]. Then for
every d > 1 there exist positive constants
a and

 b such that for all n and all t,
P a|Y t |
E
e i
≤ bn.
i

We are now ready to prove Lemma 4.5.

17

BALANCED ALLOCATION: PATIENCE IS NOT A VIRTUE

Proof of Lemma 4.5.. Combining Lemma 4.6 with Theorem 4.7 tells us that, if
X t is the load vector generated by FirstDiff[d],
!
X
a|Xit |
≤ bn.
e
E
i

Clearly, Pr(Gt ≥

c log n
a )

Pr(Gt ≥

t

= Pr(eaG ≥ nc ). Observe that

P

t

t

ea|Xi | ≥ eaG . Then

i

t
c log n
) = Pr(eaG ≥ nc )
a
t
E[eaG ]
≤
(by Markov’s inequality)
nc
bn
≤ c (by Theorem 4.7 and Lemma 4.6)
n

and the theorem is proved.
Reducing the gap
Lemma 4.5 gives an initial bound on Gt of order log n. The next step is to reduce it
to our desired gap value. For this reduction, we use a modified version of Lemma 2
from [14], with a similar but more involved proof. We now give the modified lemma
and prove it.
Lemma 4.8. For every k, there exists a universal constant γ such that the fol1
lowing holds: for any t, ℓ, L such that 1 ≤ ℓ ≤ L ≤ n 4 , L = Ω(log log n) and
1
t
Pr(G ≥ L) ≤ 2 ,
3
+ n12 ,
Pr(Gt+L ≥ logloglogk n + ℓ + γ) ≤ Pr(Gt ≥ L) + 16bL
eaℓ
where a and b are the constants from Theorem 4.7.
Proof. This proof consists of many steps. We first observe that Lemma 4.8 follows directly from Lemma 4.5 for sufficiently small n. We then use layered induction
to bound the proportion of bins of each size for larger n. This in turn allows us to
compute our desired bound on the probability of a large gap occurring.
Proof of
Define n1
Define n2

Lemma 4.8 for smaller values of n
to be the minimum value of n such that L ≥ 2 (recall L = Ω(log log n)).
tobe the minimum
value of n such that

1

(18 log n) ∗

4

18en 4 log n
n

≤

1
2n2 .

Define n3 to be the minimum value of n such that

n ≥ 54 log n. Define absolute constant n0 = max(n1 , n2 , n3 ).
Notice that, when n ≤ n0 , Lemma 4.5 implies that Lemma 4.8 holds with γ =
O(log n0 ). If n ≤ n0 , then
Pr(Gt+ℓ ≥ log log n + ℓ + γ) ≤ Pr(Gt+L ≥ γ).
Consider the right hand side of Lemma 4.8.
Pr(Gt ≥ L) +

1
16bL3
+ 2 ≥ n−2 ,
exp(aℓ) n

so it will be sufficient to prove the inequality
Pr(Gt+L ≥ γ) ≤ n−2 .

18

J. AUGUSTINE, W. K. MOSES JR., A. REDLICH, AND E. UPFAL

Since there are no conditions on t in Lemma 4.5, we may rewrite it as
Pr(Gt+L ≥ λ log n) ≤ n−c .
Let c = 2 and compute the constant λ accordingly. Set γ = λ log n0 ≥ λ log n. Then
n−2 ≥ Pr(Gt+L ≥ λ log n) ≥ Pr(Gt+L ≥ γ),
and we are done.
Rewriting initial probability inequality
We now prove Lemma 4.8 assuming n > n0 . Start by rewriting the probability in
terms of Pr(Gt ≥ L).
Pr(Gt+L ≥

log log n
log log n
+ ℓ + γ) = Pr(Gt+L ≥
+ ℓ + γ|Gt ≥ L)Pr(Gt ≥ L)
log k
log k
log log n
+ Pr(Gt+L ≥
+ ℓ + γ|Gt < L)Pr(Gt < L)
log k
log log n
≤ Pr(Gt ≥ L) + Pr(Gt+L ≥
+ ℓ + γ|Gt < L)
log k

To prove the theorem, then, it is enough to to show that
3
1
Pr(Gt+L ≥ logloglogk n + ℓ + γ|Gt < L) ≤ 16bL
eaℓ + n2 .
Bins’ loads
Define vi to be the fraction of bins of load at least t + L + i after (t + L)n balls are
placed. Let us set i∗ = logloglogk n + ℓ and set γ = 4. Using this new notation, we want to
show that Pr(Gt+L ≥ i∗ + 4|Gt < L) is negligible. This can be thought of as showing
that the probability of the fraction of bins of load at least t + L + i∗ + 4 exceeding 0
after (t + L)n balls are placed, conditioned on the event that Gt < L, is negligible.
Suppose we have a non-increasing series of numbers β0 , β1 , . . . , βi , . . . that are
upper bounds for v0 , v1 , . . . , vi , . . .. Then we know that
Pr(vi∗ +4 > 0) = Pr(vi∗ +4 > 0|vi∗ ≤ βi∗ )Pr(vi∗ ≤ βi∗ ) + Pr(vi∗ +4 > 0|vi∗ > βi∗ )Pr(vi∗ > βi∗ )
≤ Pr(vi∗ +4 > 0|vi∗ ≤ βi∗ ) + Pr(vi∗ > βi∗ )
∗

i
X

≤ Pr(vi∗ +4 > 0|vi∗ ≤ βi∗ ) +

Pr(vj > βj |vj−1 ≤ βj−1 ) + Pr(vℓ > βℓ ) (successively expanding

j=ℓ+1

and bounding the Pr(vi∗ > βi∗ ) term and its derivatives)
Conditioning both sides on Gt < L, we have
Pr(vi∗ +4 > 0|Gt < L) ≤ Pr(vi∗ +4 > 0|vi∗ ≤ βi∗ , Gt < L)
∗

+

i
X

Pr(vi > βi |vi−1 ≤ βi−1 , Gt < L)

i=ℓ+1

(5)

+ Pr(vℓ > βℓ |Gt < L)

It remains to find appropriate βi values. We use a layered induction approach to show
that vi ’s don’t exceed the corresponding βi ’s with high probability. This then allows

19

BALANCED ALLOCATION: PATIENCE IS NOT A VIRTUE

us to upper bound each of the 3 components of equation 5.
Base case of layered induction
In order to use layered induction, we need a base case. Let us set βℓ =
in the statement of the theorem. Now,

1
8L3 ,

for the ℓ

T
Pr((vℓ > 8L1 3 ) (Gt < L))
Pr(Gt < L)
1
1
≤ 2 · Pr(vℓ >
) (since, by the statement of the theorem Pr(Gt < L) ≥ )
3
8L
2
8bL3
≤ 2 · aℓ (applying Markov’s inequality and using Theorem 4.7)
e
16bL3
≤ aℓ
e

Pr(vℓ > βℓ |Gt < L) =

Therefore we have the third term of Equation 5 bounded:
(6)

Pr(vℓ > βℓ |Gt < L) ≤

16bL3
eaℓ

Recurrence relation for layered induction
We now define the remaining βi values recursively. Note that for all i ≥ ℓ, βi ≤ βℓ .
Let ui be defined as the number of balls of height at least t + L + i after (L + t)n balls
are placed.
Initially there were nt balls in the system. Then we threw another nL balls into
the system. Remember that t+L is the average load of a bin after nL balls are further
placed. Because we condition on Gt < L, we have it that any ball of height i, i ≥ 1,
must have been one of the nL balls placed.
Therefore the number of bins of load t + L + i + 1 after (t + L)n balls are placed is
upper bounded by the number of balls of height at least t+ L + i + 1. So vi+1 n ≤ ui+1 .
In order to upper bound vi+1 , we can upper bound ui+1 .
Recall the algorithm places a ball in a bin of load t + L + i if it probes k times
and sees a bin of load t + L + i each time; or if it probes j < k times and sees a bin
of load t + L + i each time, then probes a bin of load ≥ t + L + i + 1; or if it probes
j < k times and sees a bin of load at least t + L + i + 1 each time (where the load of
the bin probed each time is the same), then probes a bin of load t + L + i. Thus the
probability that a ball will end up at height at least t + L + i + 1 is


k−2
2
≤ βik + βi βi+1 1 + βi + βi2 + . . . + βik−2 + βi βi+1 1 + βi+1 + βi+1
+ . . . + βi+1
!
k−1
1 − βi+1
1 − βik−1
k
≤ βi + βi βi+1
+
1 − βi
1 − βi+1


1
≤ βik + βl βi+1 2 ∗
1 − βl
2βi+1
≤ βik +
8L3 − 1
Let vi+1 (f ) be the fraction of bins with load at least t + i + 1 after the tn + f th ,
1 ≤ f ≤ nL, ball is placed in a bin.

20

J. AUGUSTINE, W. K. MOSES JR., A. REDLICH, AND E. UPFAL

Let f ∗ = min[arg minf vi+1 (f ) > βi+1 , nL], i.e. f ∗ is the first f such that
vi+1 (f ) > βi+1 or nL if there is no such f . By our preceding argument, the probability that f ∗ < nL is bounded by the probability that a binomial random variable
2βi+1
B(nL, ≤ βik + 8L
3 −1 ) is greater than βi+1 nL.
Fix
2βi+1
2nL(βik + 8L
3 −1 )
8L3 − 1
k
βi+1 = 2L 3
β ≥
.
8L − 4L − 1 i
n
Then using a Chernoff bound,
we can
say that with high probability, f ∗ = nL or


vi+1 ≤ βi+1 , so long as e−

βik +

2βi+1
8L3 −1
3

= O( n1c ) for some constant c ≥ 1.


2βi+1
βik +
8L3 −1
−
3

n
Now, so long as βi+1 ≥ 18 log
, e
= O( n1c ). In other words, this
n
upper bound holds for the placement of all nt + nL balls.

We now show that according to the previous recurrence relation, βi∗ dips below
We later propose a modified recurrence relation which sets the value of βi to
n
. This ensures
the maximum of the value of obtained from the recurrence and 18 log
n
18 log n
. This upper bound will be used later in the argument. We have,
that βi∗ =
n
from the value of βℓ and the above discussion,
log βℓ = −3 log(2L) and
3
−1
log βi+1 = k log βi + log(2L) + log( 8L8L
3 −4L−1 )
Solving the recursion for log βℓ+log log n , we get


2L(8L3 − 1)
k log log n − 1
− 3k log log n log(2L)
log
log βℓ+log log n =
k−1
8L3 − 4L − 1



8L3 − 1
≤ k log log n (−3k + 4) log(2L) + log
8L3 − 4L − 1



8L3 − 1
≤ k log log n (−6 + 4) log(2L) + log
8L3 − 4L − 1
18 log n
.
n

≤ k log log n ((−1.5) log(2L)) (when L ≥ 2)

≤ 2log log n ((−1.5) log(2L))
≤ (−1.5)(log n)
n
,
Therefore, βi∗ ≤ n−1.5 , when L ≥ 2. Since n ≥ n1 , we have L ≥ 2. Thus βi∗ < 18 log
n
as desired.
Now, we need to bound Pr(vi > βi |vi−1 ≤ βi−1 , Gt < L) for all i’s from ℓ + 1 to
3
−1
k 18 log n
i∗ . Let us set βi+1 = max(2L 8L8L
).
3 −4L−1 βi ,
n
Using the values of βi generated above, we prove that for all i such that ℓ + 1 ≤
i ≤ i∗ , Pr(vi > βi |vi−1 ≤ βi−1 , Gt < L) ≤ n13 .

For a given i,
Pr(vi > βi |vi−1 ≤ βi−1 , Gt < L) = Pr(nvi > nβi |vi−1 ≤ βi−1 , Gt < L)
≤ Pr(ui > nβi |vi−1 ≤ βi−1 , Gt < L)
We now upper bound the above inequality using the following idea. Let Yr be an
indicator variable set to 1 when all three of the following conditions are met: (i) the

21

BALANCED ALLOCATION: PATIENCE IS NOT A VIRTUE

nt + rth ball placed is of height at least t + L + i, (ii) vi−1 ≤ βi−1 and (iii) Gt < L.
Yr is set to 0 otherwise. Now for all 1 ≤ r ≤ nL, the probability that Yr = 1 is upper
2βi+1
βi
8L3 −1
k
t
bounded by βik + 8L
3 −1 ≤ 8L3 −4L−1 βi−1 ≤ 2L . Since we condition on G < L, the
number of balls of height at least t + L or more come only from the nL balls placed.
Therefore, the probability that the number of balls of height at least n + L + i exceeds
βi
βi is upper bounded by Pr(B(nL, 2L
) > βi ), where B(., .) is a binomial random
variable with given parameters.
µδ2

According to Chernoff’s bound, for 0 < δ ≤ 1, Pr(X ≥ (1 + δ)µ) ≤ e− 3 , where
X is the sum of independent Poisson trials and µ is the expectation of X. If we set
δ = 1, then we have

Pr(vi > βi |vi−1 ≤ βi−1 , Gt < L)
βi
≤ Pr(B(nL,
) > βi )
2L
n ∗ ( β2i )
−
3
≤e
n
n ∗ ( 18 log
)
n
18 log n
6
≤e
(since βi ≥
, ∀i ≤ i∗ )
n
1
≤ 3
n
−

Thus we bound the middle term in Equation 5

∗

i
X

Pr(vj > βj |vj−1 ≤ βj−1 , Gt < L) ≤

log log n
n3

Pr(vj > βj |vj−1 ≤ βj−1 , Gt < L) ≤

1
(since n ≥ n1 )
2n2

j=ℓ+1
∗

(7)

=⇒

i
X
j=ℓ+1

Top layers of layered induction
Finally, we need to upper bound the first term in Equation 5,
Pr(vi∗ +4 > 0|vi∗ ≤ βi∗ , Gt < L). Consider a bin of load at least i∗ . We will upper
bound the probability that a ball falls into this specific bin. Regardless of how the
probes are made for that ball, one of them must be made to that specific bin. Thus
we have a formula similar to our original recursion, but with a factor of 1/n.

22

J. AUGUSTINE, W. K. MOSES JR., A. REDLICH, AND E. UPFAL

Therefore the probability that a ball will fall into that bin is
≤
≤
≤
≤
≤
≤

 1

1 k−1 1
+ βi∗ +1 1 + βi∗ +1 + βi2∗ +1 + . . . + βik−2
βi
+ βi∗ +1 1 + βi∗ + βi∗ + . . . + βik−2
∗
∗ +1
n 
n
n


1
1
k−1
· βi∗ + 2βi∗ +1
n
1 − βi∗ +1



1
1
· βik−1
+ 2βi∗
∗
n
1 − βi∗


1
2n
· βik−1
βi∗
+
∗
n
n − 18 log n
1 3n − 18 log n
·
· βi∗ (since k ≥ 2 and βi∗ ≤ 1)
n n − 18 log n
4
· βi∗ (since n > n3 )
n

Now, we upper bound the probability that 4 balls fall into a given bin of load
at least βi∗ and then use a union bound over all the bins of height at least βi∗ to
show that the probability that the fraction of bins of load at least βi∗ +4 exceeds 0 is
negligible.
First, the probability that 4 balls fall into a given bin of load at least βi∗ is
4
≤ Pr(B(nL, ( · βi∗ )) ≥ 4)
n
4
 
nL
4
· βi∗
≤
n
4
4

4
1
≤ e · nL · ( · βi∗ ) ·
n
4
4

≤ (eLβi∗ )

Taking the union bound across all possible βi∗ n bins, we have the following inequality
4

Pr(vi∗ +4 > 0|vi∗ ≤ βi∗ , Gt < L) ≤ (βi∗ n) · (eLβi∗ )

4
18eL log n
t
∗
∗
∗
=⇒ Pr(vi +4 > 0|vi ≤ βi , G < L) ≤ (18 log n) ·
n
1
(since n ≥ n2 )
=⇒ Pr(vi∗ +4 > 0|vi∗ ≤ βi∗ , Gt < L) ≤
2n2

(8)

Putting together equations 5, 6, 7, and 8, we get
16bL3
1
1
+ 2+ 2
eaℓ
2n
2n
1
16bL3
+ 2
≤
aℓ
e
n

Pr(vi∗ +4 > 0|Gt < L) ≤

Thus

23

BALANCED ALLOCATION: PATIENCE IS NOT A VIRTUE

Pr(Gt+L ≥

log log n
+ ℓ + 4|Gt < L) = Pr(vi∗ +4 > 0|Gt < L)
log k
1
16bL3
+ 2
≤
eaℓ
n

Finally
Pr(Gt+L ≥

log log n
log log n
+ ℓ + 4) ≤ Pr(Gt ≥ L) + Pr(Gt+L ≥
+ ℓ + 4|Gt < L)
log k
log k
1
16bL3
≤ Pr(Gt ≥ L) + aℓ + 2
e
n

Hence Lemma 4.8 is proved.
By Lemma 4.5, we know that at some arbitrary time t, the gap will be O(log n)
with high probability. Now applying Lemma 4.8 once with L = O(log n) and ℓ =
O(log log n) with appropriately chosen constants, we get Pr(Gt+L ≥ logloglogk n +O(log log n)+
γ) ≤ O((log log n)−4 ). Applying the lemma again with L = O(log log n) and ℓ =
O(log log log n) with appropriately chosen constants, we get
c
Pr(Gt > logloglogk n + c log log log n) ≤ (log log
n)4 when time t = ω(log n).
We now show that as more balls are placed, the probability that the gap exceeds
a particular value increases. This is true by Lemma 4 from [14]:
′

′

Lemma 4.9. [14] For t ≥ t′ , Gt is stochastically dominated by Gt . Thus E[Gt ] ≤
′
E[Gt ] and for every z, Pr(Gt ≥ z) ≤ Pr(Gt ≥ z).
Although the setting is different in [14], their proof of Lemma 4.9 applies here
as well. Thus knowing the gap is large when time t = ω(log n) with probability
O((log log n)−4 ), implies that for all values of t′ < t, the gap exceeds the desired value
with at most the same probability. Substituting k = 2d/2.17 in Pr(Gt > logloglogk n +
c
c log log log n) ≤ (log log
n)4 and modifying the inequality to talk about max. load after
m balls have been thrown results in the lemma statement.
Thus concludes the proof of Lemma 4.4.
Putting together Lemma 4.2 and Lemma 4.4, we get Theorem 4.1.
5. Lower Bound on Maximum Bin Load. We now provide a lower bound
to the maximum load of any bin after using FirstDiff[d] as well as other types of algorithms which use a variable number of probes for Class 1 type algorithms as defined
by Vöcking [15]. Class 1 algorithms are those where for each ball, the locations are
chosen uniformly and independently at random from the bins available. We first give
a general theorem for this type of algorithm and then apply it to FirstDiff[d].
Theorem 5.1. Let Alg[k] be any algorithm that places m balls into n bins, where
m ≥ n, sequentially one by one and satisfies the following conditions:
1. At most k probes are used to place each ball.
2. For each ball, each probe is made uniformly at random to one of the n bins.
3. For each ball, each probe is independent of every other probe.
The maximum load of any bin after placing all m balls using Alg[k] is at least m
n +
ln ln n
−
Θ(1)
with
high
probability.
ln k

24

J. AUGUSTINE, W. K. MOSES JR., A. REDLICH, AND E. UPFAL

Proof. We show that Greedy[k] is majorized by Alg[k], i.e. Greedy[k] always performs better than Alg[k] in terms of load balancing. Thus any lower bound that
applies to the max. load of any bin after using Greedy[k] must also apply to Alg[k].
Let the load vectors for Greedy[k] and Alg[k] after t balls have been placed using
the respective algorithms be ut and v t respectively. We use induction on the number
of balls placed to prove our claim of majorization. Initially, no ball is placed and by
default u0 is majorized by v 0 . Assume that ut−1 is majorized by v t−1 . We now use the
standard coupling argument to prove the induction hypothesis. For the placement of
the tth ball, let Alg[k] use wt probes. Couple Greedy[k] with Alg[k] by letting the first
wt bins probed by Greedy[k] be the same bins probed by Alg[k]. Greedy[k] will always
make at least wt probes and thus possibly makes probes to lesser loaded bins than
those probed by Alg[k]. Since Greedy[k] places a ball into the least loaded bin it finds,
it will place a ball into a bin with load at most the same as the one chosen by Alg[k].
Therefore ut is majorized by v t . Thus by induction, we see that ut is majorized by v t
for all 0 ≤ t ≤ m. Therefore Greedy[k] is majorized by Alg[k].
It is known that the max. load of any bin after the placement of m balls into n
ln ln n
bins (m ≥ n) using Greedy[k] is at least m
n + ln k − Θ(1) with high probability [3].
Therefore, the same lower bound also applies to Alg[k].
Now we are ready to prove our lower bound on the max. load of any bin after
using FirstDiff[d].
Theorem 5.2. The maximum load of any bin after placing m balls into n bins
using FirstDiff[d], where maximum number of probes allowed per ball is 2Θ(d) , is at
ln ln n
least m
n + Θ(d) − Θ(1) with high probability.
Proof. We see that FirstDiff[d] uses at most 2Θ(d) probes and satisfies the requirements of Theorem 5.1. Thus by substituting k = 2Θ(d) , we get the desired bound.
Table 1
Experimental results for the maximum load for n balls and n bins based on 100 experiments for
each configuration. Note that the maximum number of probes per ball in FirstDiff[d], denoted as k,
is chosen such that the average number of probes per ball is fewer than d.

n
28

Greedy[d]
2...11%
3...87%
4... 2%

d = 2, k = 3
Left[d]
FirstDiff[d]
2...43%
2...81%
3...57%
3...19%

Greedy[d]
2...88%
3...12%

d = 3, k = 10
Left[d]
FirstDiff[d]
2...100%
2...100%

Greedy[d]
2...100%

d = 4, k = 30
Left[d]
FirstDiff[d]
2...100%
2...100%

2...10%
3...90%

2...12%
3...88%

2...96%
3... 4%

2...100%

2...93%
3... 7%

2...100%

2...100%

2...100%

3...100

2...31%
3...69%

2...100%

3...100%

2...49%
3...51%

2...100%

3...98%
4... 2%

2...100%

2...100%

3...100%

3...100%

3...100%

4...100%

3...96%
4... 4%

2...100%

2...100%

3...100%

3...100%

3...100%

4...100%

3...37%
4...63%

212

3...99%
4... 1%

3...100%

216

3...63%
4...37%

2...100%
220

3...100%
2...100%

224

3...100%

6. Experimental Results. We experimentally compare the performance of
FirstDiff[d] with Left[d] and Greedy[d] in Table 1. Similar to the experimental results in [15], we perform all 3 algorithms in different configurations of bins and d

BALANCED ALLOCATION: PATIENCE IS NOT A VIRTUE

25

values. Let k be the maximum number of probes allowed to be used by FirstDiff[d]
per ball. For each value of d ∈ [2, 4], we choose a corresponding value of k such
that the average number of probes required by each ball in FirstDiff[d] is at most d.
For each configuration, we run each algorithm 100 times and note the percentage of
times the maximum loaded bin had a particular value. It is of interest to note that
FirstDiff[d], despite using on average less than d probes per ball, appears to perform
better than both Greedy[d] and FirstDiff[d] in terms of maximum load.
7. Conclusions and Future Work. In this paper, we have introduced a novel
algorithm called FirstDiff[d] for the well-studied load balancing problem. This algorithm combines the benefits of two prominent algorithms, namely, Greedy[d] and
Left[d]. FirstDiff[d] generates a maximum load comparable to that of Left[d], while
being as fully decentralized as Greedy[d]. From another perspective, we observe that
FirstDiff[log d] and Greedy[d] result in a comparable maximum load, while the number
of probes used by FirstDiff[log d] is exponentially smaller than that of Greedy[d]. In
other words, we exhibit an algorithm that performs as well as an optimal algorithm,
with significantly less computational requirements. We believe that our work has
opened up a new family of algorithms that could prove to be quite useful in a variety
of contexts spanning both theory and practice.
A number of questions arise out of our work. From a theoretical perspective, we
are interested in developing a finer-grained analysis of the number of probes; experimental results suggest the number of probes used to place the ith ball depends on
the congruence class of i modulo n. From an applied perspective, we are interested in
understanding how FirstDiff[d] would play out in real world load balancing scenarios
like cloud computing, where the environment (i.e. the servers, their interconnections,
etc.) and the workload (jobs, applications, users, etc.) are likely to be a lot more
heterogeneous and dynamic.
Acknowledgements. We are thankful to Anant Nag for useful discussions and
developing a balls-in-bins library [9] that was helpful for our experiments. We are
also grateful to Thomas Sauerwald for his helpful thoughts when he visited Institute
for Computational and Experimental Research in Mathematics (ICERM) at Brown
University. Finally, John Augustine and Amanda Redlich are thankful to ICERM for
having hosted them as part of a semester long program.
REFERENCES
[1] J. Augustine, W. K. Moses Jr., A. Redlich, and E. Upfal, Balanced allocation: patience
is not a virtue, in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on
Discrete Algorithms, Society for Industrial and Applied Mathematics, 2016, pp. 655–671.
[2] Y. Azar, A. Z. Broder, A. R. Karlin, and E. Upfal, Balanced allocations, SIAM journal
on computing, 29 (1999), pp. 180–200.
[3] P. Berenbrink, A. Czumaj, A. Steger, and B. Vöcking, Balanced allocations: The heavily
loaded case, SIAM Journal on Computing, 35 (2006), pp. 1350–1385.
[4] P. Berenbrink, K. Khodamoradi, T. Sauerwald, and A. Stauffer, Balls-into-bins with
nearly optimal load distribution, in Proceedings of the 25th ACM symposium on Parallelism
in algorithms and architectures, ACM, 2013, pp. 326–335.
[5] A. Czumaj and V. Stemann, Randomized allocation processes, Random Structures & Algorithms, 18 (2001), pp. 297–331.
[6] S. Fu, C.-Z. Xu, and H. Shen, Randomized load balancing strategies with churn resilience in
peer-to-peer networks, Journal of Network and Computer Applications, 34 (2011), pp. 252–
261.
[7] S. Janson, Tail bounds for sums of geometric and exponential variables, Technical report,
(2014).

26

J. AUGUSTINE, W. K. MOSES JR., A. REDLICH, AND E. UPFAL

[8] M. Mitzenmacher and E. Upfal, Probability and computing: Randomized algorithms and
probabilistic analysis, Cambridge University Press, 2005.
[9] A. Nag, Problems in Balls and Bins Model, master’s thesis, Indian Institute of Technology
Madras, India, 2014.
[10] Y. Peres, K. Talwar, and U. Wieder, The (1+ β)-choice process and weighted balls-into-bins,
in Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms,
Society for Industrial and Applied Mathematics, 2010, pp. 1613–1619.
[11] M. Raab and A. Steger, “balls into bins”–a simple and tight analysis, in Randomization and
Approximation Techniques in Computer Science, Springer, 1998, pp. 159–170.
[12] H. Shen and C.-Z. Xu, Locality-aware and churn-resilient load-balancing algorithms in structured peer-to-peer networks, Parallel and Distributed Systems, IEEE Transactions on, 18
(2007), pp. 849–862.
[13] X.-J. Shen, L. Liu, Z.-J. Zha, P.-Y. Gu, Z.-Q. Jiang, J.-M. Chen, and J. Panneerselvam,
Achieving dynamic load balancing through mobile agents in small world p2p networks,
Computer Networks, 75 (2014), pp. 134–148.
[14] K. Talwar and U. Wieder, Balanced allocations: A simple proof for the heavily loaded case,
in Automata, Languages, and Programming, Springer, 2014, pp. 979–990.
[15] B. Vöcking, How asymmetry helps load balancing, Journal of the ACM (JACM), 50 (2003),
pp. 568–589.

