%%%%%%%%%%%%%%%%%%%%%%%
\documentclass{doublecol}
%%%%%%%%%%%%%%%%%%%%%%%

\usepackage{amssymb}
\usepackage{amsbsy,natbib}
\usepackage{amsthm}
\usepackage{amsfonts,amsmath,bm}
\usepackage[dvipsone]{epsfig}
\RequirePackage{graphics,epsf}

%%%%%%%%%%%%%%%%%%%%%%
% \'Enonc\'es
%%%%%%%%%%%%%%%%%%%%%%
\newtheorem{proposition}{Proposition}
\newtheorem{theorem}{Theorem}
\newtheorem{remark}{Remark}
\newtheorem{lemma}{Lemma}
\newtheorem{definition}{Definition}

%%%%%%%%%%%%%%%%%%%%%%
% Lettres
%%%%%%%%%%%%%%%%%%%%%%

\def\A{{\mathcal A}}
\def\B{{\mathbb B}}
\def\K{{\mathbb K}}
\def\L{{\mathcal L}}
\def\F{{\mathbb F}}
\def\N{{\mathbb N}}
\def\C{{\mathbb C}}
\def\R{{\mathbb R}}
\def\Z{{\mathbb Z}}
\def\Q{{\mathbb Q}}
\def\X{{\mathbb X}}
\def\al{\alpha}
\def\be{\beta}
\def\ga{\gamma}
\def\ep{\epsilon}
\def\S{{\Sigma}}
\def\Q{{\mathbb Q}}
\def\SG{{\goth S}}
\def\mref#1{(\ref{#1})}

%%%%%%%%%%%%%%%%%
\begin{document}
%%%%%%%%%%%%%%%%%

\LRH{Shift Operators and Complex Systems}

