Parallel randomized load balancing

Abstract

It is well known that after placing n balls independently and uniformly at random into n bins, the fullest bin holds Θ(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 of Ω(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 Ω(log log n) rounds of communication. The algorithm also works well in asynchronous environments. © 1998 John Wiley & Sons, Inc.