+++ /dev/null
-\begin{exampleblock}{}
-
-\begin{itemize}
-\item Our Prototype: confirmation of convergence
-of mixed asynchronous iterations with uniform delays
-\item Mixed iterations with
- $SCC(1)=\{1,2\}$,
- $SCC(3)=\{3\}$ and $SCC(4)=\{4,5\}$
-\begin{center}
- \includegraphics[width=2.5cm]{../xpl_iteration_final.ps}
-\end{center}
-\end{itemize}
-\end{exampleblock}
+++ /dev/null
-
-\begin{exampleblock}{}
-\begin{itemize}
-\item Connection graph:
-\begin{center}
-\includegraphics[width=3cm]{../xplgraph.ps}
-\end{center}
-\end{itemize}
-\end{exampleblock}
+++ /dev/null
-\begin{itemize}
-\item Intuition:
- \begin{itemize}
- \item Nodes that may introduce cyclic iterations: grouped
- \item Nodes inside each group: synchronized at each other
- \item Nodes of distinct groups: keeping asynchronism
- \end{itemize}
-\item Formalization:
- \begin{itemize}
- \item Group: SCC of the connection graph
- \item Mixed iterations of DN with Uniform Delays:
- \begin{itemize}
- \item $S_{ij}^t$ is $t$ if $i \in SCC(j)$.
- \item $
- \begin{array}{l}
- \forall p_0,p_1,q_0,q_1,t \, .\,
- \quad (
- p_1 \in SCC(p_0) \land
- q_1 \in SCC(q_0))\\
- \qquad \Rightarrow
- S_{p_0q_0}^{t} =
- S_{p_1q_1}^{t}
- \end{array}
- $
- \end{itemize}
- \end{itemize}
-\item Elements in the same SCC: cannot be differentiated
-\end{itemize}
+++ /dev/null
-\newcommand{\Nats}[0]{\ensuremath{\mathbb{N}}}
-
-\begin{Theorem}{}
- Given an initial configuration $X^0 = (X_1^0, \ldots, X_n^0)$ and a
- strategy $(J^t)^{t \in \Nats}$. If chaotic iterations with strategy
- $(J^t)^{t \in \Nats}$ converge to some fixed-point, then mixed iterations with
- uniform delays with the same strategy $(J^t)^{t \in \Nats}$ converge to the
- same fixed-point.
-\end{Theorem}
-\begin{Proof}
-\begin{itemize}
-\item Element renaming wrt. a partial order
-\item Induction on the SCC index
-\end{itemize}
-\end{Proof}
+++ /dev/null
-\begin{itemize}
- \item \emph{Strategy}: sequence of elements updated at time $t$;
- \begin{itemize}
- \item $n*n$ diagonal matrix: $J_{ii}^t = 1$ iff $X_i \in E_i$
- is updated at time $t$
- \end{itemize}
- \item \emph{Visibility Dates}: sequence of the more recent dates where
- components know values of other ones
- \begin{itemize}
- \item $n*n$ matrix $S_{ij}^t$: highest $t'$
- s.t. $t' \le t$ and $X_j^{t'}$ is accessible for $i$
- \item Communcation delays from $j$ to $i$: $t - S_{ij}^t$
- \end{itemize}
- \item \emph{Iterations modes}:
-\[
-X^{t+1}= (I -J^t)X^t + J^t
-\left(
-\begin{array}{c}
-F_1
-\left( X_1^{S_{11}^t},\ldots, X_{n}^{S_{1{n}}^t} \right) \\
-\vdots \\
-F_{n} \left( X_1^{S_{{n}1}^t},\ldots, X_{n}^{S_{{n}{n}}^t} \right)
-\end{array}
-\right)
-\]
-\begin{itemize}
-\item Parallel mode: $J^t=I$ and $S^t=(t)$
-\item Chaotic mode: $S^t=(t)$
-\item Asynchronous: no constraint
-\end{itemize}
-\end{itemize}
-
+++ /dev/null
-\begin{itemize}
-\item<1-3> Objectives: ``similar behaviors'' in asynchronous iterations
- as in some chaotic iterations
-\item<2-3> Issues:
-\begin{itemize}
-\item Strengthening the convergence conditions of chaotic mode
-\item Lightly introduce synchronism into asynchronous modes [ABCVS05]
-\end{itemize}
-\item<3> \alert{Proof of convergence conjecture}
-\end{itemize}
-
-
-
+++ /dev/null
-\begin{exampleblock}{}
-\begin{itemize}
-\only<1>{\item Parallel iterations: convergence
-\begin{center}
-\includegraphics[width=8cm]{../implementation/para_iterate_dec.ps}
-\end{center}}
-\only<2>{\item Chaotic iterations: divergence with $J^t=\{24;15;14;15;\ldots\}$
-\begin{center}
-\includegraphics[width=4cm]{../chao_iterate_excerpt.ps}
-\end{center}}
-\only<3>{\item Asynchronous iterations: divergence even with $J^t=I$
-\begin{itemize}
-\item $S^t = \left(
-\begin{array}{lllll}
-t & t' & t & t & t \\
-t & t & t & t & t \\
-t & t & t & t & t \\
-t & t & t & t & t\\
-t & t & t & t & t \\
-\end{array}
-\right)
-\textrm{ where }
-t' = \left\{
-\begin{array}{l}
-t \textrm{ if t is even;} \\
-t-1 \textrm{ otherwise.}
-\end{array}
-\right.
-$
-\item
-$
-\begin{array}{rcl}
-X^{2k+1} & =& F(X^{2k}) \\
-X^{2k} & =& \left(
-\begin{array}{l}
-F_1(X_1^{2k-1},X_2^{2k-2},X_3^{2k-1},X_4^{2k-1},X_5^{2k-1}) \\
-F_2(X^{2k-1})\\
-\vdots \\
-F_5(X^{2k-1})
-\end{array}
-\right).
-\end{array}
-$
-
-$\rightarrow$ cycle between 3 and 11.
-\end{itemize}
-}
-\end{itemize}
-\end{exampleblock}
+++ /dev/null
-\begin{exampleblock}{}
-\begin{itemize}
-\item Five elements $1 \le i \le 5$ taking their value $X_i$ in $\{0,1\}$
-\item Configuration: a binary number in 0,1,\ldots,31
-\item Dynamic: a map
-\[
-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.
-\]
-\end{itemize}
-\end{exampleblock}
