Paper Info
Title
Balanced Allocation: Patience is not a Virtue.
Abstract
Load balancing is a well-studied problem, with balls-in-bins being the primary framework. The greedy algorithm Greedy[d] of Azar et al. places each ball by probing d > 1 random bins and placing the ball in the least loaded of them. It ensures a maximum load that is exponentially better than the strategy of placing each ball uniformly at random. Vöcking showed that a slightly asymmetric variant, Left[d], provides a further significant improvement. However, this improvement comes at an 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, 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 d probes on average per ball (in both the standard and the heavily-loaded settings). Thus the number of probes is no greater than either that of 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 additionally give experimental data that FirstDiff[d] is indeed as good as Left[d], if not better, in practice.
Year
DOI
Venue
2016
10.5555/2884435.2884483
SODA '16: Symposium on Discrete Algorithms Arlington Virginia January, 2016
DocType
Volume
ISSN
Conference
abs/1602.08298
In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016), 655-671
ISBN
Citations 
PageRank 
978-1-61197-433-1
0
0.34
References 
Authors
7
4
Name
Order
Citations
PageRank
John Augustine120524.35
William K. Moses Jr.2245.65
Amanda Redlich362.96
Eli Upfal44310743.13