Geodesic
Distributing Unit Size Workload Packages in Heterogeneous Networks
Journal of Graph Algorithms and Applications, Special Issue on Selected Papers from the Engineering and Applications Track of the 12th Annual European Symposium on Algorithms (ESA 2004) , Tome 10 (2006) no. 1, pp. 51-68.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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. 
@article{JGAA_2006_10_1_a2,
     author = {Robert Els\"asser and Burkhard Monien and Stefan Schamberger},
     title = {Distributing {Unit} {Size} {Workload} {Packages} in {Heterogeneous} {Networks}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {51--68},
     publisher = {mathdoc},
     volume = {10},
     number = {1},
     year = {2006},
     doi = {10.7155/jgaa.00118},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00118/}
}
TY  - JOUR
AU  - Robert Elsässer
AU  - Burkhard Monien
AU  - Stefan Schamberger
TI  - Distributing Unit Size Workload Packages in Heterogeneous Networks
JO  - Journal of Graph Algorithms and Applications
PY  - 2006
SP  - 51
EP  - 68
VL  - 10
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00118/
DO  - 10.7155/jgaa.00118
LA  - en
ID  - JGAA_2006_10_1_a2
ER  - 
%0 Journal Article
%A Robert Elsässer
%A Burkhard Monien
%A Stefan Schamberger
%T Distributing Unit Size Workload Packages in Heterogeneous Networks
%J Journal of Graph Algorithms and Applications
%D 2006
%P 51-68
%V 10
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00118/
%R 10.7155/jgaa.00118
%G en
%F JGAA_2006_10_1_a2
Robert Elsässer; Burkhard Monien; Stefan Schamberger. Distributing Unit Size Workload Packages in Heterogeneous Networks. Journal of Graph Algorithms and Applications, 
							Special Issue on Selected Papers from the Engineering and Applications Track of the 12th Annual European Symposium on Algorithms (ESA 2004)
					, Tome 10 (2006) no. 1, pp. 51-68. doi : 10.7155/jgaa.00118. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00118/

Cité par Sources :