X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/loba-papers.git/blobdiff_plain/59636878becb2087601db617b593fd3f35181655..f1aa5b9dfdd4ecd85ea65ea01584c8c452d8acec:/loba-besteffort/loba-besteffort.tex?ds=sidebyside

diff --git a/loba-besteffort/loba-besteffort.tex b/loba-besteffort/loba-besteffort.tex
index 3ccb2b0..2d37f5f 100644
--- a/loba-besteffort/loba-besteffort.tex
+++ b/loba-besteffort/loba-besteffort.tex
@@ -87,7 +87,8 @@
 Load  balancing algorithms  are  extensively used  in  parallel and  distributed
 applications in  order to  reduce the  execution times. They  can be  applied in
 different scientific  fields from high  performance computation to  micro sensor
-networks.   They are  iterative by  nature.  In  literature many  kinds  of load
+networks.   They are  iterative by  nature.\FIXME{really?}
+In  literature many  kinds  of load
 balancing  algorithms  have been  studied.   They  can  be classified  according
 different  criteria:   centralized  or  decentralized,  in   static  or  dynamic
 environment,  with  homogeneous  or  heterogeneous load,  using  synchronous  or
@@ -115,11 +116,11 @@ ensuring that all the nodes concerned  by the load balancing phase have the same
 amount of  load.  Moreover, when real asynchronous  applications are considered,
 using  asynchronous   load  balancing   algorithms  can  reduce   the  execution
 times. Most of the times, it is simpler to distinguish load information messages
-from  data  migration  messages.  Former  ones  allows  a  node to  inform  its
+from  data  migration  messages.  Former  ones  allow  a  node to  inform  its
 neighbors of its  current load. These messages are very small,  they can be sent
-quite often.  For example, if an  computing iteration takes  a significant times
+quite often.  For example, if a computing iteration takes  a significant times
 (ranging from seconds to minutes), it is possible to send a new load information
-message at each  neighbor at each iteration. Latter  messages contains data that
+message to each  neighbor at each iteration. Latter  messages contain data that
 migrates from one node to another one. Depending on the application, it may have
 sense or not  that nodes try to balance  a part of their load  at each computing
 iteration. But the time to transfer a load message from a node to another one is
@@ -129,14 +130,12 @@ it can take this information into account  and it can consider that its new load
 is larger.   Consequently, it can  send a part  of it real  load to some  of its
 neighbors if required. We call this trick the \emph{virtual load} mechanism.
 
-
-
-So, in  this work, we propose a  new strategy for improving  the distribution of
-the  load  and  a  simple  but  efficient trick  that  also  improves  the  load
-balancing. Moreover, we have conducted  many simulations with SimGrid in order to
-validate our improvements are really efficient. Our simulations consider that in
-order  to send a  message, a  latency delays  the sending  and according  to the
-network  performance and  the message  size, the  time of  the reception  of the
+So, in this work, we propose a new strategy to improve the distribution of the
+load and a simple but efficient trick that also improves the load
+balancing. Moreover, we have conducted many simulations with SimGrid in order to
+validate that our improvements are really efficient. Our simulations consider
+that in order to send a message, a latency delays the sending and according to
+the network performance and the message size, the time of the reception of the
 message also varies.
 
 In the following of this paper, Section~\ref{sec.bt-algo} describes the
@@ -159,8 +158,8 @@ In  order  prove  the  convergence  of  asynchronous  iterative  load  balancing
 Bertsekas         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 different processors. In this work, we
+Communication links  are represented by  a connected undirected  graph $G=(N,A)$
+where $A$ is the set of links connecting different 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
@@ -193,12 +192,12 @@ Nevertheless,  we  think that  this  condition may  lead  to  deadlocks in  some
 cases. For example, if we consider  only three processors and that processor $1$
 is linked to processor $2$ which is  also linked to processor $3$ (i.e. a simple
 chain which 3 processors). Now consider we have the following values at time $t$:
-\begin{eqnarray*}
-x_1(t)=10   \\
-x_2(t)=100   \\
-x_3(t)=99.99\\
- x_3^2(t)=99.99\\
-\end{eqnarray*}
+\begin{align*}
+  x_1(t)   &= 10    \\
+  x_2(t)   &= 100   \\
+  x_3(t)   &= 99.99 \\
+  x_3^2(t) &= 99.99 \\
+\end{align*}
 In this case, processor $2$ can either sends load to processor $1$ or processor
 $3$.  If it sends load to processor $1$ it will not satisfy condition
 (\ref{eq.ping-pong}) because after the sending it will be less loaded that
@@ -307,7 +306,7 @@ a load balancing decision, it starts by sorting its neighbors by increasing
 order of their load.  Then, it computes the difference between its own load, and
 the load of each of its neighbors.  Finally, taking the neighbors following the
 order defined before, the amount of load to send $s_{ij}$ is computed as
-$1/(N+1)$ of the load difference, with $N$ being the number of neighbors.  This
+$1/(n+1)$ of the load difference, with $n$ being the number of neighbors.  This
 process continues as long as the node is more loaded than the considered
 neighbor.
 
