Threshold load balancing with weighted tasks

We study threshold-based load balancing protocols for weighted tasks. We are given an arbitrary graph with nodes (resources, bins) and tasks (balls). Initially the tasks are distributed arbitrarily over the 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.