The Power of Two Choices for Deletions in Balls and Bins Models

Efficient load balancing is central to modern large-scale distributed systems, and the balls and bins paradigm has long provided a foundation for modelling task allocation in these scenarios, with the power-of-choices technique yielding exponential improvements in load balancing for insertions. However, the role of deletions has so far remained largely unexplored, leaving open a significant gap between theory and practice, since the effectiveness of a system depends not only on how new tasks are assigned, but also on how completed tasks are removed and resources reclaimed. In this thesis, we address this gap by extending the power-of-choices paradigm to deletions. We introduce the Power of d Choices for Deletions (PoCD) technique, where a ball is removed from the fullest of d randomly chosen bins, and prove its stochastic optimality among all online bin-based deletion algorithms. Building on this foundation, we design and analyse two dynamic models: a lazy model, where deletions may fail if all sampled bins are empty, and a guaranteed model, where deletions always succeed at the cost of additional overhead. Finally, we extend the framework to more complex multi-server systems by introducing the infopoint model, a novel queueing model that integrates PoCD into service policies. Through simulations, we show that this approach significantly reduces waiting times, improves load distribution, and makes better use of the available resources compared to the state of the art. Together, these results show that extending the power-of-choices paradigm to deletions yields scalable, efficient, and effective algorithms for modern load balancing challenges.