Randomised Load Balancing with Random Deletions

Abstract

Random processes like hashing and load balancing can be modelled as
balls-into-bins games where the bins are buckets or servers and the
balls are items or requests. Most results in the literature consider
only ball insertions but leave out ball deletions. For a long time it
has remained an open problem to prove what effect random ball deletions
have on the load balance.

In this talk I will present the analysis of an infinite balls-into-bins
process with random deletions. In every round t, with probability
\beta(t), a ball is inserted with two choices (i.e. the ball is
allocated to the lesser loaded of two randomly chosen bins), and with
probability 1-\beta(t), a randomly chosen ball is deleted. Tight bounds
on the (current) maximum load will be given, which hold with high
probability. The results were achieved by combining different methods
including a potential analysis, a layered induction, and probabilistic
couplings to obtain recovery properties.