A simple approach for adapting continuous load balancing processes to discrete settings
Hoda Akbari, Petra Berenbrink, Thomas Sauerwald · 2012
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.