Balls-into-bins processes are a useful and common abstraction for many load-balancing related problems. A well known paradigm for load balancing 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 \emph{not} sampled from the uniform distribution. Byers \etal \cite{BCM04} 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.

PowerPoint slide show

PDF file

In: SPAA '07: Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures

Publisher: ACM

Details