####
Parallel Randomized Load Balancing

It is well known that after placing n balls independently and
uniformly at random into n bins, the fullest bin holds Omega(log n/log
log n) balls with high probability. More recently, Azar et
al. analyzed the following process: randomly choose d bins for each
ball, and then place the balls, one by one, into the least full bin
from its d choices. Azar et al. They show that after all n balls have
been placed, the fullest bin contains only log log n/log d+(1) balls
with high probability. We explore extensions of this result to
parallel and distributed settings. Our results focus on the tradeoff
between the amount of communication and the final load. Given r rounds
of communication, we provide lower bounds on the maximum load for a
wide class of strategies. Our results extend to the case where the
number of rounds is allowed to grow with n. We then demonstrate
parallelizations of the sequential strategy presented in Azar et
al. that achieve loads within a constant factor of the lower bound for
two communication rounds and almost match the sequential strategy
given log log n/log d+O(d) rounds of communication. We also examine a
parallel threshold strategy based on rethrowing balls placed in
heavily loaded bins. This strategy achieves loads within a constant
factor of the lower bound for a constant number of rounds, and it
achieves a final load of at most O(log log n) given Omega(log log n) rounds
of communication.