\documentclass[a4paper]{article}

\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\usepackage{lmodern}
\usepackage{amsmath}
%\usepackage{amsthm}
%\usepackage{amsfonts}
\usepackage[english,frenchb]{babel}

% intervalles
\newcommand*{\intFF}[2]{\mathopen[ #1 \mathrel; #2 \mathclose]}
\newcommand*{\intFO}[2]{\mathopen[ #1 \mathrel; #2 \mathclose[}
\newcommand*{\intOF}[2]{\mathopen] #1 \mathrel; #2 \mathclose]}
\newcommand*{\intOO}[2]{\mathopen] #1 \mathrel; #2 \mathclose[}

\newcommand*{\vxi}{x_i(t)}
\newcommand*{\vxij}{x_j^i(t)}
\newcommand*{\vxik}{x_k^i(t)}
\newcommand*{\sij}{s_{ij}(t)}
\newcommand*{\sik}{s_{ik}(t)}

\begin{document}

%\author{Arnaud Giersch}
%\title{}
%\date{}


\section*{Objectif}

Notre objectif est de concevoir et d'étudier des solutions
d'équilibrage de charge par diffusion asynchrone.  Pour cela, on a
cherché à s'appuyer sur des travaux de Bertsekas et
Tsitsiklis~\cite[section~7.4]{bertsekas+tsitsiklis.1997.parallel}.
Ces auteurs présentent des hypothèses sous lesquelles l'algorithme
itératif est garanti de converger.  Nous avons alors cherché des
fonctions de diffusion respectant ces hypothèses.

Nous allons exhiber ici un exemple simple pour lequel les points~(a)
et~(b) de l'hypothèse~4.2 de Bertsekas et Tsitsiklis sont
contradictoires.

\section*{Contre-exemple}

Nous utilisons ici les mêmes notations que Bertsekas et Tsitsiklis.
Soient trois processeurs : $i$, $j$ et $k$ tels que $A(i) = \{j, k\}$.
Soit $\alpha$, une constante telle que $\alpha \in \intOO{0}{1}$.  Il
s'agit du même $\alpha$ que celui dont il est question dans
l'hypothèse~4.2(a) de Bertsekas et Tsitsiklis.  Nous supposons que
$\vxi > \vxij$ et $\vxi > \vxik$.  Supposons de plus que:
\begin{equation}
  \label{eq.hyp}
  \vxik > \vxi - \alpha (\vxi - \vxij)
  \text{.}
\end{equation}

On montre facilement que $\vxi - \vxik < \alpha (\vxi - \vxij) < \vxi
- \vxij$ et par conséquent que $\vxij < \vxik$.  Intuitivement,
l'équation~(\ref{eq.hyp}) exprime le fait que, par rapport à $\vxij$,
$\vxik$ est très proche de $\vxi$.

\medskip

D'après la proposition~4.1 de Bertsekas et Tsitsiklis, l'algorithme
d'équilibrage de charge converge si l'hypothèse~4.2 est vérifiée.
Ainsi, par le point~(a) de l'hypothèse~4.2, on doit vérifier que:
\begin{equation}
  \label{eq.sij}
  \sij \geq \alpha (\vxi - \vxij)
  \text{.}
\end{equation}
Par le point~(b) de la même hypothèse, il faut vérifier que:
\begin{equation*}
  \vxi - \sij - \sik \geq \vxik + \sik
  \text{.}
\end{equation*}
Comme, par définition, $\sik \geq 0$, on en déduit que:
\begin{equation*}
   \vxik \leq \vxik + \sik \leq \vxi - \sij - \sik \leq \vxi - \sij
\end{equation*}
et donc, par l'équation~(\ref{eq.sij}), que:
\begin{equation*}
  \vxik \leq \vxi - \alpha (\vxi - \vxij)
  \text{.}
\end{equation*}
Cette dernière équation est en contradiction avec l'hypothèse de
départ donnée par l'équation~(\ref{eq.hyp}).

Il est donc impossible, si l'équation~(\ref{eq.hyp}) est vérifiée, de
trouver $\sij$ et $\sik$ respectant l'hypothèse~4.2 de Bertsekas et
Tsitsiklis.

\medskip

De plus, si les trois proceseurs sont organisés en ligne : une
connexion entre $i$ et $j$ et une connexion entre $i$ et $k$, avec
$x_i^j \geq x_j$ et $x_i^k \geq x_k$, le système ne pourra plus
évoluer car alors $s_{ji} = 0$ et $s_{ki} = 0$ (hypothèse 4.2(a)).

\NoAutoSpaceBeforeFDP
\begin{thebibliography}{1}

\bibitem{bertsekas+tsitsiklis.1997.parallel}
Dimitri~P. Bertsekas et John~N. Tsitsiklis.
\newblock \foreignlanguage{english}%
          {\em Parallel and Distributed Computation: Numerical Methods}.
\newblock Athena Scientific, 1997.

\end{thebibliography}
\AutoSpaceBeforeFDP

\end{document}

% LocalWords:  Bertsekas Tsitsiklis biblio donne-t-elle
