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 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 tasks allocated to resources with a load above the threshold decide on their own whether to migrate to a neighbouring resource or not. For resource-controlled protocols we present results for arbitrary graphs. Our bounds are in terms of the mixing time (for above-average thresholds) and the hitting time (for tight thresholds) of the graph. We relate the balancing time of resource-controlled protocols for above-average thresholds in arbitrary graphs to the mixing time of the graph and to the hitting time for tight thresholds. Our bounds are tight and, surprisingly, they are independent of the weights of the tasks. 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. (2015, May). Threshold Load Balancing with Weighted Tasks. Presented at 2015 IEEE 2015 IEEE 29th International Parallel and Distributed Processing Symposium., Hyderabad, India

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 2015 IEEE 2015 IEEE 29th International Parallel and Distributed Processing Symposium.
• Start Date: May 25, 2015
• End Date: May 29, 2015
• Acceptance Date: Dec 12, 2014
• Publication Date: May 29, 2015
• Deposit Date: Dec 16, 2015
• Publicly Available Date: Mar 18, 2016
• Pages: 550-558
• Series Title: Parallel and Distributed Processing Symposium (IPDPS)
• Series ISSN: 1530-2075
• Book Title: 2015 IEEE International Parallel and Distributed Processing Symposium (IPDPS 2015), 25–29 May 2015, Hyderabad, India ; proceedings.
• DOI: https://doi.org/10.1109/ipdps.2015.73
• Public URL: https://durham-repository.worktribe.com/output/1151464
• Additional Information: Date of Conference: 25-29 May 2015