Parallel Balanced Allocation

We study the well known problem of throwing m balls into n bins. If each ball in the sequential game is allowed to select more than one bin, the maximum load of the bins can be exponentially reduced compared to the 'classical balls into bins' game.We consider a static and a dynamic variant of a randomized parallel allocation where each ball can choose a constant number of bins. All results hold with high probability. In the static case all m balls arrive at the same time. We analyze for m = n a very simple optimal class of protocols achieving maximum load O{x?{log n}/{log log n}} if r rounds of communication are allowed. This matches the lower bound of [ACMR95].Furthermore, we generalize the protocols to the case of m > n balls. An optimal load of O(m/n) can be achieved using {log log n}/{log(m/n)} rounds of communication. Hence, for m = n{log log n}/{log log log n} balls this slackness allows to hide the amount of communication. In the 'classical balls into bins' game this optimal distribution can only be achieved for m = nlog n.In the dynamic variant n of the m balls arrive at the same time and have to be allocated. Each of these initial n balls has a list of m/n successor-balls. As soon as a ball is allocated its successor will be processed. We present an optimal parallel process that allocates all m = nlog n balls in O(m/n) rounds. Hence, the expected allocation time is constant. The main contribution of this process is that the maximum allocation time is additionally bounded by O(log log n).

ICSI Technical Report TR-96-020

Technical Report