| Title | : | Balanced Allocation: Patience is not a Virtue |
| Speaker | : | William Kumar Moses Jr (IITM) |
| Details | : | Tue, 9 Aug, 2016 4:30 PM @ BSB 361 |
| Abstract: | : | Load balancing is a common problem in multiple domains. The version that we are interested in is where a load balancer must allocate process requests to servers such that the number of requests (load) on each server is minimized. The theoretical framework to analyze this is called the balls-in-bins model where process requests are denoted by balls and servers are denoted by bins.
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. Vocking 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. 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 further provide a tight lower bound on the maximum load up to O(log log log n) terms. We additionally give experimental data that FirstDiff[d] is indeed as good as Left[d], if not better, in practice. |
