A Simple Approach for Adapting Continuous Load Balancing Processes to Discrete Settings

摘要

We introduce a general method that converts a wide class of continuous neighborhood load balancing algorithms into a discrete version. Assume that initially the tasks are arbitrarily distributed among the nodes of a graph. In every round every node is allowed to communicate and exchange load with an arbitrary subset of its neighbors. The goal is to balance the load as evenly as possible. Continuous load balancing algorithms that are allowed to split tasks arbitrarily can balance the load perfectly, so that every node has exactly the same load. Discrete load balancing algorithms are not allowed to split tasks and therefore cannot balance the load perfectly. 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 neighborhood load balancing algorithm that balances the load perfectly in t rounds, we convert the algorithm into a discrete version. This new algorithm is deterministic and balances the load in t rounds so that the difference between the average and the maximum load is at most 2d·w_(max), where d is the maximum degree of the network and w_(max) is the maximum weight of any task. Compared to the previous methods that work for general graphs , our method achieves asymptotically lower discrepancies (e.g. Ο(1) vs. Ο(log n) for constant-degree expanders and Ο(r) vs. Ο(n~(1/r)) for r-dimensional tori) in the same number of rounds. For the case of uniform weights we present a randomized version of our algorithm balancing the load so that the difference between the minimum and the maximum load is at most Ο( (d log n)~(1/2)) if the initial load on every node is large enough.