Threshold load balancing with weighted tasks

• Published in: Journal of parallel and distributed computing 2018-03, Vol.113, p.218-226
• Main Authors: Berenbrink, Petra, Friedetzky, Tom, Mallmann-Trenn, Frederik, Meshkinfamfard, Sepehr, Wastell, Chris
• Format: Article
• Language: English
• Subjects: Mixing time of random walks; Random walks; Threshold load balancing; Weighted tasks
• ISSN: 0743-7315; 1096-0848
• DOI: 10.1016/j.jpdc.2017.10.012

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 neighboring 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. •We study threshold-based load balancing protocols for weighted tasks in graphs.•We consider two models: (i) The resource-based model where the nodes decide which tasks are sent to neighbors; (ii) The user-based model where the tasks decide whether and where to move.•We show that the required time to balance depends on the mixing time and hitting time.•Our bounds for the resourced-based case are tight and, surprisingly, they are independent of the weights of the tasks.