The Average Diffusion Method for the Load Balancing Problem
Gregory Karagiorgos7
and Nikolaos M. Missirlis7 
| (7) |
Department of Informatics and Telecommunications, University of Athens, Panepistimioupolis, 157 84 Athens, Greece |
Abstract
This paper proposes the Average Diffusion (ADF) method for solving the load balancing problem. It is shown that a sufficient and necessary condition for the ADF method
to converge to the uniform distribution of loads is the induced network of processors to be d-regular, connected and not bipartite. Next, we proceed and apply Fourier analysis determining the convergence factor γ in
terms of the diffusion parameters c
ij (weighted case) when the network of processors is a ring and 2D-torus. It is shown that c
ij = 1/2 and c
ij ∈ (0, 1/2) when the network is a ring and 2D-torus, respectively, thus solving partially the open problem which concerns
the determination of the diffusion parameters c
ij.
Keywords Load balancing - diffusion method - multiple parameters -
d-regular graphs - distributed computing
Research is supported by the Greek General Secretary of Research and Technology (EΠET- II No. 87) and the National and Kapodistrian University of Athens (No.70/4/4917).
References secured to subscribers.