Starting with an arbitrary assignment of n balls to n bins, the balls-into-bins process repeatedly selects one ball from a non-empty bin and reassigns the selected ball to one of the n bins uniformly at random. This results in each ball performing a delayed random walk over all the bins.

The balls-into-bins process is of particular interest in parallel and distributed computing, where the maximum load on each processor is modeled by the maximum number of balls in a bin.

A legitimate configuration is defined as an allocation of balls to bins such that the maximum number of balls in a bin is logarithmically bounded. The key result presented in this paper is that, starting from any configuration, the balls-into-bins process “converges to a legitimate configuration in linear time,” and subsequently, with high probability, takes on only legitimate configurations over any polynomially bounded time period. Starting with an overview of strategy, the steps of the proof are presented in a way that is both convincing and readable. Two short appendices highlight important details that would otherwise clutter the proof.

Overall, this paper is likely to attract readers with an interest in applying the key results to problems in distributed computing, as well as those who want to present proofs in an accessible way.