Simple Load Balancing

Abstract

We consider the following load balancing process for $m$ tokens distributed arbitrarily among $n$ nodes connected by a complete graph: In each time step a pair of nodes is selected uniformly at random. Let ${\ell }_1$ and ${\ell }_2$ be their respective number of tokens. The two nodes exchange tokens such that they have $\lceil ({\ell }_1+{\ell }_2)/2\rceil$ and $\lfloor ({\ell }_1+{\ell }_2)/2\rfloor$ tokens, respectively. We provide a simple analysis showing that this process reaches almost perfect balance within $O(n\log n+n\log \Delta )$ steps, where $\Delta$ is the maximal initial load difference between any two nodes.