Dimension-Exchange Algorithms for Load Balancing on Trees.
Michael E. Houle, Antonios Symvonis, David R. Wood · 2002
This paper considers dimension-exchange algorithms for load balanc- ing on trees with finitely-divisible loads ( token distribution). We present im- proved analysis of an existing protocol, and in particular, establish a loga- rithmic upper bound on the discrepancy of the final distribution. Our second contribution is a new algorithm, which assuming each node has knowledge of the total number of