"Precomputation-based Load Balancing"
Article by Max Böhm, Ewald Speckenmeyer, available as BibTeX Source, postscript file and compressed postscript file.
Informatik, Universität zu Köln
Preprint Key:	zpr96-219
Keywords:	distributed computing, load balancing, satisfiability problem
MSC codes:	68Q25, 68T20, 68W10
This article was published in 1997 by World Scientific in the proceedings "Proc. of the 4th Workshop on Parallel Systems and Algorithms (PASA '96)" (edited by F. Hoss;feld, E. Maehle, E. W. Mayer), number 219, pages 177--194.
Abstract:	An algorithm, called PLB is introduced, which redistributes workload in a processor network N in order to supply every processor of N with (about) the same amount of workload. PLB is defined in its basic form for trees, but can be extended to other topologies. The redistribution is done locally on the basis of information of over- or underload in subnetworks of N. We show, that PLB performs O(d) steps, only, where d denotes the diameter of N, and in the average case at most four times as many workload has to be migrated in complete binary trees compared to clique networks, the best possible networks. We describe an implementation of PLB and present experimental results when solving the Boolean satisfiability problem, demonstrating that PLB performs very well in practice.