X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/loba-papers.git/blobdiff_plain/d4cea59118bd3352b939bf2a01443778b9a2129b..b680616f7e0702003982aa20fd7208c18eba98f1:/supercomp11/supercomp11.tex?ds=inline diff --git a/supercomp11/supercomp11.tex b/supercomp11/supercomp11.tex index 6cd7b58..f975555 100644 --- a/supercomp11/supercomp11.tex +++ b/supercomp11/supercomp11.tex @@ -31,7 +31,8 @@ \begin{abstract} Most of the time, asynchronous load balancing algorithms have extensively been -studied in a theoretical point of view. The Bertsekas and Tsitsiklis' algorithm +studied in a theoretical point of view. The Bertsekas and Tsitsiklis' +algorithm~\cite[section~7.4]{bertsekas+tsitsiklis.1997.parallel} is certainly the most well known algorithm for which the convergence proof is given. From a practical point of view, when a node wants to balance a part of its load to some of its neighbors, the strategy is not described. In this @@ -43,7 +44,7 @@ balancing algorithm is implemented most of the time can dissociate messages concerning load transfers and message concerning load information. In order to increase the converge of a load balancing algorithm, we propose a simple heuristic called \texttt{virtual load} which allows a node that receives an load -information message to integrate the load that it will receive latter in its +information message to integrate the load that it will receive later in its load (virtually) and consequently sends a (real) part of its load to some of its neighbors. In order to validate our approaches, we have defined a simulator based on SimGrid which allowed us to conduct many experiments. @@ -68,10 +69,13 @@ algorithm which is definitively a reference for many works. In their work, they proved that under classical hypotheses of asynchronous iterative algorithms and a special constraint avoiding \texttt{ping-pong} effect, an asynchronous iterative algorithm converge to the uniform load distribution. This work has -been extended by many authors. For example, DASUD propose a version working with -integer load. +been extended by many authors. For example, +DASUD~\cite{cortes+ripoll+cedo+al.2002.asynchronous} propose a version working +with integer load. +\bibliographystyle{spmpsci} +\bibliography{biblio} \end{document}