We study distributed load balancing problem on arbitrary graphs. First Order (FO) and Second Order (SO) schemes are popular local diffusive schedules for this problem. To use these schemes, several parameters have to be chosen carefully. Determining the "optimal" parameters analytically is difficult, and on a practical level, despite the widespread use of these schemes, little is known on how relevant parameters must be set.

We employ systematic experiments to engineer the choice of relevant parameters in first and second order schemes. Some of our contributions here are as follows. We present a centralized polynomial time algorithm for choosing the "optimal" F0 scheme based on semidefinite programming. Based on the empirical evidence from our implementation of this algorithm, we pose conjectures on the closed-form solution of optimal F0 schemes for various graphs. We also present a heuristic algorithm to locally estimate relevant parameters in the FO and SO schemes; our estimates are fairly accurate compared to those based on expensive global communication. Finally, we show that the FO and SO schemes that use approximate values rather than the optimal parameters, can be improved using a new iterative scheme that we introduce here; this scheme is of independent interest. The software we have developed for our implementations can serve as a platform for experimental research in this area and it will be made available freely. Our methods are being included in PadFEM, the Paderborn Finite Element Library.

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £66 +P&P)