Simple Load Balancing

08/16/2018
by   Petra Berenbrink, et al.
0

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 ℓ_1 and ℓ_2 be their respective number of tokens. The two nodes exchange tokens such that they have (ℓ_1 + ℓ_2)/2 and (ℓ_1 + ℓ_2)/2 tokens, respectively. We provide a simple analysis showing that this process reaches almost perfect balance within O(nn + n Δ) steps, where Δ is the maximal initial load difference between any two nodes.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset