Skip to main content

Research Repository

Advanced Search

Threshold Load Balancing With Weighted Tasks

Berenbrink, Petra; Friedetzky, Tom; Mallmann-Trenn, Frederik; Meshkinfamfard, Sepehr; Wastell, Chris

Threshold Load Balancing With Weighted Tasks Thumbnail


Authors

Petra Berenbrink

Frederik Mallmann-Trenn

Sepehr Meshkinfamfard

Chris Wastell



Abstract

We study threshold-based load balancing protocols for weighted tasks. We are given an arbitrary graph G with n nodes (resources, bins) and m≥n tasks (balls). Initially the tasks are distributed arbitrarily over the n nodes. The resources have a threshold and we are interested in the balancing time, i.e., the time it takes until the load of all resources is below or at the threshold. We distinguish between resource-based and user-based protocols. In the case of resource-based protocols resources with a load larger than the threshold are allowed to send tasks to neighbouring resources. In the case of user-based protocols the tasks make the migration decisions and we restrict ourselves to the complete graph in the model. Any task allocated to a resource with a load above the threshold decides whether to migrate to a neighboring resource independently of the other tasks. For resource-controlled protocols we present results for arbitrary graphs. For the user-controlled migration we consider complete graphs and derive bounds for both above-average and tight thresholds.

Citation

Berenbrink, P., Friedetzky, T., Mallmann-Trenn, F., Meshkinfamfard, S., & Wastell, C. (2018). Threshold Load Balancing With Weighted Tasks. Journal of Parallel and Distributed Computing, 113, 218-226. https://doi.org/10.1016/j.jpdc.2017.10.012

Journal Article Type Article
Acceptance Date Oct 22, 2017
Online Publication Date Nov 14, 2017
Publication Date 2018-03
Deposit Date Oct 23, 2017
Publicly Available Date Nov 14, 2018
Journal Journal of Parallel and Distributed Computing
Print ISSN 0743-7315
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 113
Pages 218-226
DOI https://doi.org/10.1016/j.jpdc.2017.10.012

Files





You might also like



Downloadable Citations