Tight & Simple Load Balancing

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

doi:10.1109/ipdps.2019.00080

Tight & Simple Load Balancing

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

Authors

Petra Berenbrink

Dr Tom Friedetzky tom.friedetzky@durham.ac.uk
Associate Professor

Dominik Kaaser

Peter Kling

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). Tight & Simple Load Balancing. In 33rd IEEE International Parallel & Distributed Processing Symposium ; proceedings (718-726). https://doi.org/10.1109/ipdps.2019.00080

Conference Name	IEEE International Parallel & Distributed Processing Symposium (IPDPS)
Conference Location	Rio de Janeiro, Brazil
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

Files

Accepted Conference Proceeding (456 Kb)
PDF

Copyright Statement
© 2019 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.