]> AND Private Git Repository - loba-papers.git/commitdiff
Logo AND Algorithmique Numérique Distribuée

Private GIT Repository
premiere description de l'algo de bertsekas
authorRaphael Couturier <raphael.couturier@univ-fcomte.fr>
Wed, 20 Apr 2011 09:47:59 +0000 (11:47 +0200)
committerRaphael Couturier <raphael.couturier@univ-fcomte.fr>
Wed, 20 Apr 2011 09:47:59 +0000 (11:47 +0200)
supercomp11/biblio.bib
supercomp11/supercomp11.tex

index 6b076af64b3df41705fea616e8345e1009d3a754..f671f0cd000ef3e4f7343b5a481f3213299ef249 100644 (file)
   month =        dec,
   doi =          {10.1016/S0743-7315(02)00006-0}
 }
   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",
+}
index d1ff213f5c40139afc57faf9790cf454145749f6..4a7e57a42bfccc81c3133734063ad0cf6ce3b4bf 100644 (file)
@@ -122,7 +122,29 @@ conclusion and some perspectives to this work.
 \section{Bertsekas  and Tsitsiklis' asynchronous load balancing algorithm}
 \label{BT algo}
 
 \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}
 
 \section{Best effort strategy}
 \label{Best-effort}