From: Arnaud Giersch <arnaud.giersch@iut-bm.univ-fcomte.fr>
Date: Tue, 1 Jun 2010 07:59:45 +0000 (+0200)
Subject: Ajout du contre-exemple à B&T.
X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/equilibrage.git/commitdiff_plain/aaff6f1d1dd08bcbc9623a9fa92e50dc56daa0e3?ds=sidebyside;hp=ca2431052036182f0fc8544f8ba18a6446c2fc40

Ajout du contre-exemple à B&T.
---

diff --git a/contre-exemple.tex b/contre-exemple.tex
new file mode 100644
index 0000000..550b12e
--- /dev/null
+++ b/contre-exemple.tex
@@ -0,0 +1,115 @@
+\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