Load Balancing under Adaptive Bin Deletions
This work provides theoretical guarantees for load balancing in dynamic settings with adversarial deletions, relevant to distributed systems and cloud computing.
The paper analyzes load balancing under adaptive bin deletions, proving that uniform random redistribution achieves O(n) recourse and O(log n / log log n) maximum load after n/2 rounds, and that the power of two choices reduces maximum load to O(log log n) while maintaining linear recourse.
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 \ll 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.