ALCOMFT-TR-03-152

Robert Elsässer and Burkhard Monien
Load Balancing of Unit Size Tokens and Expansion Properties of Graphs
Paderborn. Work package 2. December 2003.

Abstract: Diffusive schemes have been widely analyzed for parallel and distributed load balancing. It is well known that their convergence rates depend on the eigenvalues of some associated matrices and on the expansion properties of the underlying graphs. In the first part of this paper we make use of these relationships in order to obtain new spectral bounds on the edge and node expansion of graphs. We show that these new bounds are better than the classical bounds for several graph classes. In the second part of the paper, we consider the load balancing problem for indivisible unit size tokens. Since known diffusion schemes do not completely balance the load for such settings, we propose a randomized distributed algorithm based on Markov chains to reduce the load imbalance. We prove that this approach provides the best asymptotic result that can be achieved in l₁- or l₂-norm concerning the final load situation.

Postscript file: ALCOMFT-TR-03-152.ps.gz (102 kb).