From: Raphael Couturier <raphael.couturier@univ-fcomte.fr>
Date: Wed, 20 Apr 2011 09:47:59 +0000 (+0200)
Subject: premiere description de l'algo de bertsekas
X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/loba-papers.git/commitdiff_plain/50f790a50dfec79e4aeabbe564c4c7d375c7d57f?ds=sidebyside

premiere description de l'algo de bertsekas
---

diff --git a/supercomp11/biblio.bib b/supercomp11/biblio.bib
index 6b076af..f671f0c 100644
--- a/supercomp11/biblio.bib
+++ b/supercomp11/biblio.bib
@@ -33,3 +33,15 @@
   month =        dec,
   doi =          {10.1016/S0743-7315(02)00006-0}
 }
+
+
+@Article{ElsMonPre02,
+  author =	"R. Elsässer and B. Monien and R. Preis",
+  title =	"Diffusion Schemes for Load Balancing on Heterogeneous
+		 Networks",
+  journal =	"Theory of computing systems",
+  volume =	"35",
+  number = "3",
+  pages = "305--320",
+  year = 	"2002",
+}
diff --git a/supercomp11/supercomp11.tex b/supercomp11/supercomp11.tex
index d1ff213..4a7e57a 100644
--- a/supercomp11/supercomp11.tex
+++ b/supercomp11/supercomp11.tex
@@ -122,7 +122,29 @@ conclusion and some perspectives to this work.
 \section{Bertsekas  and Tsitsiklis' asynchronous load balancing algorithm}
 \label{BT algo}
 
-Comment on the problem in the convergence condition.
+In  order  prove  the  convergence  of  asynchronous  iterative  load  balancing
+Bertesekas         and        Tsitsiklis         proposed         a        model
+in~\cite{bertsekas+tsitsiklis.1997.parallel}.   Here we  recall  some notations.
+Consider  that  $N={1,...,n}$  processors   are  connected  through  a  network.
+Communication links  are represented by  a connected undirected  graph $G=(N,V)$
+where $V$ is the set of links connecting differents processors. In this work, we
+consider that  processors are  homogeneous for sake  of simplicity. It  is quite
+easy to tackle the  heterogeneous case~\cite{ElsMonPre02}. Load of processor $i$
+at  time $t$  is  represented  by $x_i(t)\geq  0$.   Let $V(i)$  be  the set  of
+neighbors of processor  $i$.  Each processor $i$ has an estimate  of the load of
+each  of its  neighbors $j  \in V(i)$  represented by  $x_j^i(t)$.  According to
+asynchronism and communication  delays, this estimate may be  outdated.  We also
+consider that the load is described by a continuous variable.
+
+When a processor  send a part of its  load to one or some of  its neighbors, the
+transfer takes time to be completed.  Let $s_{ij}(t)$ be the amount of load that
+processor $i$ has transfered to processor $j$ at time $t$ and let $r_{ij}(t)$ be the
+amount of  load received by processor $j$  from processor $i$ at  time $t$. Then
+the amount of load of processor $i$ at time $t+1$ is given by:
+\begin{equation}
+x_i(t+1)=x_i(t)-\sum_{j\in V(i)} s_{ij}(t) + \sum_{j\in V(i)} r_{ji}(t)
+\end{equation}
+
 
 \section{Best effort strategy}
 \label{Best-effort}