It is well known that after placing n balls independently and uniformly at random into n bins, the fullest bin holds approximately log n / log log n balls with high probability. More recently, Azar, Broder, Karlin, and Upfal 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. They show that after all n balls have been placed, the fullest bin contains only about log log n / log d 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 of Omega(sqrt[r]{log n / log log n}) 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. The algorithm also works well in asynchronous environments.
Originally appeared in roceedings of the 27th ACM Symposium on the Theory of Computing, pp. 238-247, 1995. Journal version: Random Structures and Algorithms, vol. 13:2, September 1998, pp. 159-188.