TI Distributed Load Balancing and Random Walks in Graphs 

LT 90-013 

YR 1990 

AU Jacques E. Boillat 

AV ftp iam.unibe.ch:TechReports1990iam-90-013.ps.Z 

AB We present a fully distributed dynamic load balancing
algorithm for MIMD architectures.  We show that the algorithm can
be interpreted as a multiple random walk of the processes to be
distributed.  The random walk is analyzed using Markov chain
techniques.  We prove the that the algorithm converges in
polynomial time resulting in global load balance.