| Tight Analyses Of Two Local Load Balancing Algorithms (1995) | |||||||||||||||||
Abstract | |||||||||||||||||
| . This paper presents an analysis of the following load balancing algorithm. At each step, each node in a network examines the number of tokens at each of its neighbors and sends a token to each neighbor with at least 2d + 1 fewer tokens, where d is the maximum degree of any node in the network. We show that within O(\Delta=ff) steps, the algorithm reduces the maximum difference in tokens between any two nodes to at most O((d 2 log n)=ff), where \Delta is the maximum difference between the number tokens at any node initially and the average number of tokens, n is the number of nodes in the network, and ff is the edge expansion of the network. The time bound is tight in the sense that for any graph with edge expansion ff, and for any value \Delta, there exists an initial distribution of tokens with imbalance \Delta for which the time to reduce the imbalance to even \Delta=2 is at least \Omega\Gammaa =ff). The bound on the final imbalance is tight in the sense that there exists a cl... | |||||||||||||||||
Details der Publikation | |||||||||||||||||
| |||||||||||||||||