relecture preuve PCH

[rairo15.git] / Equivalence.tex

%%%%%%%% Sample LaTeX input for Complex Systems %%%%%%%%%%% 
%
% This is a LaTeX input file  
% Text following % on a particular line is treated as a comment, and 
% ignored by LaTeX.  
% You do not need to type any text that follows a % 
% 
\documentclass{article}

\usepackage{epsf}
\usepackage{complex-systems}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage[utf8]{inputenc}
\usepackage{color}
\usepackage{framed}

% complex-systems.sty is the special macro package for Complex Systems.
% epsf.sty is the preferred graphics import method

% complex-systems.sty defines the following defaults:
% \newtheorem{theorem}{Theorem}
% \newtheorem{lemma}{Lemma}
% \newtheorem{corollary}{Corollary}
% \newtheorem{example}{Example}
% \newtheorem{proposition}{Proposition}

%%% Personal definitions
\newcommand{\Alg}[1]{Algorithm~\ref{#1}}
\newcommand{\Sec}[1]{Section~\ref{#1}}
\newcommand{\Equ}[1]{Equ.(\ref{#1})}
\newcommand{\Prop}[1]{Prop.~\ref{#1}}
\newcommand{\Th}[1]{Theorem~\ref{#1}}
\newcommand{\Fig}[1]{Fig.~\ref{#1}}
\newcommand{\Def}[1]{Def.~\ref{#1}}

\newcommand{\astep}{\stackrel{a.s}{\mapsto}}
\newcommand{\alead}{\stackrel{a.i}{\leadsto}}
\newcommand{\aconv}{\stackrel{a.cv}{\Longrightarrow}}
\newcommand{\notaconv}{\stackrel{a.cv}{\Longrightarrow}\hspace{-5mm}/\hspace{3.2mm}}
\newcommand{\boolprod}{\stackrel{\sim}{\prod}}
\newcommand{\cycle}{Cycle}
\newcommand{\pcycle}{p\_Cyc}
\newcommand{\sub}{S}

\def\N{\mathbb{N}}
\def\R{\mathbb{R}}

\definecolor{shadecolor}{rgb}{0.95,0.95,0.95}
\newenvironment{Algo}{\begin{center}\begin{minipage}[h]{0.95\columnwidth}\begin{shaded}\begin{tabbing}%
  \hspace{3mm}\=\hspace{3mm}\=\hspace{3mm}\=\hspace{3mm}\=\hspace{3mm}\=\hspace{3mm}\=\hspace{3mm}\= \kill} %
 { \end{tabbing}\vspace{-1em}\end{shaded}\end{minipage}\end{center}\vspace{-1em}}

%%%
%%% MAIN DOCUMENT
%%%
\begin{document}

% 
% The format for a general title is slightly complicated; 
% here first is a comment giving a simple example: %
% \title{Sample Paper for Complex Systems} 
% \author{\authname{First Author}\\[2pt]
% \authadd{University Department, University Name, Address,}\\ 
% \authadd{City, State ZIP/Zone, Country}\\ 
% \authadd{and}\\
% \authadd{Group, Company, Address, City, State ZIP/Zone, Country}\\ 
% \and 
% \authname{Second Author}\\ 
% \authname{Third Author}\\ 
% \authname{Fourth Author}\\[2pt]
% \authadd{Group, Laboratory, Address, City, State ZIP/Zone, Country} 
% }
% \markboth{F. Author, S. Author, T. Author, and F. Author}
% {Sample Paper for Complex Systems}
% \maketitle 

% Here is a more complete case:

\title{Transformation of Asynchronous System with Delays to Asynchronous System
  without Delays} 
% Use \\ to indicate line breaks in titles longer than about 
% 55 characters. 
% Lines throughout the title section should be broken so that 
% successive lines are progressively shorter. 
% Use \thanks for footnotes to the title. Put acknowledgments at the 
% end of the paper. 
%
% \thanks{The title serves as a headline for the paper: many readers 
% use it to decide whether to look at the paper. Avoid excessively 
% general, technical, or cutesy titles. Questions are acceptable as 
% titles. Capitalize the first letters of important words only. 
% Funding and personal acknowledgments go at the end of the paper. 
% Use footnotes to the title only for statements such as ``This paper 
% was based on a talk given at the conference on$\ldots$'' or ``Part 1 
% in this series of papers appeared in$\ldots$''}}

\author{\authname{Sylvain Contassot-Vivier% 
\thanks{Electronic mail address: contasss@loria.fr}}
\\[2pt] 
% Use \\[2pt] to end the line and add space between author and affiliation 
\authadd{Loria UMR 7503, Université Lorraine}\\ 
\authadd{Campus Scientifique - BP 239}\\
\authadd{54506 Vandoeuvre-lès-Nancy, France}
%\thanks{Give complete affiliation and mailing address, including 
%country. Capitalize important words and proper names only. (Use 
%standard two-letter abbreviations for state names.) For foreign 
%addresses, give as much as possible in English. }\\ 
%\authadd{and}\\ 
%\authadd{Group, Company, Address, City, State ZIP/Zone, Country}\\ 
%\and
% precede the second set of authors with \and.
%\authname{Second Author} \\ 
%\authname{Third Author}\\ 
%\authname{Fourth Author}\\[2pt]
% Each author name goes on a separate line. 
%\authadd{Group, Laboratory, Address, City, State ZIP/Zone, Country} 
% Put no ``.'' at the end of any address. 
}

\maketitle    
% End title section

% The following specifies the running headings 
\markboth{S. Contassot-Vivier}{Equivalence between asynchronous systems} 

% Each running heading should be less than about 50 characters long. 
% If necessary, give a shortened version of the title. Do not use 
% abbreviations. 
%
% If they will fit, include complete author names; otherwise use 
% initials only. If abbreviated names do not fit, truncate the author 
% list and end with ``and others''.

\begin{abstract} 
  This  paper presents  a  transformation process  of  any asynchronous  complex
  system with  delays to an  equivalent asynchronous system without  delays. The
  interest of such equivalence lies in the suppression of the history dependency
  of the system in  its evolution. This has an important impact  on the study of
  the dynamic of  the system.  The equivalence is  illustrated on representative
  examples and  the gain is pointed  out by a comparison  between algorithms for
  attraction basin determination.
\end{abstract}

% The text of the paper follows. It is usually easiest to put 
% everything in the same file. The file may however need to be 
% split for some computer mail systems. 
% Automatic section numbering in the LaTeX source is encouraged, 
% but is not essential.

\section{Introduction} 
\label{intro}

The different models of complex systems  are essential in the study of many real
life  systems,  whatever  they  are  natural or  man-made.   % As  a  particularly
% interesting example,  parallel iterative algorithms  play a central role  in the
% domain of scientific computation and simulation. Indeed, such algorithms are the
% key to high accuracy and  large scale simulations of complex phenomena.
In  this paper,  we  focus  on the  discrete-time  discrete-state systems.   The
discrete nature  of the  states is not  a limitation  of the model  according to
potential  applications in computer  science as  current computers  actually use
discrete  number representations.  However,  the study  of their  behavior stays
difficult, especially due to the fast combinatorial explosion in possible states
of such  systems. Moreover,  different models exist  that can take  into account
some specific  behaviors such as asynchrony  between the elements  of the system
and  also  communication delays  between  the  elements.  Such models  are  very
interesting because  they are among  the most general  ones. However, it  is yet
harder to study them, especially  the ones including communication delays due to
the dependence of the history of the system in its evolution.

In this paper,  we propose an equivalence between  asynchronous systems with and
without  communication delays.   The  interest  of such  an  equivalence is  the
possibility  to reduce  the complexity  of the  behavior study  of  systems with
delays.  In fact, the  history of the system is no more  required to explore its
possible evolutions  and this represents  a great simplification.   Moreover, it
allows the use of the same  theoretical results and tools as for systems without
delays.

The next  section presents the  standard formulation of complex  systems, recall
the main  asynchronous modes that are  usually studied and  details the specific
model we focus on.  In  \Sec{sec:transfo}, the theoretical result of equivalence
between asynchronism  with delays and asynchronism without  delays is presented.
Then,  some  representative examples  are  given  in  \Sec{sec:ex}.  Finally,  a
comparison of attraction  basin determination between the two  formulations of a
given system is performed in \Sec{sec:comp}.

\section{Asynchronous complex systems}
\label{sec:base}

\subsection{Notations}
\label{sec:notations}

Classically, a complex  system is composed of $n$  elements.  Each element $x_i$
takes its value in the set $E_i$ and  the global value of the system is then the
collection of  the states of all the  elements $x=(x_1,...x_n)$ in the  set $E =
\prod_{i=1}^nE_i$.   The  dynamics of  the  system  is  given by  the  evolution
functions $f_i$ respectively associated to the $x_i$. Here again, the collection
of the  individual functions forms the  global evolution function  of the system
$f=(f_1,f_2,...,f_n)$.   Each $f_i$  may  be  general and  can  be expressed  as
algorithms  taking as  input the  values  of the  components in  the system  and
yielding one  value in $E_i$.   This feature is  very important as it  implies a
larger generality than specific systems  such as cellular automata. Finally, the
system evolves during  discrete time $t$ (also called  iterations) and the state
at time $t$ is denoted by $x^{t}=(x_1^t,...,x_n^t)$.

The synchronous dynamics of such a system is given by \Alg{algo:sync}.
\begin{algorithm}[h]
  \caption{Synchronous system}
  \label{algo:sync}
  \begin{Algo}
    Given an initial state $x^{0}=(x_{1}^{0},...,x_{n}^{0})$\\
    \textbf{for} $t=0,1,...$\\
    \>\textbf{for} $i=1,...,n$\\
    \>\>$x_{i}^{t+1} = f_i(x^{t}) = f_i(x_1^t,x_2^t, ...,x_n^t)$\\
    \>\textbf{endfor}\\
    \textbf{endfor}
  \end{Algo}
\end{algorithm}

\subsection{Asynchronous mode}
\label{sec:opmodes}

Classically, different models of asynchronism  are used depending on the way the
communications      are       managed      and      the       updatings      are
performed~\cite{Rob86,BT89,HM93}.   In   this  study,  we   consider  the  fully
asynchronous mode with delays according to \Alg{algo:async}.

\begin{algorithm}[h]
  \caption{Asynchronous system}
  \label{algo:async}
  \begin{Algo}
    Given an initial state $x^{0}=(x_{1}^{0},...,x_{n}^{0})$\\
    \textbf{for} $t=0,1,...$\\
    \>\textbf{for} $i=1,...,n$\\
    \>\>\textbf{if} $i\in J(t)$ \textbf{then}\\
    \>\>\>$x_{i}^{t+1} = f_i(x_1^{t-d_1^i(t)},x_2^{t-d_2^i(t)}, ...,x_n^{t-d_n^i(t)})$\\
    \>\>\textbf{else}\\
    \>\>\>$x_{i}^{t+1} = x_i^t$\\
    \>\>\textbf{endif}\\
    \>\textbf{endfor}\\
    \textbf{endfor}
  \end{Algo}
\end{algorithm}

In  this algorithm, $J(t)$  is the  subset of  elements of  the system  that are
updated at time $t$ and $d_j^i(t)$ is  the delay of element $j$ according to $i$
at  time $t$. So,  $d_j^i(t)$ represents  the number  of iterations  between the
production of  the value of $x_j$ and  its reception on element  $i$.  When this
value is 0, then there is no delay and element $i$ uses the value of element $j$
at the previous iteration.  Although  $d_j^i(t)$ is not bounded, it is generally
assumed  that  the  versions of  values  received  on  each element  follow  the
evolution       of       the      system,       that       is      to       say:
$\lim_{t\rightarrow\infty}t-d_{j}^{i}(t)  =\infty$.   Moreover,  the  \emph{fair
  sampling} condition  is also  supposed.  It assumes  that all the  element are
regularly updated:  $\forall i\in\left\{ 1,...,n\right\}  ,\left| \left\{ t,i\in
    J(t)\right\} \right| =\infty$.

\section{Transformation Process }
\label{sec:transfo}

\section{Representative Examples}
\label{sec:ex}

\section{Comparison of Attraction Basin Determination}
\label{sec:comp}

\section*{Acknowledgments}

\bibliographystyle{plain}
\bibliography{biblio}
%\begin{thebibliography}{99}
% The number of 9s indicates how wide the reference 
% numbers must hang for all references to be aligned properly.

% \bibitem{a-review}
% % ``a-review'' is just a sample tag: use a tag that describes the 
% % paper; or perhaps just use numerical tags.
% First Author and Second Author, ``A Review Article,'' \textit{Full Name
% of Journal}, \textbf{volume} (date) page--page.
% % Use \textit{...} for italics, \textbf{...} for boldface.
% % Do not explicitly use the word ``volume''
% % The full year (e.g., 1991) should be used for the date.
% % Use -- to get an appropiate dash between page numbers.

%\end{thebibliography}

\end{document}