--- /dev/null
+\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
