Repository logo
 

A simple approach for adapting continuous load balancing processes to discrete settings

Accepted version
Peer-reviewed

Type

Article

Change log

Authors

Akbari, H 
Berenbrink, P 
Sauerwald, T 

Abstract

We consider the neighbourhood load balancing problem. Given a network of processors and an arbitrary distribution of tasks over the network, the goal is to balance load by exchanging tasks between neighbours. In the continuous model, tasks can be arbitrarily divided and perfectly balanced state can always be reached. This is not possible in the discrete model where tasks are non-divisible. In this paper we consider the problem in a very general setting, where the tasks can have arbitrary weights and the nodes can have different speeds. Given a continuous load balancing algorithm that balances the load perfectly in (Formula presented.) rounds, we convert the algorithm into a discrete version. This new algorithm is deterministic and balances the load in  (Formula presented.) rounds so that the difference between the average and the maximum load is at most (Formula presented.) , where d is the maximum degree of the network and  (Formula presented.) is the maximum weight of any task. For general graphs, these bounds are asymptotically lower compared to the previous results. The proposed conversion scheme can be applied to a wide class of continuous processes, including first and second order diffusion, dimension exchange, and random matching processes. For the case of identical tasks, we present a randomized version of our algorithm that balances the load up to a discrepancy of  (Formula presented.) provided that the initial load on every node is large enough.

Description

Keywords

Load balancing, Discrete diffusion, Randomized rounding

Journal Title

Distributed Computing

Conference Name

Journal ISSN

0178-2770
1432-0452

Volume Title

29

Publisher

Springer
Sponsorship
Hoda Akbari, Petra Berenbrink and Thomas Sauerwald work was supported by an NSERC Discovery Grant “Analysis of Randomized Algorithms”.