\RRH{Lua\"\i Jaff, G\'erard H.E. Duchamp and Cyrille Bertelle}

\VOL{x}

\ISSUE{x/y/z}

\PUBYEAR{2006}

\setcounter{page}{1}

\LRH{Shift Operators and Complex Systems}

\RRH{Lua\"\i Jaff, G\'erard H.E. Duchamp and Cyrille Bertelle}

\VOL{x}

\ISSUE{x/y/z}

\PUBYEAR{2006}

\BottomCatch

\title{Shift Operators and Complex Systems}

\authorA{Lua\"\i~Jaff*}

\affA{LIPN - University of Paris 13\\
99, avenue Jean-Baptiste Cl\'ement \\ 
93430 Villetaneuse - France \\
E-mail: luai.jaff@gmail.com \\
E-mail: gheduchamp@gmail.com\\ 
*Corresponding author}

\authorB{G\'erard H.E. Duchamp}
 
\affB{LIPN - University of Paris 13\\
99, avenue Jean-Baptiste Cl\'ement \\ 
93430 Villetaneuse - France \\
E-mail: gheduchamp@gmail.com}

\authorC{Cyrille Bertelle}

\affC{LITIS - University of Le Havre\\
25 rue Ph. Lebon - BP 540\\
76058 Le Havre cedex - France\\
E-mail: cyrille.bertelle@univ-lehavre.fr}


\begin{abstract}
In a previous paper \cite{epnads}, some of the authors dealt with the use of automata with (various type of) 
multiplicities for modelizing agents with rational behaviour and how one could perform genetic operations on them. 
In this paper, we emphasize the role played by shift operators to identify automata with similar behaviour.   
\end{abstract}

\KEY{shift operators; complex systems; automata; emergence.}

\REF{to this paper should be made as follows: Jaff, L., Duchamp, G.H.E. and Bertelle, C., 
(2006)
`Shift Operators and Complex Systems', Int. J. of Modeling, Identification and Control,
Special Issue Modeling Complex Systems, Vol. x, Nos. x/y/z, pp.xx--yy.}

\BIO
{Lua\"\i  Jaff is PhD student at LIPN in the Institute Galil\'ee
at the University of Paris 13, France. He is working on efficient operators and complex systems modelling, especially in using genetic on automata.
}

\maketitle

%\section{INTRODUCTION: COMPLEX SYSTEM DESCRIPTION USING AUTOMATA-BASED AGENT MODEL}
\section{INTRODUCTION}

\begin{figure*} [htp]
\begin{center}
\includegraphics[scale=1.0]{sys2beh.eps}
\caption{Multi-scale complex system description: from global to individual 
models}
\label{sys2beh}
\end{center}
\end{figure*}

According to General System Theory \cite{gst, Mo}, a complex system is composed 
of entities in mutual interaction and interacting with the outside environment. 
A 
system has some characteristic properties which confer its structural aspects, 
as schematically described in part (a) of Figure \ref{sys2beh}: 
\begin{itemize}
\item The set elements or entities are in interactive dependance. The alteration 
of only one entity or one interaction reverberates on the whole system. 
\item A global organization emerges from interacting constitutive elements. This 
organization can be identified and carries its own autonomous behavior while it 
is in relation and dependance with its environment. The emergent organization 
possesses new properties that its own constitutive entities do not have. "The 
whole is more than the sum of its parts". 
\item The global organization retro-acts over its constitutive components. "The 
whole is less than the sum of its parts" after E. Morin.\\
\end{itemize}

The interacting entities network as described in part (b) of Figure 
\ref{sys2beh} leads each entity to perceive informations or actions from other 
entities or from the whole system and to act itself.\\

A well-adapted modeling consists of using an agent-based representation which is 
composed of the entity called agent as an entity which perceives and acts on an 
environment, using an autonomous behaviour as described in part (c) of 
Figure \ref{sys2beh}.\\

To compute a simulation composed of such entities, we need to describe the 
behaviour of each agent. This one can be schematically described using internal 
states and transition processes between these states, as described in part 
(d) of Figure \ref{sys2beh}.\\  

There are several definitions of ``agents'' or ``intelligent agents'' according 
to their behaviour specificities~\cite{Fe, We}.
Their autonomy  means that the agents try to satisfy a goal
and execute actions, optimizing a satisfaction function to reach it.\\

For agents with high level of autonomy, specific actions are realized even when no 
perception are detected from the environment. 
To represent the process of this deliberation, different formalisms can be 
used and a behaviour decomposed in internal states is an effective approach.
Finally, when many agents operate, the social aspects must also be taken into 
account. 
These aspects are expressed as communications through agent organisation with 
message
passing processes. 
Sending a message is an agent action and receiving a message is an agent 
perception. The previous description based on the couple: perception and action, 
is well adapted to this.\\

In the following, we begin to define in sections 2 and 3 some general efficient operators and data structures which are well-suited for agent behavior modelling. In sections 4 and 5, we deal with populations of automata to define operators on them and we conclude in section 6, to define genetic operators on automata. Then we develop two applications. The first in section 7 concerns adaptive strategies for game theory. The second consists in an original contribution for automatic emergent system computation. This final application is an illustration of an efficient computation for the complex systems concepts defined previously in this section. 


\section{SHIFT OPERATORS}

One of the most natural operations on functions is the shifting of the argument. 
Using the denotation of\\ 
{\tt http://mathworld.wolfram.com/}\\
{\tt ShiftOperator.html},\\ 
one has 
\begin{equation}
	E^a(f)[x]:=f(x+a)
\end{equation}
What is little less known (but not less useful) is the use of shifting operations 
on the exponents of a Taylor series (which amounts to the same realm, considering a series as a function of the monomials).\\
To each series, 
\begin{equation}
	S=\sum_{n\geq 0}\al_n z^n
\end{equation}
one make correspond the series 
\begin{equation}\label{gammadag}
	\gamma_z^\dag(S)=\sum_{n\geq 0}\al_{n+1} z^n
\end{equation}
In this manner one can deal not only with polynomials but with rational functions. This setting has a natural 
extension to the multivariate case allowing to deal with rational behaviours.
Rational behaviours are exactly the behaviours of automata with multiplicities and these automta are the type 
which is well fitted for the use of genetic algorithms over populations of agents with rational behaviours \cite{epnads}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{KINDS OF AUTOMATA}


Automata theory is at the edge of many areas of human skill
 (mathematics, physics, engeneering, ...) and roughly speaking, could be defined as 
 {\it all models dealing with transition rules}.\\
 Several domains have been developped within automata theory including: {\it cellular automata, 
 boolean automata (or finite-state automata) and multiplicity automata}.\\
 The first kind deals with {\it local transition rules} whereas the two last are defined by 
 {\it global rules}. As a matter of fact, the last one ({\it multiplicity automata theory \cite{Ei,BR}})
  includes the second by specializing the scalars to the Boolean semiring. Indeed varying the scalars, 
  one can reach, with the same theory, models as diverse as {\it deterministic finite automata}, {\it finite Markov chains} and {\it transducers} (kinds of automata where transitions produce words and languages).\\  
This gives the general framework for {\it multiplicity automata} or {\it automata with multiplicities}. 
In this model, the output data of the automata belongs to a specific 
algebraic structure, a semiring \cite{Ei,Go,St}. 
In that way, we will be able to build effective operations on such automata, 
using the power of the algebraic structures of the output data 
and we are also able to describe this automaton by means of a matrix 
representation with all the power of this new linear algebra (i.e. with semirings).\\
Moreover, the automaton can be observed by means of the function it generates. 
This function will be called the {\it behaviour} of the automaton.

\begin{definition}
{\bf (Automaton with multiplicities)}\\
 An automaton with multiplicities over an alphabet  $A$  and a semiring $K$ is 
the 5-uple $(A,Q,I,T,F)$ where
\begin{itemize}
\item  $Q=\{S_1,S_2\cdots S_n\}$ is the (finite) set of states;
\item   $I: Q\mapsto K$  is a function over the set of states, which 
associates to each initial state a value in $K$ (for instance probability, word or boolean), 
called entry cost, and to non-initial state a zero value ;
\item	$F: Q\mapsto K$  is a function over the set states, which 
associates to each final state a value in $K$, called final cost, and to non-final 
state a zero value;
\item $T$ is the transition function, that is\\
 $T: Q\times A\times Q\mapsto K$ 
which, to a state $S_i$, a letter $a$ and a state $S_j$ associates a value $\alpha$ in 
$K$ (the cost of the transition) 
if it exist a transition labelled with $a$ from the state $S_i$  to the 
state $S_j$ and and zero otherwise.\\   
\end{itemize}
\end{definition}

\begin{remark}
i) As told above, automata with multiplicities are a generalisation of finite automata. In fact, 
finite automata can be considered as automata with multiplicities in the 
semiring $K$, the boolan set $B=\{0,1\}$ (endowed with the semiring structure induced by the 
logical operations ``or/and'').
 To each transition, we affect $1$ if it exists and $0$ if not.\\
ii) We have not yet, on purpose, defined what a semiring is. Roughly it is the least 
structure which allows the matrix ``calculus'' with unit (one can think of a ring without 
the "minus" operation).
\end{remark}

With such a setting, the automaton can be seen as a machine which accepts a word and provides a scalar 
(for instance a probability, a word or a boolean). Let us describe now how the output is computed.

We associate to the support of $T$ the weighted graph $\Gamma_T$ with
edges $edges(\Gamma_T) =$
\begin{equation}
\{(q,a,\alpha,r) \in Q\times A\times k\times Q\}_{\ T(q,a,r) \neq 0}
\end{equation}

\noindent
This means that every edge $(q \rightarrow r)$ is superscripted by the 
pair $(a|\alpha)$ such that $T(q,a,r) = \alpha\ne 0$. 
Classically call the {\bfseries{path}}, a sequence of edges
$(p_j, a_j,\alpha_j, q_j)_{1\leq j \leq n}$ such that, for all $j<n$, 
one has $ q_j = p_{j+1}$.

\noindent
Now, the cost of the path is $\prod_{1 \leq j \leq n} \alpha_j$ (product in K) 
and its label is $a_1 a_2 \,...\, a_n$ (concatenation)
\begin{equation} 
A(w) = \sum_{q,r \in Q} I(q) \big(\sum_{c\ path\ q\rightarrow r\atop label(c)=w}\textrm{cost}(c)\big) F(r)
\end{equation}

\begin{remark}
The previous automaton with multiplicities can be, equivalently, expressed by its 
matrix representation which is a triplet 
\begin{itemize}
\item $\lambda\in K^{1\times Q}$ which is a row-vector which coefficients are 
$\lambda_i=I(S_i)$,
\item $\gamma\in K^{Q\times 1}$ is a column-vector which coefficients are 
$\gamma_i=F(S_i)$,
\item $\mu: A\mapsto K^{Q\times Q}$ is the mapping such that 
the coefficient on the $q_i$th row and $q_j$th column of $\mu(a)$ is 
$T(q_i,a,q_j)$ 
\end{itemize} 
\end{remark}

\noindent
Due to the effect of matrix computation we have

\medskip
\noindent
\begin{theorem} \cite{BR,Ei} Still denoting $\mu$ the extension of $\mu$ to words, 
one has
$$A(w) = I \mu(w) T $$
\end{theorem}

As the behaviour is a function on the words, we will have advantage to 
consider operators on such functions.\\ 
In this paper we will concentrate on shifts which are generalizations of the 
univariate case considered above \mref{gammadag}. 

The behaviour of an automaton $\A$ is, by definition, 
\begin{equation}
	Behaviour(\A)=\sum_{w\in A^*}\A(w)w
\end{equation}
where $w\rightarrow \A(w)$, is the output function\\

\section{POPULATIONS OF AUTOMATA}

For complexity theory, it is important to deal with {\it populations of automata with 
multiplicities}. The first step, before considering neibourhood of {\it close behaviours} 
(however, see below sections 5 and 8) is
\begin{enumerate}
	\item to be able to test whether two automata have the same behaviour
	\item to be able to reduce the number of states of automata (the behaviour being preserved)
\end{enumerate}
In fact, given an automaton $\A$ and if the scalars are taken in a field 
(also certain rings can do, see \cite{Lu}) 
there is a minimal automaton having the same behaviour as $\A$. This automaton is the automaton of 
the {\it shifts of $Behaviour(\A)$}.\\
For a general function $f: A^*\mapsto k$, denoted as a sum\\
 $f=\sum_{w\in A^*}f(w)w$ one considers the 
{\it positive shifts} $(\gamma_u)_{u\in A^*}$
\begin{equation}
	\gamma_u(f)=\sum{w\in A^*}f(w)uw
\end{equation}
and their duals, the {\it negative shifts}
\begin{equation}
	\gamma_u^\dag(f)=\sum_{w\in A^*}f(uw)w
\end{equation} 

Now, the states of the minimal automaton corresponding to $\A$ is exactly the orbit of $Behaviour(\A)$
under the negative shifts, more precisely
\begin{equation}
	\Omega(Behaviour(\A))=\big\{ \gamma_u^\dag(Behaviour(\A))\big\}_{u\in A^*}
\end{equation}
now, one can show that this orbit can be computed from a finite process (see theorem below and \cite{IPL}, for full 
details). 

\subsection{The Orbit Method for Functions \\$A^* \rightarrow K$}

One has the following central theorem which sheds some light over the effective computation of a {\it normal form} within population of automata.

\begin{theorem}
Let k be a field, $S \in k^{A^*}$ and\\  
$\Omega(S)= \big\{\gamma_{u}^{\dag}(S)\big\}_{u\in A^*}$ be the orbit of $S$ as above 
then
\begin{enumerate}
\item S is the behaviour of an automaton if and only if $\Omega(S)$
is of finite rank
%
\item in the case above, let $(\gamma_{u_i}^{\dag}(S))_{i=1}^{n}$ be a basis of\\ 
$span(\Omega(S))\subset k^{A^*}$. Then, one must have, for\\
$(i,a)\in [1..n]\times A$
\begin{equation}
	\gamma_{a}^{\dag}(\gamma^{\dag}_{u_i}(S)) = \sum_{j=1}^n \mu_{ij}(a) \gamma^{\dag}_{u_j}(S)
\end{equation}
%
set
\begin{eqnarray*}
	& S=\sum_{i=1}^n \lambda_i \gamma^{\dag}_{u_i}(S)& \cr\cr
	&I = (\lambda_i)_{i=1}^n \textrm{ and } F= [(S(u_i))_{i=1}^n]^t &\cr\cr
	&T(i,a,j)=\mu_{ij}(a) \textrm{, for pairs }(i,j)&\cr
	& \textrm{ such that }\mu_{ij}(a)\not=0&
\end{eqnarray*}
and, we have the behaviour of $(A,Q,I,T,F)$ which is effectively $S$.
%
\item Conversely, if $\A = (A,Q,I,T,F)$ is an automaton recognizing $S$ and $\A_0 = (A,Q_0,I_0,T_0,F_0)$ the automaton constructed from $S$ as above, one has interwining matrices between the linear representations of $\A$ and $\A_0$.
\end{enumerate}
\end{theorem}

Now, from any automaton, one can construct algorithmically a minimal automaton and decide 
wether an automaton is the minimized the other.

\noindent
The reader is refered to \cite{IPL} where this algorithm is described 
in detail.

\subsection{Shift Operators and Modern Computation Techniques}

We would like here to mention two fields of applications of these shifting technique.
The first is the use of shifts to symbolic summation \cite{MCA}. 
The second is finding formulas for algebraic combinatorics. Let us illustrate
this on one example belonging to a class of problems that could be named:

\begin{center}
{\it ``finding closed formulas describing\\ 
statistics over data structures''.}
\end{center}

 Here the data structure under consideration is that of permutations of certain sets
  [1, 2, ..., n].
Readers which are more familiar with lists are invited to consider these as lists
$[\sigma(1), \sigma(2), ..., \sigma(n)]$ such that every number between $1$ to $n$ 
occurs once (and then only once).

\noindent
The population we consider will be the set of permutations without pattern $123$. 
This means that there is no triplet $i<j<k$ such that 
$\sigma(i) <\sigma(j)<\sigma(k)$
these permutations begin by a maximal descent that is there exists $k$ such that
$$\sigma(1)>\sigma(2)> ... > \sigma(k) <\sigma(k+1)$$

\noindent
Denoting by $L(n,k)$ their set and writing $\sigma(1), \sigma(2), ..., \sigma(n)$
instead of the list, we get the first values 

\begin{itemize}

\item $L(n,0) = L(0,n) = \emptyset\ (\forall n\geq 1)$
\item $L(0,0) = \{\emptyset\}$
\item $L(1,1) = \{1\}$
\item $L(2,1) = \{1\, 2\}$
\item $L(2,2) = \{2\,1\}$
\item $L(3,1) = \{132,231\}$ 
\item $L(3,2) = \{312,213\}$
\item $L(3,3) = \{321\}$

\end{itemize} 

\noindent
Now if one sets $l(n,k) = |L(n,k)|$ one can prove that

\begin{itemize}

\item $l(n,0) =  l(0,n)=0\ (\forall n\geq 1)$
\item $l(0,0)=1$
\item $l(n,k) = \sum_{j\geq {k+1}} l(n-1,j)$
\end{itemize} 

whence the easy computed table of the first values

\bigskip
\begin{tabular}{c||c|c|c|c|c|c|c|c|}

n$\backslash$ k & 0&1&2&3&4&5&6&7\\
\hline
\hline 
0& 1&0&0&0&0&0&0&0\\
\hline 
1& 0&1&0&0&0&0&0&0\\
\hline
2& 0&1&1&0&0&0&0&0\\ 
\hline 
3& 0&2&2&1&0&0&0&0\\
\hline 
4& 0&5&5&3&1&0&0&0\\
\hline 
5& 0&14&14&9&4&1&0&0\\
\hline 
6& 0&42&42&28&14&5&1&0\\
\hline 
7& 0&132&132&90&48&20&6&1\\
\hline
\end{tabular}

\bigskip
\noindent
This implies that, if one considers the diagonal functions, 

$$F_n(k):= l(n+k, k)$$

\noindent
using 
\begin{eqnarray}\label{shiftrel}
	&(E^{1} - Id) F_n(k) =&\cr 
	&l(n+(k+1), k+1) - l(n+k,k)=&\cr
	& l(n+(k+1), k+2)&\cr
	&\textrm{and } F_n(0) = 0\textrm{ for } n\geq 1& 
\end{eqnarray}

\noindent
One can conjecture that

$$F_n(k) = \frac{k.(k+n+1)...(k+2n-1)}{n!} $$

and indeed, relations \mref{shiftrel} have become nowadays an automatic 
certificate (see \cite{MCA}) of validity for this formmula.

Finally, we have the double generating series of this statistics 

$$\sum_{n,k} l(n,k) x^n y ^k = \frac{1}{1 - \frac{xy}{\sqrt{1-4x}}} $$

\section{TOPOLOGICAL CONSIDERATIONS}\label{topo}


If $K$ is a field, one sees that the space $\A_{(n)}$ of automata of dimension 
$n$ (with multiplicities in $K$) is a $K$-vector space of dimension 
$k.n^2+2n$ ($k$ is here the number of letters). So, in case the ground field is 
the field of real or complex numbers \cite{Bo1}, one 
can take any vector norm (usually one takes one of the H\"older norms 
$||(x_i)_{i\in I}||_\alpha := \big(\sum_{i\in I} | x_i 
|^\alpha\big)^{\frac{1}{\alpha}}$ 
for $\alpha\geq 1$,
 but any norm will do) and the distance is derived, in the classical way, by 
\begin{equation}
d(\A_1,\A_2)=norm(V(\A_1)- V(\A_2))
\end{equation}
where $V(\A)$ stands for the vector of all coefficients of\\ 
$\A=(\lambda,\mu,\gamma)$ 
arranged in some order. One has then the result of Theorem \ref{th1}.
 Assuming that $K$ is the field of 
real or complex numbers, we endow the 
space of series/behaviours with the topology of  pointwise convergence (Topology 
of F. Treves \cite{Tr}).  

\begin{theorem}\label{th1}
Let  $(\A_n)$ be a sequence of automata with limit $\L$ ($\L$ is an automaton), 
then one has
\begin{equation}
Behaviour(\L)=\lim_{n\rightarrow \infty} Behaviour(\A_n)
\end{equation}
where the limit is computed in the topology of Treves.
\end{theorem}


\section{GENETIC AUTOMATA}


We define the chromosome for each automata with multiplicities as the sequence 
of all the matrices 
 associated to each letter from the (linearly ordered) alphabet. 
The chromosomes are composed with alleles 
which are here the lines of the matrices \cite{BFJOP2}.\\

In the following, genetic algorithms are going to generate new automata 
containing possibly new transitions 
from the ones included in the initial automata.\\

The genetic algorithm over the population of automata with multiplicities 
follows a reproduction iteration 
broken up in three steps \cite{Gol,Mi,Ko}:
\begin{itemize}
\item 	{\it Duplication}: where each automaton generates a clone of itself; 
\item	{\it Crossing-over}: concerns a couple of automata. Over this couple, we 
consider a sequence of lines of each 
matrix  for all. For each of these matrices, a permutation on the lines of the 
chosen 
sequence is made between the analogue matrices of this couple of automata; 
\item	{\it Mutation}: where a line of each matrix  is randomly chosen and a 
sequence 
of new values is given for 
this line.
\end{itemize}

Finally the whole genetic algorithm scheduling for a full process of 
reproduction over all the population of 
automata is the evolutionary algorithm:

\begin{enumerate}
\item For all couple of automata, two children are created by duplication, 
crossover and mutation 
mechanisms;
\item The fitness for each automaton is computed;
\item For all 4-uple composed of parents and children, the performless automata, 
in term of fitness 
computed in previous step, are suppressed. The two automata, still living, 
are the result of the 
evolution of the two initial parents.
\end{enumerate}

\begin{remark}
The fitness is not defined at this level of abstract formulation, but it is 
defined 
corresponding to the context for which the automaton is a model, as we will do 
in 
the next section.
\end{remark}

%\section{APPLICATIONS TO COMPETITION-COOPERATION MODELLING USING PRISONER DILEMMA}
\section{APPLICATIONS TO GAME THEORY}

We develop in this section how we can modelize competition-cooperation processes 
in a same automata-based representation. The genetic computation allows to make 
automatic transitions from competition to cooperation or from cooperation to 
competition. The basic problem used for this purpose is the well-known prisoner 
dilemma \cite{Ax}.

\subsection{From adaptive strategies to probabilistic automata}

The prisoner dilemma is a two-players game where each player has two possible 
actions: 
cooperate ($C$) with its adversary or betray him ($\overline{C}$). So, four 
outputs are possible for the global 
actions of the two players. A payoff is defined relatively to these 
possible outputs, as 
described in the following table where the rows correspond to one player 
behaviour and the 
columns to the other player.\\

\begin{table}[htp]
        \begin{center}
        \begin{tabular}{|l|c|c|} \hline
                                & $C$           & $\overline{C}$ \\ \hline
                $C$             & (3,3)     & (0,5)       \\ \hline
                $\overline{C}$  & (5,0)     & (1,1)       \\ \hline
        \end{tabular}
        \caption{Prisoner dilemma payoff}
        \label{prisonerDilemmaPayoff}
\end{center}
\end{table}

In the iterative version of the prisoner's dilemma, successive steps can be 
defined.  
Each player do not know the action of its adversary during the current step but 
he knows it for the preceding step. 
So, different strategies can be defined for a player behaviour, the goal of each 
one is to 
obtain a maximal payoff for himself.\\
 
In Figures \ref{titfortat} and \ref{vindictive}, we describe two strategies 
with transducers. 
Each transition is labeled by the input corresponding to the player perception 
which is the precedent adversary action and the output corresponding to the 
present player 
action.  
The only inital state is the state 1, recognizable by the incoming arrow labeled 
only by the output. 
The final states are the states 1 and 2, recognizable with the double circles.\\
 
In the strategy of Figure \ref{titfortat}, the player has systematically the 
same behaviour as its adversary at the previous step. 
In the strategy of Figure \ref{vindictive}, the player chooses definitively to 
betray as soon as his adversary does it.  
The previous automaton represents static strategies and so they are not well 
adapted for the 
modelization of evolutive strategies. 
For this purpose, we propose a model based on a probabilistic automaton 
described by Figure \ref{probaDilemma} \cite{BFJOP1}.\\

\begin{figure} [htp]
\begin{center}
\includegraphics[scale=0.7]{titfortat.eps}
\caption{Tit-for-tat strategy automaton}
\label{titfortat}
\end{center}
\end{figure}

\begin{figure} [htp]
\begin{center}
\includegraphics[scale=0.7]{rancunier.eps}
\caption{Vindictive strategy automaton}
\label{vindictive}
\end{center}
\end{figure}

\begin{figure} [htp]
\begin{center}
\includegraphics[scale=0.7]{proba.eps}
\caption{{Probabilistic multi-strategies 
automaton}}
%\caption{Probabilistic multi-strategies 
%for two-states automata}
\label{probaDilemma}
\end{center}
\end{figure}



This automaton represents all the two-states strategies for cooperation  and 
competitive   
behaviour of one agent against another in prisoner's dilemma.\\

The transitions are labeled in output by the probabilities $p_i$ of their 
realization.  The first state is the state reached after cooperation action and 
the second state is reached after betrayal. \\

For this automaton, the associated matrix representation, as described 
previously, is:

\begin{eqnarray} 
I &=& \begin{pmatrix}p_1 & 1-p_1 \end{pmatrix}; \\
F &=& \begin{pmatrix}p_6\cr 1-p_6 \end{pmatrix};\\
T(C) &=& \begin{pmatrix}p_2 & 1-p_2\cr p_3 & 1- p_3 \end{pmatrix};\\ 
T(\overline{C}) &=& \begin{pmatrix}1-p_4 & p_4\cr 1-p_5 & p_5\end{pmatrix}
\end{eqnarray}


\subsection{From probabilistic automata to genetic automata}

From the matrix representations of the automata, we can compute genetic automata 
as described 
in previous sections. Here the chromosomes are the sequences of all the matrices 
associated to 
each letter. We have to define the fitness in the context of the use of these 
automata. The 
fitness here is the value of the payoff. 


\subsection{General Genetic Algorithm Process for Genetic Automata}


A population of automata is initially generated. These automata are playing 
against a predefined 
strategy, named $S_0$.\\

Each automaton makes a set of plays. At each play, we run the probabilistic 
automaton 
which gives one of the two outputs: ($C$) or ($\overline{C}$). With this output 
and the $S_0$'s output, we compute the payoff of the automaton, according with 
the payoff table.\\

At the end of the set of plays, the automaton payoff is the sum of all the 
payoffs of each play. 
This sum is the fitness of the automaton. At the end of this set of plays, each 
automaton has 
its own fitness and so the selection process can select the best automata. At 
the end of these 
selection process, we obtain a new generation of automata.\\

This new generation of automata is the basis of a new computation of the 3 
genetic operators.\\

This processus allows to make evolve the player's behavior which is modelized by 
the probabilistic multi-stra\-te\-gies two-states automaton from cooperation to 
competition or from competition to cooperation. The evolution of the strategy is 
the expression of an adaptive computation. This leads us to use this formalism 
to implement some self-organisation processes which occurs in complex systems.  

%(to be completed ... we can add a discussion about prisoner dilemma and how 
% that can be used in economical modeling : firm concurence, cold war, ...)
\newpage
\section{EMERGENT SYSTEMS MODELLING}\label{emergent}

In this section, we study how evolutive automata-based modeling can be used to 
compute automatic emergent systems. The emergent systems have to be understood 
in the meaning of complex system paradigm that we recall in the first section. We 
have previously defined some way to compute the distance between automata and we 
use these principles to define semi-distance between agents behaviours that are 
modeled 
with automata. Finally, we defined a specific fitness that allows to use genetic 
algorithms as a kind of reinforcement method which leads to emergent system 
computation \cite{Ho}.



\subsection{Agent Behavior Semi-Distance}

We describe in this section the bases of the genetic algorithm used on the 
probabilistic automata allowing to manage emergent self-organizations in the 
multi-agent simulation.\\

For each agent, we define $e$ an evaluation function of its own
behaviour returning the matrix $M$ of values such that $M_{i,j}$ is 
the output series from all possible successive perceptions when
starting from the initial state $i$ and ending at the final state $j$,
without cycle. It will clearly be $0$ if either $i$ is not an initial
state or $j$ is not a final one and the matrix $M_{i,j}$ is indeed a matrix of 
evaluations \cite{BR} of subseries of 
\begin{equation}
M^*:=(\sum_{a\in A} \mu(a)a)^*
\end{equation}

%equal to the value of the sum of the multipicities of all
%the successful paths between $i$ and $j$, without cycle, if $i$ is an
%initial state and $j$ is a final state, and is equal to $0$ otherwise. 
Notice that the
coefficients of this matrix, as defined, are computed whatever the
value of the perception in the alphabet $A$ on each transition on the successful
path\footnote{A {\it succesful path} is a path from an initial state to a final 
state}. This means that the contribution of the agent behaviour for
collective organization formation is only based, here, on
probabilities to reach a final state from an initial one.     
This allows to preserve individual characteristics in each agent
behaviour even if the agent belongs to an organization.\\

Let $x$ and $y$ be two agents and $e(x)$ and $e(y)$ their respective
evaluations as described above.
We define $d(x,y)$ a semi-distance (or pseudometrics, see \cite{Bo1} ch IX) 
between the two agents $x$ and $y$ as 
$||e(x)-e(y)||$, a matrix norm of the difference of their
evaluations. Let ${\cal{V}}_x$ a
neighbourhood of the agent $x$, relatively to a specific criterium, for
example a spatial distance or linkage network.  
We define $f(x)$ the agent fitness of the agent $x$ as~:
$$
f(x) = 
\left\lbrace
\begin{array}{ll}
\frac{ {\displaystyle card({\cal{V}}_x) } }
     { {\displaystyle \sum\limits_{y_i \in {\cal{V}}_{x}} d(x, y_i)^2} } 
     \ \ \ \ &\mbox{if} \sum\limits_{y_i \in {\cal{V}}_{x}} d(x,
y_i)^2 \neq 0 \\
\infty &\mbox{otherwise}
\end{array}
\right.
$$

\subsection{Evolutive Automata for Automatic Emergence of Self-Organized Agent-Based Systems}
 
In the previous computation, we defined a semi-distance between two agents. This 
semi-distance is computed using the matrix representation 
of the automaton with multiplicities associated to the agent behaviour. This 
semi-distance is based on the computation of successful paths which 
needs to define initial and final states on the behaviour automata. For specific 
purposes, we can choose to define in some specific way, the 
initial and final states. This means that we try to compute some specific action 
sequences which are chararacterized by the way of going from some specific 
states (defined here as initial ones) to some specific states (defined here as 
final ones).\\

Based on this specific purpose which leads to define some initial and final 
states, we compute a behaviour semi-distance and then the fitness function 
defined 
previously. This fitness function is an indicator which returns high value when 
the evaluated agent is near, in the sense of the behaviour semi-distance defined 
previously, to all the other agents belonging to a predefined neighbouring.\\

Genetic algorithms will compute in such a way to make evolve an agent population 
in a selective process. So during the computation, the genetic algorithm will 
make 
evolve  the population towards a newer one with agents more and more adapted to 
the 
fitness. The new population will contain agents with better fitness, so the 
agents of a population will become nearer to each others in order to improve their 
fitness. 
In that way, the genetic algorithm reinforces the creation of a system which 
aggregates agents with similar behaviors, in the specific way of the definition 
of initial and final states defined on the automata.\\

The genetic algorithm proposed here can be considered as a modelization of the 
feed-back of emergent systems which leads to gather agents of similar behaviour, 
but these formations are dynamical and we cannot predict what will be the 
set of these aggregations which depends of the reaction of agents during the 
simulation. Moreover the genetic process has the effect of generating a feed-
back of the emergent systems on their own contitutive elements in the way that 
the fitness improvement leads to bring closer the agents which are picked up 
inside the emergent aggregations.\\

For specific problem solving, we can consider that the previous fitness 
function can be composed with another specific one which is able to measure the 
capability of the agent to solve one problem. This composition of fitness 
functions leads to create emergent systems only for the ones of interest, that 
is, these systems are able to be developed only if the aggregated agents are 
able to satisfy some problem solving evaluation. 

\section{CONCLUSION}

The aim of this study is to develop a powerful algebraic structure to represent 
behaviors concerning cooperation-competition processes and on which we can 
add genetic operators. We have explained how we can use these structures for 
modeling adaptive behaviors needed in game theory. More than for this 
application, we have described how we can use such adaptive computations to 
automatically detect emergent systems inside interacting networks of entities 
represented by agents in a simulation. 



%Consider the equation (1) as the percentage of CPU resource occupation,
%where: {\it $\lambda $} is the total quantum of each process; {\it $\mu $}
%is portion of the time {\it $\lambda $} in which the CPU was effectively
%used by one process and {\it p} is the number of system processes.
%\begin{equation}
%\label{eq1}
%{\rm O}_{cpu} =\frac{\sum\nolimits_{i=0}^p {\frac{\mu _i }{\lambda _i }}
%}{p}
%\end{equation}
%Consider the equation (2) as the percentage of main memory resource
%occupation, where: {\it $\theta $} is the total amount of main memory; {\it
%$\sigma $} is the amount of main memory used by a process and {\it p} is the
%number of system processes.
%\begin{equation}
%\label{eq2}
%{\rm O}_{mem} =\frac{\left( {\sum\nolimits_{i=0}^p {\sigma _i } }
%\right)}{\theta }
%\end{equation}
%The new load index, {\it I}$_{comp}$, is defined by the equation (3), where:
%${\rm O}_{cpu} $ is the percentage of CPU resource occupation and ${\rm
%O}_{mem} $ is the percentage of main memory resource occupation.
%\begin{equation}
%\label{eq3}
%I_{comp} =\frac{(O_{cpu} +O_{mem} )}{2}
%\end{equation}
%This load index considers the CPU and memory occupations of each computer of
%the system. The occupation of each resource is divided by its total
%capacity, generating an occupation percentage. By summing up the CPU and
%memory occupations it is generated as a single index, which is handled by
%the whole system.
%
%This load index helps the load balancing algorithm \newline
%to define the load states of the computers with \newline
%higher precision. This precision improves the homogeneity of load
%distribution (Shivaratri et al., 1992; Mello \newline
%et al., 2003).
%
%{\small {\bf 3.3 Location policy}}
%
%The selection of the best computer to execute a process received by the
%system is made by using the tables contained in each computer of the tree.
%Each computer has the updated information related to its subtree. This
%information is propagated until it reaches the root computer of the system,
%located at level zero. A request to execute the process in the system is
%always received by the root computer and this computer starts a deep search
%through the tree until it finds the best computer of the environment.
%
%The deep search in the tree is started on the root computer. This computer
%compares its load to the ones belonging to the other computers of its
%subtree. Observe that the root computer does not have the load information
%of all system computers. The root computer has only a load value that
%resumes the load of its subtrees. If the root computer had all system
%computers' load it could send the process directly to the laziest node. This
%technique would be similar to the Central algorithm (Zhou and Ferrari,
%1987), generating many messages, overloading the computer network. In case
%the root computer has the lowest load, it executes the process. If not, it
%sends a request to the best computer of its subtree, which continues the
%same searching process until it finds the idlest computer in the system.
%
%{\small {\bf 3.4 Transference policy}}
%
%The TLBA provides support for the check pointing and migration of processes
%initiated in the system. When a computer updates its local load information
%it also analyses the percentage occupation of the system. In case the system
%load is above a pre-determined limit it generates an analysis message for
%the migration of processes that will follow. This message is sent to the
%root computer of the system, which calculates the average occupation of the
%whole system.
%
%The average occupation of the whole system is calculated by dividing the
%total load of the system by the number of computers. The root computer is
%capable of making this calculation as it has the updated load information of
%the whole system. This value, calculated by the root computer, is sent back
%to the computer that has sent an analysis message for the migration that
%will follow.
%
%The computer that sent an analysis message for the succeeding migration
%compares its load to the average load of the remaining computers of the
%system. If its load is higher than the other ones, it starts the check
%pointing and requests the root computer to search for the idlest computer in
%the system (Section 3.3). After finding the idlest computer, it submits one
%of its processes. If its load is lower or similar to the ones belonging to
%the remaining computers in the system, it does not make the check pointing
%and migration of processes.
%
%{\small {\bf 3.5 Other considerations}}
%
%The computers participate in the tree through the decisions made by a
%Broker. This Broker is a software component, which receives interested
%computers' requisitions in participating in the tree. The Broker defines
%where a computer will be put. The goal of the Broker is to create a balanced
%tree according to the computer's capacity. The computer's capacity is
%measured though a benchmark program; this program is run before the computer
%is placed in the tree.
%
%The computers of a higher or lower level detect the failure of a computer.
%The higher levels identify failures when trying to send load information
%(Section 3.1). The lower levels identify failures when selecting the best
%computer to run a process (Section 3.3). Once a computer detects a failure
%it sends a message to the Broker, which remounts the tree structure. The
%Broker can be running on several computers avoiding a single point of
%failure. If a system administrator does not want to use the Broker, he/she
%can manually configure the environment, setting the tree levels and
%computers per level. However, manual configurations cannot use the
%advantages of the failure treatment offered by the Broker.
%
%Another relevant aspect is that the system administrator defines the number
%of nodes per tree level. Several nodes per level can increase the generated
%messages between levels, overloading the computer network. Fewer nodes per
%level make difficult, the deep search to find the best computer to run a
%process (Section 3.3).
%
%{\small {\bf 4 SIMULATIONS}}
%
%The simulations compare the behaviour of the TLBA to the improved Lowest
%(Mello et al., 2003). The improved Lowest is chosen because it showed a
%better performance than the Stable Symmetrically Initiated (Mello et al.,
%2003) which was proposed by Shivaratri et al. (1992) as the best solution.
%The simulations are subdivided into the following groups:
%
%\begin{itemize}
%\item simulations analysing a small system composed of computers with homogeneous and heterogeneous processing capacity
%\item simulations analysing a large system composed of computers with homogeneous and heterogeneous processing capacity
%\item simulations to analyse the number of messages that pass through the TLBA and improved Lowest communication system.
%\end{itemize}
%These simulation groups permit analyses of TLBA on different systems and to
%check its possibilities. We \newline
%used seven computers for the small system and 781 for the large ones. These
%numbers were chosen just to create symmetrical trees for the tests. For
%seven computers it created a tree composed of three levels, where it was two
%computers per level. For 781 computers it created a tree composed by five
%levels, where it was five computers \newline
%per level.
%
%This section uses tables to present the simulation results, because they
%show more data precision. A Poisson point distribution was used to simulate
%the process arrival at the system; the same probability distribution
%function used by Zhou and Ferrari (1987), Theimer and Lantz (1988) and
%Shivaratri et al. (1992).
%
%The following sections show the simulation groups and their respective
%analyses.
%
%{\small {\bf 4.1 Comparing TLBA and improved lowest average response times
%on small systems}}
%
%Table 1 presents the results obtained by the simulations conducted on an
%environment composed of seven homogeneous computers. The improved Lowest
%algorithm considered a subset of three computers to define the idlest one
%and, therefore, to receive a process initiated in the system. The Poisson
%probability distribution function used to define the processes arrival has
%an average of 100~seconds. The capacity of each computer in the system is
%368 cycles per millisecond. 320 processes have been submitted to the system.
%
%Table 2 shows the results obtained on the simulations conducted in an
%environment composed of seven heterogeneous computers. In this simulation we
%used a Poisson probability distribution function to define the processes
%arrival with average of 100~seconds. The capacity of four computers of the
%system is 368 cycles per \newline
% \newline
% \newline
%millisecond and the other three computers have processing capacity of 139
%cycles per millisecond. 320 processes have been submitted to the system and
%a subset of three computers was considered to find the idlest computer in
%the improved Lowest algorithm.
%
%{\small {\bf Table 1~~~}}{\small {\it Response time variation of the lowest
%algorithm to the different occupations of the process}}
%
%\begin{table}[htbp]
%\begin{center}
%\begin{tabular}{|l|l|l|}
%\hline
%{\small {\it Occupation per process }}{\small (cycles)}{\small  }&
%{\small {\it Average response time of the improved lowest algorithm in a homogeneous environment }}{\small (ms)}{\small  }&
%{\small {\it Average response time of the TLBA in a homogeneous environment }}{\small (ms)}{\small  } \\
%\hline
%{\small 1.00~E~+~01}&
%{\small 6.1275533000~E+~05}&
%{\small 6.0450143000~E~+~05} \\
%\hline
%{\small 1.00~E~+~02}&
%{\small 6.3940207300~E~+~06}&
%{\small 6.3176135300~E~+~06} \\
%\hline
%{\small 1.00~E~+~03}&
%{\small 6.4152160200~E~+~07}&
%{\small 6.3446532460~E~+~07} \\
%\hline
%{\small 1.00~E~+~04}&
%{\small 6.4098737963~E~+~08}&
%{\small 6.3473560175~E~+~08} \\
%\hline
%{\small 1.00~E~+~05}&
%{\small 6.4189585691~E~+~09}&
%{\small 6.3476263532~E~+~09} \\
%\hline
%{\small 1.00~E~+~06}&
%{\small 6.5020352364~E~+~10}&
%{\small 6.3476532508~E~+~10} \\
%\hline
%{\small 1.00~E~+~07}&
%{\small 6.4361410067~E~+~11}&
%{\small 6.3476559492~E~+~11} \\
%\hline
%{\small 1.00~E~+~08}&
%{\small 6.4261208947~E~+~12}&
%{\small 6.3476562200~E~+~12} \\
%\hline
%{\small 1.00~E~+~09}&
%{\small 6.4770720080~E~+~13}&
%{\small 6.3476562470~E~+~13} \\
%\hline
%{\small 1.00~E~+~10}&
%{\small 6.4230638584~E~+~14}&
%{\small 6.3476562497~E~+~14} \\
%\hline
%{\small 1.00~E~+~11}&
%{\small 6.5764266304~E~+~15}&
%{\small 6.3476562500~E~+~15} \\
%\hline
%{\small 1.00~E~+~12}&
%{\small 6.4104959239~E~+~16}&
%{\small 6.3476562500~E~+~16} \\
%\hline
%\end{tabular}
%\label{tab1}
%\end{center}
%\end{table}
%
%{\small {\bf Table 2~~~}}{\small {\it Lowest algorithm response times for
%the different process occupation at a heterogeneous system}}
%
%\begin{table}[htbp]
%\begin{center}
%\begin{tabular}{|l|l|l|}
%\hline
%{\small {\it Occupation per process }}{\small (cycles)}{\small  }&
%{\small {\it Average response time of the improved lowest algorithm in a heterogeneous environment }}{\small (ms)}{\small  }&
%{\small {\it Average response time of the TLBA in a heterogeneous environment }}{\small (ms)}{\small  } \\
%\hline
%{\small 1.00~E~+~01}&
%{\small 8.7436701000~E~+~05}&
%{\small 8.3431215000~E~+~05} \\
%\hline
%{\small 1.00~E~+~02}&
%{\small 8.9294303600~E~+~06}&
%{\small 8.6260096700~E~+~06} \\
%\hline
%{\small 1.00~E~+~03}&
%{\small 8.9918432930~E~+~07}&
%{\small 8.6541094870~E~+~07} \\
%\hline
%{\small 1.00~E~+~04}&
%{\small 8.9724402245~E~+~08}&
%{\small 8.6569206619~E~+~08} \\
%\hline
%{\small \textsc{1.00~E}}{\small ~}{\small \textsc{+~05}}&
%{\small 8.9697114641~E~+~09}&
%{\small 8.6572026521~E~+~09} \\
%\hline
%{\small 1.00~E~+~06}&
%{\small 9.0185968863~E~+~10}&
%{\small 8.6572308610~E~+~10} \\
%\hline
%{\small 1.00~E~+~07}&
%{\small 9.0240793834~E~+~11}&
%{\small 8.6572336769~E~+~11} \\
%\hline
%{\small 1.00~E~+~08}&
%{\small 8.9810014499~E~+~12}&
%{\small 8.6572339589~E~+~12} \\
%\hline
%{\small 1.00~E~+~09}&
%{\small 8.9777274689~E~+~13}&
%{\small 8.6572339869~E~+~13} \\
%\hline
%{\small 1.00~E~+~10}&
%{\small 8.9860080004~E~+~14}&
%{\small 8.6572339897~E~+~14} \\
%\hline
%{\small 1.00~E~+~11}&
%{\small 8.9554548820~E~+~15}&
%{\small 8.6572339900~E~+~15} \\
%\hline
%{\small 1.00~E~+~12}&
%{\small 8.9532098574~E~+~16}&
%{\small 8.6572339900~E~+~16} \\
%\hline
%\end{tabular}
%\label{tab2}
%\end{center}
%\end{table}
%
%Analysing the results presented in Tables 1 and 2 we can conclude that the
%average response times of TLBA are lower than the ones generated by the
%improved Lowest algorithm. Thus, we can conclude that TLBA offers higher
%performance and consequently the better results.
%
%{\small {\bf 4.2 Comparing TLBA and improved lowest average response times
%on large systems}}
%
%The following simulations compare the improved Lowest to the TLBA in a
%homogeneous environment composed of 781 computers. On these simulations,
%35,145 processes were submitted to the environment, based on the Poisson
%probability distribution function with average 100~seconds. Each computer
%capacity is 368~cycles/ms. For the Lowest algorithm it considered a subset
%of eleven computers that were selected on a random basis and their loads
%were analysed to allow the definition of the idlest computer. Table 3
%presents the results obtained on the simulations.
%
%The same environment composed of 781 computers was simulated, however, this
%time computers with heterogeneous capacities were used: 391 of them had a
%368~cycles/ms capacity and 390 of them had a 139~cycles/ms capacity. The
%results obtained on these simulations are shown in Table 4.
%
%{\small {\bf Table~3~~~}}{\small {\it Response time related to the
%occupation per process of lowest algorithm}}
%
%\begin{table}[htbp]
%\begin{center}
%\begin{tabular}{|l|l|l|}
%\hline
%{\small {\it Occupation per process }}{\small (cycles)}{\small  }&
%{\small {\it Average response time of the improved lowest algorithm in a homogeneous environment }}{\small (ms)}{\small  }&
%{\small {\it Average response time of the TLBA in a homogeneous environment }}{\small (ms)}{\small  } \\
%\hline
%{\small 1.00~E~+~04}&
%{\small 6.2159995608~E~+~08}&
%{\small 6.2156474184~E~+~08} \\
%\hline
%{\small 1.00~E~+~05}&
%{\small \textsc{6.2469085561}}{\small ~}{\small \textsc{E}}{\small ~}{\small \textsc{+}}{\small ~}{\small \textsc{09}}&
%{\small 6.2465734548~E~+~09} \\
%\hline
%{\small 1.00~E~+~06}&
%{\small 6.2500016636~E~+~10}&
%{\small 6.2496667285~E~+~10} \\
%\hline
%{\small 1.00~E~+~07}&
%{\small 6.2503193101~E~+~11}&
%{\small 6.2499760509~E~+~11} \\
%\hline
%{\small 1.00~E~+~08}&
%{\small 6.2503454303~E~+~12}&
%{\small 6.2500069804~E~+~12} \\
%\hline
%{\small 1.00~E~+~09}&
%{\small 6.2503491403~E~+~13}&
%{\small 6.2500100731~E~+~13} \\
%\hline
%{\small 1.00~E~+~10}&
%{\small 6.2503482897~E~+~14}&
%{\small 6.2500103823~E~+~14} \\
%\hline
%{\small 1.00~E~+~11}&
%{\small 6.2503475474~E~+~15}&
%{\small 6.2500104132~E~+~15} \\
%\hline
%{\small 1.00~E~+~12}&
%{\small 6.2503488649~E~+~16}&
%{\small 6.2500104163~E~+~16} \\
%\hline
%\end{tabular}
%\label{tab3}
%\end{center}
%\end{table}
%
%{\small {\bf Table~4~~~}}{\small {\it Response times obtained at different
%process occupations of lowest algorithm}}
%
%\begin{table}[htbp]
%\begin{center}
%\begin{tabular}{|l|l|l|}
%\hline
%{\small {\it Occupation per process }}{\small (cycles)}{\small  }&
%{\small {\it Average Response Time of the Improved Lowest Algorithm in an homogeneous environment }}{\small (ms)}{\small  }&
%{\small {\it Average Response Time of the TLBA in an homogeneous environment }}{\small (ms)}{\small  } \\
%\hline
%{\small 1.00~E~+~04}&
%{\small 9.0352098932~E~+~08}&
%{\small 9.0349469055~E~+~08} \\
%\hline
%{\small \textsc{1.00~E~+~05}}&
%{\small 9.0661207290~E~+~09}&
%{\small 9.0658727685~E~+~09} \\
%\hline
%{\small \textsc{1.00~E~+~06}}&
%{\small 9.0692197539~E~+~10}&
%{\small 9.0689656981~E~+~10} \\
%\hline
%{\small 1.00~E~+~07}&
%{\small 9.0695255607~E~+~11}&
%{\small 9.0692749095~E~+~11} \\
%\hline
%{\small 1.00~E~+~08}&
%{\small 9.0695560153~E~+~12}&
%{\small 9.0693058444~E~+~12} \\
%\hline
%{\small 1.00~E~+~09}&
%{\small 9.0695569517~E~+~13}&
%{\small 9.0693089372~E~+~13} \\
%\hline
%{\small 1.00~E~+~10}&
%{\small 9.0695613143~E~+~14}&
%{\small 9.0693092466~E~+~14} \\
%\hline
%{\small 1.00~E~+~11}&
%{\small 9.0695587575~E~+~15}&
%{\small 9.0693092776~E~+~15} \\
%\hline
%{\small 1.00~E~+~12}&
%{\small 9.0695602819~E~+~16}&
%{\small 9.0693092806~E~+~16} \\
%\hline
%\end{tabular}
%\label{tab4}
%\end{center}
%\end{table}
%
%Analysing the results presented in Tables 3 and 4 we can conclude that the
%average response times of TLBA are lower than the ones generated by the
%improved Lowest algorithm. Thus, we can conclude that TLBA offers higher
%performance and consequently, better results.
%
%{\small {\bf 4.3 Simulations that analyse the number of messages generated
%for the TLBA and improved lowest algorithms}}
%
%Simulations were carried out to analyse the traffic of messages exchanged
%among the computers when using the TLBA and improved Lowest algorithms. The
%simulated environment is composed of seven computers segmented into three
%levels with two computers on each level. In the improved Lowest case, the
%subset of computers analysed before the load balancing operation is composed
%of three computers. The number of processes that arrive at the system varies
%from 10 to 350. The Poisson probability distribution function related to the
%process arrival has an average of 3~s. Each computer capacity is 368 cycles
%per millisecond.
%
%The graph on Figure 2 shows the number of messages exchanged among the
%computers on Lowest algorithm and among TLBA levels.
%
%\begin{figure}[htbp]
%\centerline{\includegraphics[width=3.27in,height=2.10in]{sample2.eps}}
%\label{fig2}
%\end{figure}
%
%{\small {\bf Figure 2~~~}}{\small {\it Number of messages exchanged among
%the computers on lowest and TLBA algorithms}}
%
%Due to the TLBA tree format it is possible to segment each level at a
%physically distinct network and this causes less overload on the
%communication system. Figure 2 shows three simulated situations: the first
%one using the TLBA where there is a physically distinct network for each
%level; the improved Lowest, and the TLBA in a physically single network.
%
%The TLBA generates fewer messages per level than the ones generated by the
%improved lowest. The number of messages that pass through the communication
%network is much higher on lowest. Even when using the TLBA in a single
%network, there is a significant decrease in the number of messages when
%compared to the lowest.
%
%Both TLBA and improved Lowest show variations in the number of messages
%depending on the number of executed processes. Lowest generates messages
%based on the computers subset analysed to initiate a load balancing
%operation, whilst TLBA generates a deep search message about the tree to
%search the best computer to execute the process. The TLBA also generates
%updating messages on the environment occupation and these messages run from
%the leaves to the root of the virtual tree.
%
%Analysing Table 5, we may conclude that the number of messages on the TLBA
%is 8.647 times lower. The TLBA on a single network generates 2.88235 times
%less messages than the improved Lowest. In both situations the TLBA causes
%less overload to the communication system.
%
%{\small {\bf Table 5~~~}}{\small {\it Number of messages achieved at 350
%processes of the environment}}
%
%\begin{table}[htbp]
%\begin{center}
%\begin{tabular}{|l|l|l|}
%\hline
%{\small {\it Improved lowest}}&
%{\small {\it TLBA}}&
%{\small {\it TLBA at a single network}} \\
%\hline
%{\small 2,450}&
%{\small 283.3333}&
%{\small 850.00} \\
%\hline
%\end{tabular}
%\label{tab5}
%\end{center}
%\end{table}
%
%{\small {\bf 4.4 Simulations varying the number of computers per level}}
%
%Simulations were conducted to analyse the impacts caused by the variation on
%the number of levels and number of computers per level that make up the TLBA
%tree.
%
%The environment used on these simulations contained 781 homogeneous
%computers with a capacity of 368 cycles per millisecond. 3,000 processes
%were submitted to the environment based on the Poisson probability
%distribution function with average 3~seconds. Three situations were
%simulated for the TLBA:
%
%\begin{itemize}
%\item the first one had two levels with one computer at the first level and 780 at the second one
%\item the second one had five levels with five computers \newline
%per level
%\item the third one had 781 levels with one computer per level.
%\end{itemize}
%Figure 3 shows the results obtained on the TLBA and improved Lowest
%algorithm. We may note that Lowest generates a constant number of messages
%that are equal to 69,000.00, whilst the number of messages on TLBA varies
%according to the number of levels and computers per level. This variation is
%about 182.36 for five levels, 5,996.00 for two levels and 566,133.00 for 781
%levels.
%
%\begin{figure}[htbp]
%\centerline{\includegraphics[width=3.39in,height=2.45in]{sample3.eps}}
%\label{fig3}
%\end{figure}
%
%{\small {\bf Figure 3~~~}}{\small {\it Messages exchanged among computers
%segmented by level}}
%
%The choice for an intermediate number of levels generates a lower traffic on
%the communication system, which increases the system scalability. When a
%computer per level is used, there is an overload on the communication among
%the computers, which decreases the final efficiency of the system making it
%not scalable. The overload happens due to the number of levels roamed to
%find out the best computer in the system to execute a received process and
%to update the information that propagates forward to the root computer.
%
%The definition of an intermediate number of levels allows the creation of
%subnets. Each subnet is formed by a number of computers. The system
%segmentation into levels composed of physically distinct networks generates
%a lower traffic on the communication system, as most of the messages are
%exchanged among the computers of a certain level, which transit on the
%physical network of this level. To create a subnet, a switch per level is
%necessary. For instance, a switch is used to interconnect the computer
%placed in a n level, to ones of the {\it n}~--~1 level. A computer of the
%{\it n}~--~1 level needs to have two network interface cards, one to connect
%to {\it n} level through one switch and another to connect to {\it n}~--~2
%level. To create different subnets, the system administrator must define the
%tree structure as static, so he/she cannot use the broker as implemented so
%far (Section 3.5).
%
%{\small {\bf 5 COMPARATIVE STUDY OF THE TLBA PROTOTYPE AND SIMULATOR}}
%
%In order to confirm the TLBA's feasibility, a prototype was implemented
%using the Linux operating system as the test environment. This section
%compares the results obtained on the executions of this prototype to the
%simulation results GNU/GCC Supported Platforms (2003).
%
%The prototype was submitted to two environment configurations: a homogeneous
%one and a heterogeneous one. The homogeneous environment was composed of
%seven computers with a 368~cycles/ms capacity. The heterogeneous environment
%was composed of two computers with a 139~cycles/ms capacity and five
%computers with a 368~cycles/ms capacity. The simulated and real environment
%used the same parameters that permit comparison of both.
%
%Table 6 presents the results obtained on the prototype executions and the
%simulation results at homogeneous environments. The executions were carried
%out on processes that occupy 10,330,000 cycles in three distinct situations.
%In the first case, processes that occupied only CPU, without doing the
%context switch, were submitted. In the second case, processes that occupied
%the CPU and made calls to the kernel's sleep function were submitted, which
%totalled 512,500~ms per process. In the third and last case, processes that
%made up sleep time of 1,024,000~ms each were submitted. These sleep times
%were defined so that the processes could last a longer time to be completed,
%which allowed the whole system to have more processes executing
%simultaneously. In all cases, 350 processes were submitted to the
%environment using a Poisson function for probability distribution of process
%arrival with average 3~seconds. Two computers per level were defined to make
%up a communication tree among the TBLA modules, as shown on Figure 4. All
%computers were connected through a 100~Mbits switch.
%
%{\small {\bf Table 6~~~}}{\small {\it Response times at the homogeneous
%environment (using the prototype and the simulator)}}
%
%\begin{table}[htbp]
%\begin{center}
%\begin{tabular}{|l|l|l|l|}
%\hline
%{\footnotesize {\it Cycles}}&
%{\footnotesize {\it Simulator }}{\footnotesize (ms)}{\footnotesize  }&
%{\footnotesize {\it Prototype }}{\footnotesize (ms)}{\footnotesize  }&
%{\footnotesize {\it Variation}} \\
%\hline
%{\footnotesize 10330000}&
%{\footnotesize 698,125.60}&
%{\footnotesize 697,645.00}&
%{\footnotesize 0.00068889} \\
%\hline
%{\footnotesize 10330000~+~512500~sleep~ms}&
%{\footnotesize 1,210,625.60}&
%{\footnotesize 1,194,509.00}&
%{\footnotesize 0.013492239} \\
%\hline
%{\footnotesize 10330000~+~024000~sleep~ms}&
%{\footnotesize 1,722,125.60}&
%{\footnotesize 1,760,153.00}&
%{\footnotesize 0.022081664} \\
%\hline
%\end{tabular}
%\label{tab6}
%\end{center}
%\end{table}
%
%\begin{figure}[htbp]
%\centerline{\includegraphics[width=3.33in,height=1.73in]{sample4.eps}}
%\label{fig4}
%\end{figure}
%
%\begin{center}
%{\small {\bf Figure 4~~~}}{\small {\it Connecting tree created by TLBA}}
%\end{center}
%
%The number and occupation of processes submitted to the environment were
%defined to obtain a TLBA analysis for high load environments. The three
%analysed cases showed the results in situations where there are load peaks;
%situations where the high load is maintained for an average period of time;
%situations where the load is maintained for long periods of time.
%
%Observing Table 6, a small variation between the actual and simulated values
%may be noted. This variation is from 0.068889{\%} to 2.2081664{\%}. The low
%variation in results validates the simulator use for the feasibility
%analysis on the creation of load balancing environments with the TLBA. The
%graph on Figure 5 shows these results.
%
%\begin{figure}[htbp]
%\centerline{\includegraphics[width=3.12in,height=2.33in]{sample5.eps}}
%\label{fig5}
%\end{figure}
%
%{\small {\bf Figure~5}}{\small ~~~}{\small {\it Response times for the
%prototype executions and simulations in a homogeneous environment}}
%
%Table 7 shows the average number of load balancing messages exchanged on the
%actual environment, represented by the prototype and simulation executions.
%The variation on the number of messages between the actual system and the
%simulated one is 5.8823529{\%}, and this figure also confirms that the
%simulator can be used to forecast the behaviour of a certain environment
%that aims to use the TLBA.
%
%{\small {\bf Table 7~~~}}{\small {\it Messages passing through the network
%to the actual and simulated environments}}
%
%\begin{table}[htbp]
%\begin{center}
%\begin{tabular}{|l|l|l|}
%\hline
%{\small }&
%{\small {\it Per level}}&
%{\small {\it Total}} \\
%\hline
%{\small Simulator}&
%{\small 283.3333333}&
%{\small 850.00} \\
%\hline
%{\small Prototype}&
%{\small 300.00}&
%{\small 900.00} \\
%\hline
%{\small Variation}&
%{\small 0.058823529}&
%{\small 0.058823529} \\
%\hline
%\end{tabular}
%\label{tab7}
%\end{center}
%\end{table}
%
%Table 7 shows a column for the number of messages exchanged among the levels
%and another one for the \newline
%total messages exchanged on the environment, if the option of using a single
%network is chosen, the number of generated messages is found on the `Total'
%column. If the option of using physically distinct networks is chosen, the
%average number of messages is found on the `per level' column.
%
%The actual executions and simulations on the heterogeneous environment were
%conducted according to the same pattern followed on the homogeneous
%environment. The heterogeneous environment was composed of 5 computers with
%a 368 cycles/ms capacity and 2 computers with a 139 cycles/ms capacity.
%
%Table 8 shows the results obtained on the executions of the TLBA prototype
%and simulator in a determined heterogeneous environment. The processes were
%submitted on the same three situations previously defined for the
%homogeneous environment. On each test, 350 processes were submitted to the
%environment by using a Poisson distribution function with average of
%3~seconds. It may be noted that the variation between the simulated response
%times and the actual ones was from 1 to 4{\%}. The graph on Figure 6 shows
%these results.
%
%{\small {\bf Table 8}}{\small ~~~}{\small {\it Response times in the
%heterogeneous environment (using the prototype and the simulator)}}
%
%\begin{table}[htbp]
%\begin{center}
%\begin{tabular}{|l|l|l|l|}
%\hline
%{\small {\it Cycles}}&
%{\small {\it Simulator }}{\small (ms)}{\small  }&
%{\small {\it Prototype }}{\small (ms)}{\small  }&
%{\small {\it Variation}} \\
%\hline
%{\small 10330000}&
%{\small 781,348.89}&
%{\small 750,352.93}&
%{\small 0.04} \\
%\hline
%{\small 10330000~+~512500 ms de sleep}&
%{\small 1,293,848.89}&
%{\small 1,279,203.00}&
%{\small 0.01} \\
%\hline
%{\small 10330000~+~024000 ms de sleep}&
%{\small 1,805,348.89}&
%{\small 1,742,498.00}&
%{\small 0.04} \\
%\hline
%\end{tabular}
%\label{tab8}
%\end{center}
%\end{table}
%
%Table 9 shows the number of messages generated \newline
%both on the actual environment (prototype) and on \newline
%the simulated one. It may be noted tat the variation \newline
%between the expected and actual number of messages is about 7{\%}.
%
%\begin{figure}[htbp]
%\centerline{\includegraphics[width=3.28in,height=2.88in]{sample6.eps}}
%\label{fig6}
%\end{figure}
%
%{\small {\bf Figure 6~~~}}{\small {\it Response times for the prototype
%executions and simulations at a heterogeneous environment}}
%
%{\small {\bf Table 9~~~}}{\small {\it Messages passing through the network
%to the actual and simulated environments}}
%
%\begin{table}[htbp]
%\begin{center}
%\begin{tabular}{|l|l|l|}
%\hline
%{\small }&
%{\small {\it Per level}}&
%{\small {\it Total}} \\
%\hline
%{\small Simulator}&
%{\small 257.00}&
%{\small 771.00} \\
%\hline
%{\small Prototype}&
%{\small 275.00}&
%{\small 825.00} \\
%\hline
%{\small Variation}&
%{\small 0.070038911}&
%{\small 0.070038911} \\
%\hline
%\end{tabular}
%\label{tab9}
%\end{center}
%\end{table}
%
%As it may be observed, the values obtained on the simulations were confirmed
%afterwards by the prototype execution and this validates the simulations. It
%can also be highlighted that all actual executions were conducted with the
%aim of overloading the system. Thus, the comparisons between the prototype
%(actual system) and simulator could be made under extreme situations. In
%these situations the low variation of the number of exchanged messages to
%perform the load balancing operations and processes response times were
%confirmed.
%
%{\small {\bf 6 CONCLUSIONS}}
%
%The paper analyses the TLBA algorithm, which creates a virtual connecting
%tree to update the information on the system occupation. This tree is used
%to carry out deep searches that allow the idlest computer to be found as
%this computer is the one that should execute a process received by the
%system at a certain instant. Analysing the simulations presented on Section
%4, it was concluded that the TLBA algorithm decreases the number of messages
%generated at a certain environment and generates shorter response times than
%the improved Lowest algorithm (Mello et al., 2003).
%
%In order to confirm the results obtained on the simulations, a prototype was
%implemented on the Linux operating system. This prototype was submitted to
%tests whose results confirmed the low variation on the response times and
%the number of exchanged messages on the load balancing operations.
%
%The low variations between the TLBA prototype and simulator confirmed the
%simulator usefulness to forecast \newline
%the behaviour of environments that use the TLBA \newline
%for load balancing and, consequently, the validation of the comparisons made
%between the TLBA and improved \newline
%Lowest algorithms (Section 4) where TLBA showed the best results.

% \sectiona{ACKNOWLEDGMENT}
% 
% We would like to thank Dr. Gonzalo Travieso for his collaboration
% in this work.

\bibliographystyle{apalike}
%\NUMBIB
\begin{thebibliography}{99}
%
\bibitem{Ax} R. Axelrod, {\em The complexity of cooperation}, Princeton 
University Press, 1997.
%
\bibitem{BR} J. Berstel and G. Reutenauer, {\em Rational series and their 
languages}, EATCS, 1988.
%
\bibitem{Bo1} Bourbaki N., {\em Elements of Mathematics: General Topology}, 
Chapters 5-10, Springer-Verlag Telos (dec. 1998).
%
\bibitem{gst} L. von Bertalanffy, {\em General System Theory}, Georges Braziller 
Ed., 1968.
\bibitem{BFJOP1} C. Bertelle, M. Flouret, V. Jay, D. Olivier, and J.-L. Ponty 
"Adaptive behaviour for prisoner dilemma 
strategies based on automata with multiplicities." In {\em ESS 2002 Conf., 
Dresden} (Germany), October 2002. 
%
\bibitem{BFJOP2}C. Bertelle, M. Flouret, V. Jay, D. Olivier, and J.-L. Ponty 
"Genetic algorithms on automata with 
multiplicities for adaptive agent behaviour in emergent organizations" In {\em 
SCI'2001}, Orlando, Florida, USA, 
22-25th July 2001.
%
\bibitem{DHKL} G. Duchamp, Hatem Hadj-Kacem and Eric Laugerotte, 
"Algebraic elimination of $\epsilon$-transitions", {\em DMTCS, Volume 7} n. 1 
(2005), pp. 51-70.
%
\bibitem{DC1} G. Duchamp, J-M Champarnaud, {\it Derivatives of rational 
expressions 
and related theorems}, Theoretical Computer Science {\bf 313} (2004).
%
\bibitem{Eb} N. Eber, {\em Th\'eorie des jeux}, Dunod, 2004.
%
\bibitem{Ei} S. Eilenberg, {\em Automata, languages and machines}, Vol. A and B, 
Academic press, 1976.
%
\bibitem{Fe} J. Ferber, {\em Multi-agent system}, Addison-Wesley, 1999.
%
\bibitem{IPL} M. Flouret, E. Laugerotte, {\em Noncommutative minimization algorithms}, Info. Proc. Letters. (2003)
%
\bibitem{FOW} L.J. Fogel, A.J. Owens, M.J. Welsh, {\em Artificial intelligence 
through simulated evolution}, John Wiley, 1966.
%
\bibitem{epnads} R. Ghnemat, K. Khatatneh, S. Oqeili, C. Bertelle, G.H.E. Duchamp 
{\em Automata-based adaptive behavior 
for economic modeling using game theory}, Proc. of EPNADS�05 (Emergent Properties
In Natural and Artificial Dynamical Systems), Paris, November 17th, 2005, Springer 
(In press)
%
\bibitem{Go} J.S. Golan, {\em Power algebras over semirings}, Kluwer Academic 
Publishers, 1999.
%
\bibitem{Gol} D.E. Goldberg, {\em Genetic Algorithms}, Addison-Wesley, 1989.   
%
%
\bibitem{MCA} J. von zur Gathen and J. Gerahrd, {\em Modern Computer Algebra}, 
Cambridge (1999).
%
\bibitem{Ho} J. H. Holland, {\em Hidden Order - How adaptation builds 
complexity}, Persus books ed., 1995.
%
\bibitem{HMU} J.E. Hopcroft, R. Motwani, J.D. Ullman, {\em Introduction to 
automata theory, Languages and Computation}, Addison-Wesley, 2001.
%
\bibitem{Ko1} V. A. Kostyantyn, {\em A New Representation of Formal Power Series}, 
FPSAC'04 (Vancouver 2004).
%
\bibitem{Ko} J. Koza, {\em Genetic programming}, Encyclopedia of Computer 
Sciences and Technology, 1997.
%
\bibitem{Mi} M. Mitchell, {\em An introduction to Genetic Algorithms}, The 
MIT Press, 1996.
%
\bibitem{Mo} J.-L. Le Moigne, {\em La mod\'elisation des syst\`emes 
complexes}, Dunod, 1999.
%
\bibitem{Lu} J. -G. Luque, {\em Mono\"\i des et automates admettant un produit de m\'elange : Monoids and automata admitting a shuffle product}, 
Ph. D. University of Rouen (Dec. 1999).
% 
\bibitem{Re} I. Rechenberg, {\em Evolution strategies}, Fromman-Holzboog, 1973.
%
\bibitem{Sc} M.P. Schutzenberger, "On the definition of a family of automata", 
Information and Control {\bf 4}, 245-270 (1961).
%
\bibitem{St} R.P. Stanley, {\em Enumerative combinatorics}, Cambridge University 
Press, 1999.
%
\bibitem{Tr} F. Treves, {\em Topological Vector Spaces, Distributions and 
Kernels}, Acad. Press 1967.
%
\bibitem{We} G. Weiss, ed., {\em Multiagent Systems}, MIT Press, 1999.
%
\end{thebibliography}



% \begin{thebibliography}{99}
% \bibitem[\protect\citeauthoryear{Amir}{2000}]{Amir} %%1
% Amir, Y. {\it et al.} (2000) `An opportunity cost approach for
% job assignment in a scalable computing cluster', {\it IEEE
% Transactions on Parallel and Distributed Systems}, July, Vol.~11,
% No.~7, pp.760--768.
% 
% \bibitem[\protect\citeauthoryear{Anderson and Abraham}{2000}]{Anderson and Abraham} %%1
% Anderson, J.R. and Abraham, S. (2000) `Performance-based
% constraints for multidimensional networks', {\it IEEE
% Transactions on Parallel and Distributed Systems} January,
% Vol.~11, No.~1, pp.21--35.
% 
% \bibitem[\protect\citeauthoryear{Figueira and Berman}{2001}]{Figueira and Berman} %%1
% Figueira, S.M. and Berman, F. (2001) `A slowdown model for
% applications executing on time-shared clusters of workstations',
%  {\it IEEE Transactions on Parallel and Distributed
% Systems}, June, Vol. 12, No. 6, pp.653--670.
% 
% \bibitem[\protect\citeauthoryear{GNU/GCC Supported Platforms}{2003}]{GNU} %%1
% GNU/GCC Supported Platforms (2003) URL:
% http://gcc.gnu.org/install/specific.html, Consulted in: 25th
% June, http://www.icmc.usp.br/$\sim $mello.
% 
% \bibitem[\protect\citeauthoryear{Hsu et al}{2000}]{Hsuetal} %%1
% Hsu, T. {\it et al}. (2000) `Task allocation on a network of
% \newline processors', {\it IEEE Transactions on Parallel
% and Distributed Systems}, December, Vol. 49, No. 12,
%  pp.1339--1353.
% 
% \bibitem[\protect\citeauthoryear{Hui and Chanson}{1999}]{Hui and Chanson} %%1
% Hui, C. and Chanson, S.T. (1999) `Hydrodynamic load balancing',
%  {\it IEEE Transactions on Parallel and Distributed
% Systems}, November, Vol. 10, No. 11, pp.1118--1137.
% 
% \bibitem[\protect\citeauthoryear{Kostin et~al.}{2000}]{Kostinetal} %%1
% Kostin, A.E., Aybay, I. and Oz, G. (2000) `A randomised
% contention-based load-balancing protocol for a distributed
% multiserver queuing system', {\it IEEE Transactions on Parallel
% and Distributed Systems}, December, Vol. 11, No. 12,
%  pp.1252--1273.
% 
% \bibitem[\protect\citeauthoryear{Krueger and Livny}{1987}]{Krueger and Livny} %%1
% Krueger, P. and Livny, M. (1987) `The diverse objectives of
% distributed scheduling policies', {\it Proc. Seventh Int'l Conf.
% Distributed Computing Systems}, IEEE CS Press, Los Alamitos,
% Calif., No. 801, (microfiche only), pp.242--249.
% 
% \bibitem[\protect\citeauthoryear{Mello et~al}{2003}]{Melloetal03} %%1
% Mello, R.F. {\it et al}. (2003) `Comparative study of the
% server-initiated lowest algorithm using a load balancing index
% based on the process behaviour for heterogeneous environment,
% accepted for publication in the special issue of cluster
% computing of the Kluwer', {\it The Journal of Networks, Software
% Tools and Applications.}
% 
% \bibitem[\protect\citeauthoryear{Mello et~al.}{2002b}]{Melloetal02b} %%1
% Mello, R.F., Paiva, M.S. and Trevelin, L.C. (2002b) `OpenTella: a
% peer-to-peer protocol for the load balancing in a system formed
% by a cluster from clusters', {\it 4th International Symposium on
% High Performance Computing ISHPC-IV}, Japan, May.
% 
% \bibitem[\protect\citeauthoryear{Mello et~al.}{2002c}]{Melloetal02c} %%1
% Mello, R.F., Paiva, M.S. and Trevelin, L.C. (2002c) `Analysis on
% the significant information to update the tables on occupation of
% resources by using a peer-to-peer protocol', {\it 16th Annual
% International Symposium on High Performance Computing Systems and
% Applications}, Moncton, New-Bruncwick, Canada, June.
% 
% \bibitem[\protect\citeauthoryear{Mello et~al.}{2002d}]{Melloetal02d} %%1
% Mello, R.F., Paiva, M.S. and Trevelin, L.C. (2002d) `A java
% cluster management service', {\it IEEE International Symposium on
% Network Computing and Applications}, Cambridge, Massachusetts,
% USA, February.
% 
% \bibitem[\protect\citeauthoryear{Mello et~al.}{2002a}]{Melloetal02a} %%1
% Mello, R.F., Paiva, M.S., Trevelin, L.C. and Gonzaga, A. (2002a)
% `Model for resources load evaluation in clusters by  using a
% peer-to-peer protocol', {\it The 2002 International Conference on
% Parallel and Distributed Processing Techniques and Applications},
% Las Vegas, USA, June.
% 
% \bibitem[\protect\citeauthoryear{Mitzenmacher}{2000}]{Mitzenmacher00} %%1
% Mitzenmacher, M. (2000) `How useful is old information?',  {\it
% IEEE Transactions on Parallel and Distributed Systems}, January,
% Vol. 11, No. 1, pp.6--20.
% 
% \bibitem[\protect\citeauthoryear{Mitzenmacher}{2001}]{Mitzenmacher01} %%1
% Mitzenmacher, M. (2001) `The power of two choices in randomised
% load balancing', {\it IEEE Transactions on Parallel and
% Distributed Systems}, October, Vol. 12, No. 10,
% pp.1094--1104\vvp{}.
% 
% \bibitem[\protect\citeauthoryear{Page et~al.}{1993}]{Pageetal} %%1
% Page, I, Jacob, T. and Chern, E. (1993) `Fast algorithms for
% distributed resource allocation', {\it IEEE Transactions on
% Parallel and Distributed Systems}, February, Vol. 4, No. 2,
% pp.188--197.
% 
% \bibitem[\protect\citeauthoryear{Shivaratri et~al.}{1992}]{Shivaratrietal} %%1
% Shivaratri, N.G., Krueger, P. and Singhal, M. (1992) `Load
% distributing for locally distributed systems', {\it IEEE
% Computer,} December, pp.33--44.
% 
% \bibitem[\protect\citeauthoryear{Sinha}{1997}]{Sinha} %%1
% Sinha, P.K. (1997) {\it Distributed Operating Systems: Concepts
% and Design}, IEEE Institute of Electrical and Electronics
% Engineers, Inc, 345 East 47th Street, NY 10017--2394.
% 
% \bibitem[\protect\citeauthoryear{Theimer and Lantz}{1988}]{Theimer and Lantz} %%1
% Theimer, M.M. and Lantz, K.A. (1988) `Finding idle machines in a
% workstation-based distributed systems', {\it Proc. IEEE 8th Int.
% Conf. on Distributed Computing Systems}, pp.112--122.
% 
% \bibitem[\protect\citeauthoryear{Woodside and Monforton}{1993}]{Woodside and Monforton} %%1
% Woodside, C.M. and Monforton, G.G. (1993) `Fast allocation of
% processes in distributed and parallel systems', {\it IEEE
% Transactions on Parallel and Distributed Systems}, February, Vol.
% 4, No. 2, pp.164--174.
% 
% \bibitem[\protect\citeauthoryear{Zhang}{2001}]{Zhang} %%1
% Zhang, Y. (2001) `Impact of workload and system parameters on
% next generation cluster scheduling mechanisms', {\it IEEE
% Transactions on Parallel and Distributed Systems}, September,
% Vol. 12, No. 9, pp.967--985.
% 
% \bibitem[\protect\citeauthoryear{Zhou and Ferrari}{1987}]{Zhou and Ferrari} %%1
% Zhou, S. and Ferrari, D. (1987) {\it An Experimental Study of
% Load Balancing Performance}, Report No. UCB/CSD 87/336, Progress
% Report No. 86.8, Computer Science Division (EECS), University of
% California, Berkeley, California 94720, January, pp.1--27.
% 
% \bibitem[\protect\citeauthoryear{Zomaya and Teh}{2001}]{Zomaya and Teh} %%1
% Zomaya, A.Y. and Teh, Y. (2001) `Observations on using genetic
% algorithms for dynamic load-balancing', {\it IEEE Transactions on
% Parallel and Distributed Systems}, September, Vol. 12, No. 9,
% pp.899--911.
% \end{thebibliography}

\end{document}


