X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/loba-papers.git/blobdiff_plain/77dfff6971a1d64b3274379ad340410840d24980..bcf6cef9fa1df52f632849a68fc08e41f6163bb1:/supercomp11/supercomp11.tex?ds=inline diff --git a/supercomp11/supercomp11.tex b/supercomp11/supercomp11.tex index b0d23b0..81ee704 100644 --- a/supercomp11/supercomp11.tex +++ b/supercomp11/supercomp11.tex @@ -75,9 +75,11 @@ 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 \emph{ping-pong} effect, an asynchronous iterative algorithm converge to the uniform load distribution. This work has -been extended by many authors. For example, -DASUD~\cite{cortes+ripoll+cedo+al.2002.asynchronous} propose a version working -with integer load. {\bf Rajouter des choses ici}. +been extended by many authors. For example, Cortés et al., with +DASUD~\cite{cortes+ripoll+cedo+al.2002.asynchronous}, propose a +version working with integer load. This work was later generalized by +the same authors in \cite{cedo+cortes+ripoll+al.2007.convergence}. +{\bf Rajouter des choses ici}. Although the Bertsekas and Tsitsiklis' algorithm describes the condition to ensure the convergence, there is no indication or strategy to really implement @@ -183,12 +185,13 @@ condition or with a weaker condition. \section{Best effort strategy} \label{Best-effort} -We will describe here a new load-balancing strategy that we called -\emph{best effort}. The general idea behind this strategy is, for a -processor, to send some load to the most of its neighbors, doing its +In this section we describe a new load-balancing strategy that we call +\emph{best effort}. The general idea behind this strategy is that each +processor, that detects it has more load than some of its neighbors, +sends some load to the most of its less loaded neighbors, doing its best to reach the equilibrium between those neighbors and himself. -More precisely, when a processors $i$ is in its load-balancing phase, +More precisely, when a processor $i$ is in its load-balancing phase, he proceeds as following. \begin{enumerate} \item First, the neighbors are sorted in non-decreasing order of their