Threshold load balancing with weighted tasks

Petra Berenbrink

doi:10.1016/j.jpdc.2017.10.012

2018-03-01

Petra Berenbrink

Tom Friedetzky

Frederik Mallmann-Trenn *

Sepehr Meshkinfamfard

Chris Wastell

DOI：10.1016/j.jpdc.2017.10.012

原文链接

查看原文

摘要

En 中文

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. (C) 2017 Elsevier Inc. All rights reserved.

Keyword:

Threshold load balancing

Random walks

Mixing time of random walks

Weighted tasks