Self-Stabilizing Repeated Balls-into-Bins ˚

We study the following synchronous process that we call re-peated balls-into-bins. The process is started by assigning n balls to n bins in an arbitrary way. Then, in every sub-sequent round, one ball is chosen according to some fixed strategy (random, FIFO, etc) from each non-empty bin, and re-assigned to one of the n bins uniformly at random. This process corresponds to a non-reversible Markov chain and our aim is to study its self-stabilization properties with re-spect to the maximum (bin) load and some related perfor-mance measures. We define a configuration (i.e., a state) legitimate if its maximum load is Oplognq. We first prove that, starting from any legitimate configuration, the process will only take on legitimate configurations over a period of length bounded by any polynomial in n, with high probability (w.h.p.). Fur-ther we prove that, starting from any configuration, the pro-cess converges to a legitimate configuration in linear time, w.h.p. This implies that the process is self-stabilizing w.h.p. and, moreover, that every ball traverses all bins inOpn log2 nq rounds, w.h.p. The latter result can also be interpreted as an almost tight bound on the cover time for the problem of parallel resource assignment in the complete graph