Threshold Load Balancing With Weighted Tasks

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

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
• Electronic ISSN: 1096-0848
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 113
• Pages: 218-226
• DOI: https://doi.org/10.1016/j.jpdc.2017.10.012
• Public URL: https://durham-repository.worktribe.com/output/1342124