Tight & Simple Load Balancing

Berenbrink, Petra; Friedetzky, Tom; Kaaser, Dominik; Kling, Peter

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 ℓ 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.

Citation

Berenbrink, P., Friedetzky, T., Kaaser, D., & Kling, P. (2019, December). Tight & Simple Load Balancing. Presented at IEEE International Parallel & Distributed Processing Symposium (IPDPS), Rio de Janeiro, Brazil

• Presentation Conference Type: Conference Paper (published)
• Conference Name: IEEE International Parallel & Distributed Processing Symposium (IPDPS)
• Acceptance Date: Jan 24, 2019
• Online Publication Date: Sep 2, 2019
• Publication Date: Jan 1, 2019
• Deposit Date: Mar 29, 2019
• Publicly Available Date: Nov 13, 2019
• Pages: 718-726
• Series ISSN: 1530-2075
• Book Title: 33rd IEEE International Parallel & Distributed Processing Symposium ; proceedings.
• DOI: https://doi.org/10.1109/ipdps.2019.00080
• Public URL: https://durham-repository.worktribe.com/output/1142413