Balanced Allocations with Heterogeneous Bins

Balls-into-bins processes are a useful and common abstraction for many load-balancing related problems. A well known paradigm for loadbalancing in distributed or parallel servers is the “multiple choice paradigm” where an item (ball) is put in the less loaded out of d uniformly chosen servers (bins). In many applications however the uniformity of the sampling probability is not guaranteed. If the system is heterogenous or dynamic it may be the case that some bins are sampled with a higher probability than others. We investigate the power of the multiple choice paradigm in the setting where bins are not sampled from the uniform distribution. Byers et al [5] showed that a logarithmic imbalance in the sampling probability could be tolerated, as long as the number of balls is linear in the number of bins. We show that if the number of balls is much larger than the number of bins, this ceases to be the case. Given a probability over bins, we prove tight upper and lower bounds for the number of choices needed in the 1-out-of-d scheme in order to maintain a balanced allocations when the number of items is arbitrarily high.