Home | Issues | About JGAA | Instructions for Authors |
Special Issue on Selected Papers from the Engineering and Applications Track of the 12th Annual European Symposium on Algorithms (ESA 2004)
DOI: 10.7155/jgaa.00118
Distributing Unit Size Workload Packages in Heterogeneous Networks
Vol. 10, no. 1, pp. 51-68, 2006. Regular paper.
Abstract The task of balancing dynamically generated work load occurs in a wide
range of parallel and distributed applications. Diffusion based
schemes, which belong to the class of nearest neighbor load balancing
algorithms, are a popular way to address this problem. Originally
created to equalize the amount of arbitrarily divisible load among the
nodes of a static and homogeneous network, they have been generalized
to heterogeneous topologies. Additionally, some simple diffusion
algorithms have been adapted to work in dynamic networks as well.
However, if the load is not divisible arbitrarily but consists of
indivisible unit size tokens, diffusion schemes are not able to
balance the load properly. In this paper we consider the problem of
balancing indivisible unit size tokens on heterogeneous
systems. By modifying a randomized strategy invented for homogeneous
systems, we can achieve an asymptotically minimal expected overload in
l1, l2 and l∞ norm while only slightly increasing the
run-time by a logarithmic factor. Our experiments show that this
additional factor is usually not required in applications.
|
Journal Supporters
|