BALANCED ALLOCATION: PATIENCE IS NOT A VIRTUE.

Load balancing is a well-studied problem, with balls-in-bins being the primary framework. The greedy algorithm Greedy[d] of Azar et al. [SIAM J. Comput., 29 (1999), pp. 180-200] places each ball by probing d>1 random bins and placing the ball in the least loaded of them. With high probability, the maximum load under Greedy[d] is exponentially lower than the result when balls are placed uniformly randomly. Vöcking [J. ACM, 50 (2003), pp. 568-589] showed that a slightly asymmetric variant, Left[d], provides a further significant improvement. However, this improvement comes at the additional computational cost of imposing structure on the bins. Here, we present a fully decentralized and easy-to-implement algorithm called FirstDiff[d] that combines the simplicity of Greedy[d] and the improved balance of Left[d]. The key idea in FirstDiff[d] is to probe until a different bin size from the first observation is located and then place the ball. Although the number of probes could be quite large for some of the balls, we show that FirstDiff[d] requires only at most d probes on average per ball (in both the standard and the heavily loaded settings). Thus the number of probes is no greater than that of either Greedy[d] or Left[d]. More importantly, we show that FirstDiff[d] closely matches the improved maximum load ensured by Left[d] in both the standard and heavily loaded settings. We further provide a tight lower bound on the maximum load up to O(logloglogn) terms. We additionally give experimental data that FirstDiff[d] is indeed as good as Left[d], if not better, in practice. [ABSTRACT FROM AUTHOR]