X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/loba-papers.git/blobdiff_plain/d883af6fcab703af629fd6ca368b7076b5b3384a..2216578e9740572a34f3064af72777d9fc281fe2:/supercomp11/supercomp11.tex

diff --git a/supercomp11/supercomp11.tex b/supercomp11/supercomp11.tex
index d1ff213..6a48cd3 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}
@@ -135,9 +157,17 @@ Comment on the problem in the convergence condition.
 \section{Simulations}
 \label{Simulations}
 
+In order to test and validate our approaches, we wrote a simulator
+using the SimGrid
+framework~\cite{casanova+legrand+quinson.2008.simgrid}.  The process
+model is detailed in the next section (\ref{Sim model}), then the
+results of the simulations are presented in section~\ref{Results}.
+
 \subsection{Simulation model}
+\label{Sim model}
 
 \subsection{Validation of our approaches}
+\label{Results}
 
 
 On veut montrer quoi ? :