Load Balancing under Adaptive Bin Deletions
Abstract
We analyze a balls-and-bins game against an adaptive adversary that sequentially deletes bins. Starting with n balls distributed across n bins, the adversary deletes a bin in each step, forcing the algorithm to redistribute its balls to surviving bins. We prove that after n/2 rounds, uniform random redistribution yields optimal O(n) recourse and $O(\frac{\log n}{\log \log n})$ maximum load. Furthermore, we show that applying the "power of two choices"' reduces the maximum load to $O(\log \log n)$ while maintaining linear recourse.
We also consider a variation of this game where the balls from the deleted bin are partitioned evenly among d<<n random bins rather than being redistributed independently. We demonstrate that keeping the balls together (d=1), which gives small maximum load and recourse against an oblivious adversary, fails against an adaptive adversary. Nevertheless, we show that splitting the balls into just two groups (d=2) is sufficient to recover linear recourse and efficient load balancing in the adaptive setting.
We also consider a variation of this game where the balls from the deleted bin are partitioned evenly among d<<n random bins rather than being redistributed independently. We demonstrate that keeping the balls together (d=1), which gives small maximum load and recourse against an oblivious adversary, fails against an adaptive adversary. Nevertheless, we show that splitting the balls into just two groups (d=2) is sufficient to recover linear recourse and efficient load balancing in the adaptive setting.
Research Areas
