Tight & Simple Load Balancing

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 ℓ
₁
and ℓ
₂
be their respective number of tokens. The two nodes exchange tokens such that they have [(ℓ
₁
+ℓ
₂
)/
₂
] and [(ℓ
₁
+ℓ
₂
)/
₂
] tokens, respectively. We provide a simple analysis showing that this process reaches almost perfect balance within O(n log n + n log Δ) steps with high probability, where Δ is the maximal initial load difference between any two nodes. This bound is asymptotically tight.