The power of $d$-thinning in load balancing

Ohad N. Feldheim, Jiange Li

Published 2019-08-27Version 1

In the classical balls-and-bins model, $m$ balls are allocated into $n$ bins one by one uniformly at random. In this note, we consider the $d$-thinning variant of this model, in which the process is regulated in an on-line fashion as follows. For each ball, after a random allocation bin has been generated, an overseer may decide, based on all previous history, whether to accept or reject this allocation. However, one of every $d$ consecutive suggested allocations must be accepted. The \emph{maximum load} of the model is the number of balls in the most loaded bin. We show that after $\Theta(n)$ balls have been allocated, the least maximum load achievable with high probability is $(d+o(1))(d\log n/\log\log n)^{1/d}$. This is in contrast with the related two-choice model, in which the number of alternative choices offered to the overseer merely affects the achievable maximum load by a multiplicative constant.