Balls into non-uniform bins

• This paper investigates randomised multiple-choice balls-into-bins games.
• Such a balls-into-bins game models the allocation of tasks to servers of different speeds/capacities.
• It is shown that a balanced allocation can be achieved if the number of balls equals the total capacity.
• Simulations of other cases suggest that our algorithm works even for a small amount of balls and bins.

Balls-into-bins games for uniform bins are widely used to model randomised load balancing strategies. Recently, balls-into-bins games have been analysed under the assumption that the selection probabilities for bins are not uniformly distributed. These new models are motivated by properties of many peer-to-peer (P2P) networks. In this paper we consider scenarios in which non-uniform selection probabilities help to balance the load among the bins. While previous evaluations try to find strategies for identical bins, we investigate heterogeneous bins where the “capacities” of the bins might differ significantly. We look at the allocation of mm balls into nn bins of total capacity CC where each ball has dd random bin choices. For such heterogeneous environments we show that the maximum load remains bounded by lnln(n)/ln(d)+O(1)lnln(n)/ln(d)+O(1)w.h.p.   if the number of balls mm equals the total capacity CC. Further analytical and simulative results show better bounds and values for the maximum loads in special cases.