####
On balls and bins with deletions

We consider the problem of extending the analysis of balls and bins
processes where a ball is placed in the least loaded of d randomly
chosen bins to cover deletions. In particular, we are interested in
the case where the system maintains a fixed load, and deletions are
determined by an adversary before the process begins. We show that
with high probability the load in any bin is . In fact, this result
follows from recent work by Cole et al. concerning a more difficult
problem of routing in a butterfly network. The main contribution of
this paper is to give a different proof of this bound, which follows
the lines of the analysis of Azar, Broder, Karlin, and Upfal for the
corresponding static load balancing problem. We also give a
specialized (and hence simpler) version of the argument from the paper
by Cole et al. for the balls and bins scenario.Finally, we provide an
alternative analysis also based on the approach of Azar, Broder,
Karlin, and Upfal for the special case where items are deleted
according to their age. Although this analysis does not yield better
bounds than our argument for the general case, it is interesting
because it utilizes a two-dimensional family of random variables in
order to account for the age of the items. This technique may be of
more general use.