\JFC{Refaire le châpeau}
\section{Généralisation au cadre asynchrone}
Dans ce chapitre une stratégie $s=(s^{t})^{t \in \Nats}$ est une séquence
\emph{des éléments} qui sont mis à jour au temps $t$. Pratiquement, 
on représente ceci comme un nombre décimal dont la représentation en 
binaire donne la liste des éléments modifiés. Par exemple, pour un système 
à 5 éléments la stratégie définie par 
\begin{equation}\label{eq:pseudo}
s^{t}=24 \textrm{ si  $t$ est pair et  } s^{t}=15 \textrm{ sinon }
\end{equation}
\noindent active successivement les deux premiers éléments (24 est 11000) 
et les quatre derniers élements (15  est  01111).  
On dit que la stratégie est
\emph{pseudo-periodique}  si tous les éléments sont activés infiniment 
souvent.
% , it is sufficient to establish  that the set $\{t \mid t \in \mathbb{N}
% \land \textit{bin}(s^t)[i]  = 1\}$  is infinite for  any $i$,  $1 \le i  \le n$,
% where
% The  synchronous iterations  modes are  defined for  any $i  \in
% \{1,\ldots,n\}$ and any time $t=0,1,2,...$ by:
% \vspace{-.5em}
% \begin{equation}\label{eq:sync}
%   x^{t+1}_i= \left\{
% \begin{array}{l}
% f_i(x^t) \textrm{ if } \textit{bin}(s^t)[i] = 1\\ 
% x^{t}_i \textrm{ otherwise }
% \end{array} 
% \right.
% \end{equation}
% \vspace{-.5em}
% Notice that  parallel iterations only  constrain $s^t$ to be  equal to $2^n-1$
% for any $t$ whereas chaotic iterations do not constrain $s$.
% for  convenient reasons  [[JFC  : a  affiner]],  the set  of components  $\{1,
% \ldots,  n\}$   may  be  partitioned   into  $\alpha$  blocks   $b_1,  \ldots,
% b_{\alpha}$.
% %Elements of $b_i$ are ordered w.r.t. the component number.
% For $1\le i \le \alpha$, let $B_i$ be the product-space of block $i$.
% Formaly, $B_i = \Pi_{j \in b_{i} } E_j$.
% To  ease   the  reading,  lowercase   variable  and  upercase   one  represent
% respectively an element of some $E_i$ and a matrix of elements in some $E_i$.
% The components  may  be updated  (in  a random  order)  according to  a
% strategy $s$, as in the synchronous mode. 
Dans le mode asynchrone, a chaque itération $t$, chaque composant peut
mettre à jour son état en 
fonction des dernières valeurs qu'il connaît des autre composants.
Obtenir où non les valeurs les plus à jours dépent du temps de calcul et 
du temps d'acheminement de celles-ci. On parle de latence, de délai.

Formalisons le mode les itérations asynchrones.
Soit $x^0 =(x_1^0, \ldots, x_n^0)$ une configuration initiale.
Soit $(D^{t})^{t \in  \Nats}$ la suite de matrice de taille $n  \times n$  
dont chaque élément $D_{ij}^{t}$ represente la date (inférieure ou égale à $t$) 
à laquelle la valeur $x_j$ produite par le composant $j$ devient 
disponible au composant $i$. 
On considère que le délai entre l'émission par $j$ et la réception par $i$, 
défini par $\delta_{ij}^t  = t  - D_{ij}^{t}$ est borné par une constante $\delta_0$ pour tous les $i$, $j$.
Le \emph{mode des itérations asynchrones} est défini pour chaque  $i
\in \{1,\ldots,n\}$ et chaque  $t=0,1,2,...$ par:

\vspace{-.5em}
\begin{equation}\label{eq:async}
  x^{t+1}_i= \left\{
    \begin{array}{l}
      f_i( x_1^{D_{i1}^t},\ldots, x_{n}^{D_{i{n}}^t})
      \textrm{ if } \textit{bin}(s^t)[i] = 1\\ 
      x^{t}_i  \textrm{ sinon }
    \end{array} 
  \right.
\end{equation}

\noindent où $\textit{bin}$ convertit un entier en un nombre binaire.
Les itérations de $f$ sont \emph{convergentes} modulo une configuration 
initiale  $x^0$,  une  stratégi $s$ et une matrice de dates  $(D^{t})^{t  \in
  \Nats}$, si la fonction atteint un point fixe.
Cela revient à vérifier la propriété suivante:
\begin{equation}\label{eq:conv}      
\exists t_0 \,.\, 
(\forall t  \,.\,
t \geq t_0  \Rightarrow  x^{t}=x^{t_0}).
\end{equation}
Sinon les itérations sont dites \emph{divergentes}.
De plus, si $ (x^{(t)})^{t \in \mathbb{N}}$ défini  selon l'équation 
\Equ{eq:async} satisfait \Equ{eq:conv}  pour tous les  $x^{(0)}
\in  E$,  pour toutes les stratégies pseudo périodiques 
$s$  et pour toutes les matrices de dates,
$(D^{(t)})^{t  \in \Nats}$, alors les itérations de  $f$ sont 
\emph{universellement convergentes}.


\section{Exemple jouet}
On considère cinq éléments prenant à valeurs dans $\Bool$. 
Une configuration dans $\Bool^5$ est représentée par un entier entre 
0 et 31. La~\Fig{fig:mix:map} donne la fonction définissant la dynamique du 
système. La~\Fig{fig:mix:xplgraph} donne le graphe d'intéraction associé à cette fonction.
On note que le graphe d'intéraction contient cinq cycles. Les résultats 
connus~\cite{Bah00} de conditions suffisantes établissant la convergencedu système pour les itérations synchrones et asynchrones sont basés sur l'absence de cycles. Ils ne peuvent donc pas être appliqués ici.

\begin{figure}[ht]
\begin{minipage}[b]{0.55\linewidth}
  \centering
  $ f(x)= \left \{
    \begin{array}{lll}
      f_1(x_1,x_2,x_3,x_4,x_5) & = & x_1.\overline{x_2} + \overline{x_1}.x_2 \\
      f_2(x_1,x_2,x_3,x_4,x_5) & = & \overline{x_1 + x_2}  \\
      f_3(x_1,x_2,x_3,x_4,x_5) & = & x_3.\overline{x_1} \\
      f_4(x_1,x_2,x_3,x_4,x_5) & = & x_5  \\
      f_5(x_1,x_2,x_3,x_4,x_5) & = & \overline{x_3} + x_4
    \end{array}
  \right.  $
\caption{Fonction $f$ de l'exemple jouet.}
\label{fig:mix:map}
\end{minipage}\hfill
\begin{minipage}[b]{.40\linewidth}
  \begin{center}
    \includegraphics[scale=0.55]{images/xplgraphmix.eps}
  \end{center}
  \caption{Graphe d'interaction associé à $f$.}
  \label{fig:mix:xplgraph}
\end{minipage}
\end{figure}


\begin{figure}
\begin{minipage}{0.56\linewidth}
  \includegraphics[scale=0.55]{images/para_iterate_dec.eps}
  \caption{Itérations parallèlles de $f$.}\label{fig:mix:xplparaFig}
\end{minipage}
\hfill
\begin{minipage}{0.39\linewidth}
  \includegraphics[scale=0.55]{images/chao_iterate_excerpt.eps}
  \caption{Extrait d'itérations chaotiques.}
  \label{fig:mix:xplchaoFig}
\end{minipage}
\end{figure}

Dans ce qui suit, les  configurations  sont representées à l'aide d'entiers 
plutôt que nombres binaires. Le graphe des itérations parallèles est donné 
en~\Fig{fig:mix:xplparaFig}. Depuis n'importe quelle configuration, on constate 
qu'il converge vers le point fixe correspondant à l'entier 19.
Un extrait du graphe des itérations chaotiques est donné à 
la~\Fig{fig:mix:xplchaoFig}. Les libélés des arcs correspondent aux éléments 
activés. Les itérations chaotiques ne convergent pas pour la stratégie 
pseudo périodique donnée à l'équation~\Equ{eq:pseudo}:
le système peut infiniment boucler entre 11 et 3, entre 15 et 7.   

Comme les itérations chaotiques ne convergent pas pour certaines stratégies,
les itérations asynchrones basées sur les même stratégies peuvent ne pas 
converger aussi. Cependant, même si l'on considère que tous les composants 
sont activés à chaque itération, c'est à dire si $s^t$ est 
constamment égal à $2^n-1$, le délais peut introduire de la divergence.






  For instance, consider the matrix $D^t$ to be equal to $(t)$ except
in $D^t_{12}$  where it is equal  to $t-1$ if $t$  is odd. Then if  $t$ is even,
$x^{t+1}$ is $f(x^{t})$; if $t$ is odd we have
$$
x^{t+1}  = \left(
f_1(x_1^{t},x_2^{t-1},x_3^{t},x_4^{t},x_5^{t}), f_2(x^{t}), \ldots, 
f_5(x^{t})
\right).
$$
\noindent Starting from $x^0=00011$, the system reaches $x^1 = 01011$ and enters
in  a  cycle  between these  two  configurations.   We  are then  confronted  to
divergent asynchronous iterations whereas the synchronous ones converge.  In the
next  section,   a  particular  execution   mode  is  described   which  enables
asynchronism in iterations while guaranteeing the convergence.


