contre-exemple.tex

   1 \documentclass[a4paper]{article}
   2
   3 \usepackage[T1]{fontenc}
   4 \usepackage[latin1]{inputenc}
   5 \usepackage{lmodern}
   6 \usepackage{amsmath}
   7 %\usepackage{amsthm}
   8 %\usepackage{amsfonts}
   9 \usepackage[english,frenchb]{babel}
  10
  11 % intervalles
  12 \newcommand*{\intFF}[2]{\mathopen[ #1 \mathrel; #2 \mathclose]}
  13 \newcommand*{\intFO}[2]{\mathopen[ #1 \mathrel; #2 \mathclose[}
  14 \newcommand*{\intOF}[2]{\mathopen] #1 \mathrel; #2 \mathclose]}
  15 \newcommand*{\intOO}[2]{\mathopen] #1 \mathrel; #2 \mathclose[}
  16
  17 \newcommand*{\vxi}{x_i(t)}
  18 \newcommand*{\vxij}{x_j^i(t)}
  19 \newcommand*{\vxik}{x_k^i(t)}
  20 \newcommand*{\sij}{s_{ij}(t)}
  21 \newcommand*{\sik}{s_{ik}(t)}
  22
  23 \begin{document}
  24
  25 %\author{Arnaud Giersch}
  26 %\title{}
  27 %\date{}
  28
  29
  30 \section*{Objectif}
  31
  32 Notre objectif est de concevoir et d'étudier des solutions
  33 d'équilibrage de charge par diffusion asynchrone.  Pour cela, on a
  34 cherché à s'appuyer sur des travaux de Bertsekas et
  35 Tsitsiklis~\cite[section~7.4]{bertsekas+tsitsiklis.1997.parallel}.
  36 Ces auteurs présentent des hypothèses sous lesquelles l'algorithme
  37 itératif est garanti de converger.  Nous avons alors cherché des
  38 fonctions de diffusion respectant ces hypothèses.
  39
  40 Nous allons exhiber ici un exemple simple pour lequel les points~(a)
  41 et~(b) de l'hypothèse~4.2 de Bertsekas et Tsitsiklis sont
  42 contradictoires.
  43
  44 \section*{Contre-exemple}
  45
  46 Nous utilisons ici les mêmes notations que Bertsekas et Tsitsiklis.
  47 Soient trois processeurs : $i$, $j$ et $k$ tels que $A(i) = \{j, k\}$.
  48 Soit $\alpha$, une constante telle que $\alpha \in \intOO{0}{1}$.  Il
  49 s'agit du même $\alpha$ que celui dont il est question dans
  50 l'hypothèse~4.2(a) de Bertsekas et Tsitsiklis.  Nous supposons que
  51 $\vxi > \vxij$ et $\vxi > \vxik$.  Supposons de plus que:
  52 \begin{equation}
  53   \label{eq.hyp}
  54   \vxik > \vxi - \alpha (\vxi - \vxij)
  55   \text{.}
  56 \end{equation}
  57
  58 On montre facilement que $\vxi - \vxik < \alpha (\vxi - \vxij) < \vxi
  59 - \vxij$ et par conséquent que $\vxij < \vxik$.  Intuitivement,
  60 l'équation~(\ref{eq.hyp}) exprime le fait que, par rapport à $\vxij$,
  61 $\vxik$ est très proche de $\vxi$.
  62
  63 \medskip
  64
  65 D'après la proposition~4.1 de Bertsekas et Tsitsiklis, l'algorithme
  66 d'équilibrage de charge converge si l'hypothèse~4.2 est vérifiée.
  67 Ainsi, par le point~(a) de l'hypothèse~4.2, on doit vérifier que:
  68 \begin{equation}
  69   \label{eq.sij}
  70   \sij \geq \alpha (\vxi - \vxij)
  71   \text{.}
  72 \end{equation}
  73 Par le point~(b) de la même hypothèse, il faut vérifier que:
  74 \begin{equation*}
  75   \vxi - \sij - \sik \geq \vxik + \sik
  76   \text{.}
  77 \end{equation*}
  78 Comme, par définition, $\sik \geq 0$, on en déduit que:
  79 \begin{equation*}
  80    \vxik \leq \vxik + \sik \leq \vxi - \sij - \sik \leq \vxi - \sij
  81 \end{equation*}
  82 et donc, par l'équation~(\ref{eq.sij}), que:
  83 \begin{equation*}
  84   \vxik \leq \vxi - \alpha (\vxi - \vxij)
  85   \text{.}
  86 \end{equation*}
  87 Cette dernière équation est en contradiction avec l'hypothèse de
  88 départ donnée par l'équation~(\ref{eq.hyp}).
  89
  90 Il est donc impossible, si l'équation~(\ref{eq.hyp}) est vérifiée, de
  91 trouver $\sij$ et $\sik$ respectant l'hypothèse~4.2 de Bertsekas et
  92 Tsitsiklis.
  93
  94 \medskip
  95
  96 De plus, si les trois proceseurs sont organisés en ligne : une
  97 connexion entre $i$ et $j$ et une connexion entre $i$ et $k$, avec
  98 $x_i^j \geq x_j$ et $x_i^k \geq x_k$, le système ne pourra plus
  99 évoluer car alors $s_{ji} = 0$ et $s_{ki} = 0$ (hypothèse 4.2(a)).
 100
 101 \NoAutoSpaceBeforeFDP
 102 \begin{thebibliography}{1}
 103
 104 \bibitem{bertsekas+tsitsiklis.1997.parallel}
 105 Dimitri~P. Bertsekas et John~N. Tsitsiklis.
 106 \newblock \foreignlanguage{english}%
 107           {\em Parallel and Distributed Computation: Numerical Methods}.
 108 \newblock Athena Scientific, 1997.
 109
 110 \end{thebibliography}
 111 \AutoSpaceBeforeFDP
 112
 113 \end{document}
 114
 115 % LocalWords:  Bertsekas Tsitsiklis biblio donne-t-elle