Tight & simple load balancing

Publikationstyp
Conference Paper
Date Issued
2019-05
Sprache
English
Author(s)
Berenbrink, Petra  
Friedetzky, Thomas  
Kaaser, Dominik 
Data Engineering E-19  
Kling, Peter  
TORE-URI
https://hdl.handle.net/11420/54451
Article Number
8821017
Citation
Proceedings - IEEE 33rd International Parallel and Distributed Processing Symposium, IPDPS 2019: 8821017
Contribution to Conference
33rd IEEE International Parallel and Distributed Processing Symposium, IPDPS 2019  
Publisher DOI
10.1109/IPDPS.2019.00080
Scopus ID
2-s2.0-85070994525
Publisher
IEEE
ISBN
978-1-7281-1246-6
978-1-7281-1247-3
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(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.
DDC Class
600: Technology