images/xpl.tex

   1 \begin{xpl}
   2   Without  loss  of generality,  we  consider  Boolean  domains.  We  have  three
   3   elements taking their value in the set $\{0,1\}$.  Thus, a configuration is an
   4   element of  $\{0,1\}^3$, \textit{i.e.},  a binary  number between 0  and 7. In
   5   \Fig{fig:map}   is    given   the   function   defining    the   dynamic   and
   6   \Fig{fig:xplgraph}  depicts   its  associated  connection   graph.   Operators
   7   $\overline{a}$, sum and  product are the classical Boolean  operators.  In the
   8   incidence graph,  or connection  graph, the vertices  are the elements  of the
   9   system and an edge from $i$ to $j$ indicates that $f_j$ depends on $i$. Notice
  10   that  the connection  graph contains  five cycles.
  11
  12 \begin{figure}[ht]
  13   \centering
  14   \subfloat[Maps]{
  15     \begin{minipage}%[h]
  16 {.6\linewidth}
  17       \begin{center}
  18         %\vspace{1.6em}
  19         $ F(X)= \left \{
  20 %         \begin{array}{rcl}
  21 %           f_1(x_1,x_2,x_3) & = & x_1.(x_2 + x_3)  \\
  22 %           f_2(x_1,x_2,x_3) & = & \overline{x_1}.\overline{x_2}.x_3 \\
  23 %           f_3(x_1,x_2,x_3) & = & x_1.x_2.x_3
  24 %         \end{array}
  25          \begin{array}{rcl}
  26            f_1(x_1,x_2,x_3) & = & x_1.\overline{x_2} + x_3  \\
  27            f_2(x_1,x_2,x_3) & = & x_1 + \overline{x_3} \\
  28            f_3(x_1,x_2,x_3) & = & x_2.x_3
  29          \end{array}
  30         \right.
  31         $
  32         %\vspace{1.6em}
  33       \end{center}
  34     \end{minipage}
  35     \label{fig:map}
  36   }
  37   \subfloat[Connexion Graph]{
  38     \begin{minipage}%[h]
  39 {.35\linewidth}
  40       \begin{center}
  41         \includegraphics[width=4cm]{xplCnx.pdf}
  42       \end{center}
  43     \end{minipage}
  44     \label{fig:xplgraph}
  45   }
  46 %  \vspace{-.5em}
  47   \caption{Dynamic of the running example.}
  48   %\vspace{-2em}
  49 \end{figure}
  50
  51 % \begin{figure}
  52 % \begin{center}
  53 % %\includegraphics[width=3cm]{xplgraph.ps}
  54 % \includegraphics[width=3cm]{xplgraph.pdf}
  55 % \end{center}
  56 % \caption{Incidence graph of running example\label{fig:xplgraph}}
  57 % \end{figure}
  58
  59
  60 % \begin{figure}
  61 % \begin{center}
  62 % \includegraphics[width=3cm]{xplgraph.ps}
  63 % %\includegraphics[width=3cm]{xplgraph.pdf}
  64 % \end{center}
  65 % \caption{Incidence graph of running example\label{fig:xplgraph}}
  66 % \end{figure}
  67
  68
  69 % The prototype developed for~\cite{BCVC10:ir} has shown
  70 % that pure parallel iterations are convergent.
  71 % It has helped us to find pseudo-periodic strategies making chaotic
  72 % iterations (and then asynchronous iterations) diverging.
  73 % This example shows then a case when convergence is established
  74 % under some conditions whereas universal convergence is not.
  75
  76 % \begin{figure}[ht]
  77 % \begin{center}
  78 % \includegraphics[width=12cm]{implementation/para_iterate_dec.ps}
  79 % \end{center}
  80 % \caption{Parallel iterations of running example\label{fig:xplparaFig}}
  81 % \end{figure}
  82
  83 % In  what follows  and for  brevity  reasons, configurations  are represented  as
  84 % decimal numbers instead of binary  numbers.  The graph of parallel iterations is
  85 % given in Fig.~\ref{fig:xplparaFig}.
  86 % Starting  from any configuration, the network
  87 % converges to the fixed point corresponding to the decimal number 19.
  88
  89 % \begin{figure}[ht]
  90 % \begin{center}
  91 % \includegraphics[width=4cm]{chao_iterate_excerpt.ps}
  92 % \end{center}
  93 % \caption{Excerpt of chaotic iterations of running example
  94 % \label{fig:xplchaoFig}}
  95 % \end{figure}
  96
  97 % An extract of the  graph of  chaotic iterations  is given  in  Fig.~\ref{fig:xplchaoFig}.
  98 % Arc  label is  the  characteristic function  of  activated elements
  99 % (i.e. the matrix $J^t$)  expressed as  a
 100 % decimal number.  It  allows us to shortly represent  the strategy.
 101 % For instance,
 102 %  in this graph we only consider the pseudo-periodic strategy that  alternately activates  both the
 103 % first two elements and the last four elements.  This is formalized as
 104 % $ J^{2p} =
 105 % \left(
 106 % \begin{array}{lllll}
 107 % 1&0 &0 &0 &0  \\
 108 % 0&1 &0 &0 &0  \\
 109 % 0&0 &0 &0 &0  \\
 110 % 0&0 &0 &0 &0  \\
 111 % 0&0 &0 &0 &0
 112 % \end{array}
 113 % \right)
 114 % $
 115 % and
 116 % $J^{2p+1} =
 117 % \left(
 118 % \begin{array}{lllll}
 119 % 0&0 &0 &0 &0  \\
 120 % 0&1 &0 &0 &0  \\
 121 % 0&0 &1 &0 &0  \\
 122 % 0&0 &0 &1 &0  \\
 123 % 0&0 &0 &0 &1
 124 % \end{array}
 125 % \right)
 126 % $, $p=0,1,2,\ldots$.
 127 % The former matrix is represented as 24 and the later as 15.
 128
 129 % Iterations  do not  converge  for this strategy: for  instance,
 130 % starting from the configuration 3 (resp. configuration 7), the  network goes to the configuration 11 (resp. configuration 15) and
 131 % goes back to the configuration 3 (resp. configuration 7) by applying the strategy depicted above.
 132
 133
 134 % Since chaotic iterations do not converge for some strategies, it is obvious that
 135 % convergence  cannot  be  observed  for  some asynchronous  iterations  with  the
 136 % corresponding  strategies.  However, even  if all  the components
 137 % are activated, that is the asynchronous counterpart of pure parallel iterations,
 138 % delays may introduce divergence.
 139
 140 % For instance, let $J^t$ be constantly equal to the identity matrix and
 141 % consider the matrix
 142 % \begin{equation*}
 143 % S^t = \left(
 144 % \begin{array}{lllll}
 145 % t & t' & t & t & t \\
 146 % t & t & t & t & t \\
 147 % t & t & t & t & t \\
 148 % t & t & t & t & t\\
 149 % t & t & t & t & t \\
 150 % \end{array}
 151 % \right)
 152 % \textrm{ where }
 153 % t' = \left\{
 154 % \begin{array}{ll}
 155 % t & \textrm{ if t is even;} \\
 156 % t-1 & \textrm{ otherwise.}
 157 % \end{array}
 158 % \right.
 159 % \end{equation*}
 160
 161 % We have both
 162 % \begin{eqnarray*}
 163 % X^{2k+1} & =& F(X^{2k}) \\
 164 % X^{2k} & =& \left(
 165 % \begin{array}{l}
 166 % F_1(X_1^{2k-1},X_2^{2k-2},X_3^{2k-1},X_4^{2k-1},X_5^{2k-1}) \\
 167 % F_2(X^{2k-1})\\
 168 % \vdots \\
 169 % F_5(X^{2k-1})
 170 % \end{array}
 171 % \right).
 172 % \end{eqnarray*}
 173
 174
 175 % Starting from $X^0 = (0,0,0,1,1)$, the system reaches
 176 % $X^1 = (0,1,0,1,1)$ and enters in a cycle between  these
 177 % two configurations (as in some chaotic iterations).
 178
 179 % In
 180 % the  next  section, a  particular  execution  mode  is described  which  enables
 181 % asynchronism in iterations while guaranteeing the convergence.
 182
 183
 184 In  what follows  and for  brevity  reasons, configurations  are represented  as
 185 decimal numbers instead of binary numbers.   It is not hard to establish that in
 186 parallel synchronous iterations, starting  from any configuration different from
 187 7 (111) leads  to the fixed point 2  (010), and starting from 7 leads  to 7.
 188 With other strategies,
 189 the behavior is  quite different although the  system always
 190 reaches a stabilization.  Indeed, for the  initial states 1, 3 and 5, the system
 191 converges towards anyone of the two fixed  points 2 and 7.  However, there is no
 192 infinite  cycle and  the convergence  property defined  in  \Equ{eq:ltl:conv} is
 193 verified.
 194 Finally,  due to the presence of
 195 cycle in the connexion graph,
 196 known   sufficient  conditions~\cite{Bah00}  establishing  convergence
 197 results for asynchronous modes cannot be applied here.
 198 We address this question in what follows.
 199 \end{xpl}
 200
 201
 202 %%% Local Variables:
 203 %%% mode: latex
 204 %%% fill-column: 80
 205 %%% ispell-dictionary: "american"
 206 %%% mode: flyspell
 207 %%% TeX-master: "main"
 208 %%% End:
 209