From: Raphael Couturier <raphael.couturier@univ-fcomte.fr>
Date: Wed, 20 Apr 2011 13:52:09 +0000 (+0200)
Subject: suite description algo bertsekas
X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/loba-papers.git/commitdiff_plain/11a214bdac1c00f5f5f8ed9ff672afdb27a23b7d

suite description algo bertsekas
---

diff --git a/supercomp11/supercomp11.tex b/supercomp11/supercomp11.tex
index 6a48cd3..0479906 100644
--- a/supercomp11/supercomp11.tex
+++ b/supercomp11/supercomp11.tex
@@ -1,3 +1,4 @@
+
 \documentclass[smallextended]{svjour3}
 \usepackage[utf8]{inputenc}
 \usepackage[T1]{fontenc}
@@ -143,7 +144,35 @@ 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)
+\label{eq:ping-pong}
+\end{equation}
+
+
+Some  conditions are  required to  ensure the  convergence. One  of them  can be
+called the \texttt{ping-pong} condition which specifies that:
+\begin{equation}
+x_i(t)-\sum _{k\in V(i)} s_{ik}(t) \geq x_j^i(t)+s_{ij}(t)
 \end{equation}
+for any  processor $i$ and any  $j \in V(i)$ such  that $x_i(t)>x_j^i(t)$.  This
+condition aims  at avoiding a processor  to send a  part of its load  and beeing
+less loaded after that.
+
+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 wich 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*}
+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
+$x_3^2(t)$.  So we consider that the \texttt{ping-pong} condition is probably to
+strong. Currently, we did not try to make another convergence proof without this
+condition or with a weaker condition.
 
 
 \section{Best effort strategy}