Introduisons tout d'abord une relation d'ordre 
$\preceq$  entre les  classes d'équivalences.   
Formellement, \class{p}
$\preceq$   \class{q}   
s'il existe un chemin de longueur   $\alpha$
($0\le\alpha<|\mathcal{K}|$)  entre un élément le la classe
\class{p} vers un élément  de
\class{q}. 

\begin{lemma}
  Il existe un processus de renommage qui affecte un nouvel identifiant aux
  éléments  $i\in$ \class{p}  et $j  \in$ \class{q}  tel que 
  $i  \le  j$ si et seulement si
  \class{p} $\preceq$ \class{q}.
  \begin{proof}
    
    Tout d'abord,  soient  \class{p_1},   \ldots,  \class{p_l}  des   classes 
    contenant respectivement les éléments $n_1$,\ldots,  $n_l$
    qui ne dépendent d'aucune autre classe.  
    Les éléments de  \class{p_1} sont renommés par $1$, \ldots,  $n_1$,
    les éléments  de \class{p_i},   $2  \le   i  \le   l$  sont renommés par 
    $1+
    \Sigma_{k=1}^{i-1}  n_k$, \ldots, $\Sigma_{k=1}^{i}  n_k$. 
    On considère maintenant les classes \class{p_1},  \ldots, \class{p_{l'}} 
    dont les éléments ont été renommés et soit 
    $m$ le plus grand indice des éléments de \class{p_1}, \ldots,
    \class{p_{l'}}.
    Soit une autre classe \class{p} qui dépend exclusivement d'une classe 
    \class{p_i}, $1 \le i \le l'$ et qui contient $k$ éléments. 
    Les éléments de \class{p} sont renommés par  $m+1$, \ldots, $m+k$.
    Ce processus a été appliqué sur  $l'+1$ classes. Il se termine 
    puisqu'il diminue le nombre d'éléments auquel il reste 
    à affecter un numéro. 

    Il reste à montrer que cette méthode de renommage vérifie la propriété 
    énoncée dans le lemme.
    Cette preuve se fait par induction sur la taille  $l$
    du plus grand chemin de dépendance entre les classes.

    Tout d'abord, si \class{p} $\preceq$ \class{q} et \class{q} 
    dépend immédiatement de 
    \class{p},  \textit{i.e.} 
    le chemin le plus long entre les éléments de   \class{p} et les 
    éléments de \class{q} est de longueur 1.  
    En raison de la méthode renommage, chaque numéro d'élément
    \class{q}  est plus grand que tous ceux de  \class{p} et la preuve est 
    établie.
    Soit \class{p} et  \class{q} tels que le plus long chemin de dépendance 
    entre \class{p} et  \class{q} a une longueur de $l+1$.   
    Il existe alors une classe 
    \class{q'} telle que \class{q} 
    dépend immédiatement de  \class{q'} et le chemin de dépendance le
    plus long entre \class{p} et  \class{q'} a pour longueur $l$. 
    On a ainsi
    \class{q'}  $\preceq$ \class{q}  
    et pour tout  $k$, $j$  tels que $k  \in$
    \class{q'} et $j  \in$  \class{q},  $k \le  j$.
    Par hypothèse d'induction, 
    \class{p}  $\preceq$ \class{q'}  et pour chaque  $i$, $k$  tels que $i  \in$
    \class{p} et  $k \in$ \class{q'}, $i \le k$
    et le résultat est établi.
  \end{proof}
\end{lemma}

On peut remarquer que ce processus de renommage est inspiré des \emph{graphes 
  par couches } de Golès et Salinas~\cite{GS08}.

% \begin{xpl}
%   We  have \class{1}  $=\{1,2\}$, \class{3}  $=\{3\}$ and  \class{4} $=\{4,5\}$.
%   Processes numbers are already compliant with the order $\preceq$.
% \end{xpl}

\begin{proof}[du théorème~\ref{th:cvg}]

  Le reste de la preuve est fait par induction sur le numéro de classe. 
  Considérons la première  classe \class{b_1} de $n_1$ éléments 
  \textit{i.e.} la classe avec le plus petit identifiant.

  D'après les hypothèses du  théorème, %following the strategy $(S^t)$,
  les itérations synchrones convergent vers un point fixe en un nombre 
  fini d'itérations. %pseudo periods. % [[JFC : borner m1/n1]].
  Ainsi toutes les  \emph{classes sources} 
  (indépendantes de toutes les  autres classes) vont aussi converger 
  dans le mode mixte. 
  On peut ainsi  supposer que le  mode d'itération mixte avec délais 
  uniformes fait converger les classes \class{b_1},  \ldots, \class{b_k}
  en  un temps $t_k$.
  Par construction, la classe \class{b_{k+1}}  dépend uniquement 
  de certaines classes de  \class{b_1}, \ldots,
  \class{b_k} et éventuellement d'elle-même.
  Il existe un nombre d'itérations suffisamment grand 
  $t_0$  tel que  $D^{t_0}_{p_{k+1}p_j}$  est supérieur ou égal à   $t_k$ 
  pour chaque 
  $p_{k+1} \in$ \class{b_{k+1}} et $p_j \in$ \class{b_j}, $1 \le j \le k$.

  Il ne reste donc que des itérations synchrones entre les 
  éléments  de \class{b_{k+1}} en démarrant dans des configurations
  où tous les éléments de  \class{b_j}, $1 \le j
  \le k$, ont  des valeurs constantes.  
  D'après les hypothèses du théorème, cela converge.
\end{proof}



