\documentclass[letterpaper]{article}
\usepackage{natbib,alifeconf}
\usepackage{algorithm2e}

\newcommand{\MFM}{\textsc{MFM}}
\newcommand{\MFMs}{\textsc{MFM} \hspace{0.075cm}}

\title{Local Routing in a new Indefinitely Scalable Architecture}
\author{Trent Small\\
\mbox{}\\
The University of New Mexico\\
Albuquerque, NM, 87131-0001\\
tsmall1@unm.edu}


\begin{document}
\maketitle

\begin{abstract}
  Local routing is a problem which most of us face on a daily basis as
  we move around the places we live in. This study proposes several
  routing methods based on road signs in a procedurally generated
  city-like simulation which does not assume knowledge of global
  structures and shows its overall efficiency in a variety of dense
  city environments. We introduce a technique called
  \textit{Intersection-Canalization} which allows for this method to
  be feasible for routing information arbitrarily on an architecture
  with limited resources.
\end{abstract}

\section{Introduction}

\begin{figure*}[ht]
\centering
\includegraphics[width=\textwidth]{figure1v2.eps}
\caption{\footnotesize
         City growth stage: \hspace{0.1cm}
         \textbf{1.} A street creates streets and sidewalks. \hspace{0.1cm}
         \textbf{2.} Streets sometimes create intersections. \hspace{0.1cm}
         \textbf{3.} Intersections create streets. After time, sidewalks create buildings. \hspace{0.1cm}
         \textbf{4.} The city grows. Buildings create cars which travel along roads to find other buildings. \hspace{0.1cm}}
\label{fig1}
\end{figure*}

\subsection{New technologies = new challenges}

Designed for robustness, the \textit{Movable Feast
  Machine}\citep{AckleyCJ} (or briefly \MFM)is a new computer
architecture aimed at spatially distributing computation in a way that
can scale indefinitely. This system is robust to many hardware errors
(for instance, by its distributed nature) as well as software errors
(for instance, by its use of Cellular Automata).

Robustness comes at a price however, as this architecture is
drastically different from the tried and true Von Neumann
architecture. This makes traditional computer problem solving much
more challenging. In fact, thinking traditionally about computer
problem solving in the \MFMs is hardly feasible, particularly problems
which need to access any sort of global state. This brings about many
problems with traditional computing procedures.

\subsection{Routing revisited}

The Von Neumann architecture supplies hardware for getting information
from one end of the machine to the other. Unfortunately, this is
particularly fragile as a single fault in the machine will cause the
communication route to be severed. This is where the \MFMs shines, as
a fault in one part of the machine allows the rest of the machine to
function. However, routing information from one part of the machine to
any other becomes more difficult.

Because it is a Cellular Automata on distributed hardware, the \MFMs
memory on the system corresponds to the location of the tile
directly. This forces any data moving across an \MFMs simulation to
move physically across the machine as well. The small Event Windows of
the \MFMs also make it difficult to know much about the surroundings
of an atom when it is processing an event. The way that the \MFMs is
distributed also makes it difficult to create an absolute addressing
system like the Von Neumann architecture exhibits, making absolute
routing difficult, as well (not to mention that absolute routing is
not indefinitely scalable either, as illustrated by \textsc{IP}v4
\citep{deering1998internet}.

\subsection{A solution by example}

Because the \MFMs is built as an Artificial Life
simulator\citep{AckleyALIFE}, many aspects of the architecture reflect
ones found in the real world. This allows us to examine problems which
the Von Neumann architecture has solved and apply real-world
techniques in order to solve them on the \MFM. Even the humblest of
creatures work on solving this spatial routing problem on a daily
basis, so many angles of inspiration exist.

One solution that comes to mind is based on the idea of a city. Cities
are dense, which allow information and resources to travel only short
distances. Cities also exist upon a heavily structured road system
which allow information to travel quickly. Cities are also diverse,
allowing for many different kinds of information to share the same
structure. All of these properties are useful aspects when routing
inside a computer. Speed and flexibility are two aspects which are
deemed important by the \textit{Vehicle Routing Problem}
(\textsc{VRP}) \citep{cordeau2002guide}, along with accuracy and
simplicity.These are important to keep in mind when routing data as
well.

The efficiency of cities has been studied by many authors. Much focus
has gone into delivery algorithms, but most are more applicable to the
real world with their assumption of global
state\citep{MultPickupQuan}\citep{clarke1964scheduling}\citep{wiering2004simulation}
\citep{lammer2008self}\citep{gershenson2009modeling}. This is not a
luxury that the \MFMs provides.

There has also been research on road density using cellular automata
\citep{nagel1992cellular}, and even the effect of controlling traffic
lights in a cellular automata city to increase traffic efficiency
without collisions \citep{brockfeld2001optimizing}. These simulations
are designed to keep cars from colliding, whereas the simulation we
are looking to create simply needs to route information as quickly and
losslessly as possible. Therefore, we won't focus on the collisions of
cars at all.

It is also worth it to note that city planners appointed by United
Nations Human Settlements Programme are now starting to use tile-based
software to plan cities\citep{MinecraftPlanning}.

\section{Design considerations}

There are many properties of real cities which allow for routing to be
efficient that we can not take advantage of. Most things that are
being routed in the real world are controlled by people whom are able
to remember how to get around the city. The \MFMs only allows an Atom
performing an event to access less than 500 bytes of local
information. This is nowhere near enough information to remember where
building are around the city. Therefore, we must treat every piece of
routed information as if it were new to the city and unable to
navigate without assistance. This brings us to our first design
consideration:

\subsubsection{Local mapping:}
There must exist some method which aides information in approaching
its destination. \\

According to \citep{cordeau2002guide}, a good routing system has four
traits. It is natural to adopt these into our design:

\subsubsection{Routing traits:}
Routing must be fast, accurate, simple, and flexible.\\

Because this software is running on the \MFM, our city should take
advantage of the inherent hardware and software support for
robustness. Thus, we have our final design choice to consider:

\subsubsection{Robustness:}
A city should be long-lived.

A city must be able to work around, ride out, or otherwise recover
from a wide range of perturbations.  Utilizing techniques common to
self-organization \citep{SelfOrgConcept} will increase the robustness
of the city and allow traffic to continue to flow in an organized
manner in many destructive scenarios after a short rebuilding stage.



\section{Limitations and Simplifications}

Simulating real city traffic in the \MFMs is incredibly difficult
because there are simply too many aspects to a city's life.  Some
compromises must be made to our model in order to gather meaningful
information about city routing.

\subsection{Single-lane swapping}

Each street in this model can be seen as a two-way four-lane
road. This is a little tricky however, since each street is a single
atom. In order to make up for this, when a car moves it may swap its
position with either a street or a car that is in the direction it is
moving in. This makes for some interesting dynamics since cars waiting
at an intersection can move towards the front of their queues. These
simple rules allow a two-way one-lane single-atom road to simulate a
two-way four-lane road.

This is not how real traffic works, and it does end up needlessly
using gas while waiting at an intersection, but there has already been
research in these kinds of problems using cellular automata
\citep{nagel1998two} which shows that traffic can flow well even in a
two-lane environment as long as it follows some simple rules.

\subsection{Building types}

Because there is no notion of absolute addressing in the \MFM, there
is no way that a car can hope to find a unique building in this
city. Instead, we introduce \textit{building types}. There are 24
designated types for which a building may emulate. This differs from
the real world in that there are many unique buildings, but most real
world buildings can be placed into categories for simplicity's
sake. For example, most grocery stores are nearly identical, and the
closest one to home is often the one most frequented
\citep{hsu2010grocery}.

\subsection{Map size}

The \MFMs only provides each atom with 71 general-purpose bits to use
for anything an element enginner pleases. If 24 building types are
given, this is only enough to allocate (given that a small number of
other bits are allocated for other purposes) 2 bits per building type
to anything which should make a local map of the nearby city
blocks. Used cleverly, we will see that this limitation does not seem
to impede routing much, but an \MFMs simulator which is able to give
more bits per atom would have allowed for some experimentation of
these map sizes.

\section{Model}

The model consists of a {\it City Growth} stage (which eventually
leads to a local equilibrium), and a {\it Routing} stage. A user
begins the first stage by placing a single Element into an empty \MFMs
grid.

\subsection{City Growth}

The city begins with a single \textsc{Element\_City\_Street}
\textit{(see Fig.\ref{fig1})}, which simply tries to copy itself in a
cardinal direction. If the street encounters an Element other than
something which belongs in the street (namely an
\textsc{Element\_City\_Car}, an \textsc{Element\_City\_Intersection},
or another Street), it replaces that Element with either a Street or
an Intersection depending on its Intersection odds parameter. The
roads continue to grow indefinitely.

As the streets grow, they place \textsc{Element\_City\_Sidewalk}
elements in the sites perpendicular to the direction they are
traveling. Once a Sidewalk has been created, it waits for a
parameterized number of events before creating an
\textsc{Element\_City\_Building} on the side opposite the Street. The
sidewalks are produced solely by the Streets and do not reproduce.

Once an \textsc{Element\_City\_Building} has been created, it begins
to reproduce along the Sidewalk. Each building has a \textsc{type}
parameter, symbolizing the type of building it is, which corresponds
directly to the \textit{building type} limitation. These buildings
only grow up to a maximum size, allowing diversity on every city
block. Once a building has been created, it also gains the capacity to
create an \textsc{Element\_City\_Car} in place of a nearby Street.

The \textsc{Element\_City\_Car} simply drives along a Street by
swapping in the direction of the Street it was created in place of
using the single-lane swapping method described above. A car has a
limited amount of events before it runs out of gas and is consumed by
the system. If a Car has an event next to a Building of the same type
as its destination parameter, it is consumed and the remaining fuel is
reported.

Once the cars begin moving around the city, they may hit a dead end or
the edge of the universe (in which cases they perform a U-turn), or
they will run into an intersection. This is where routing takes
place. The cars, upon arriving at an intersection, wait for the
intersection to make an intelligent decision regarding which direction
they will travel in next. The intersection ultimately moves the car
onto one of its bordering streets which allows the car to continue in
its new direction.

\begin{figure}[h]
\begin{center}
\includegraphics[width=3.2in]{figure2v2.eps}
\vskip 0.25cm
\caption{Sidewalks contain a map of their city block distance from
  every building type.}
\label{fig2}
\end{center}
\end{figure}

\begin{figure*}[ht]
\begin{center}
\includegraphics[width=\textwidth]{graph1.eps}
\vskip 0.25cm
\caption{Summary of routing methods in terms of car arrival
  accuracy, averaged over ten simulated runs.}
\label{graph1}
\end{center}
\end{figure*}

\begin{figure*}[ht]
\begin{center}
\includegraphics[width=\textwidth]{graph2.eps}
\vskip 0.25cm
\caption{Summary of routing methods in terms of gas usage of correctly
  routed cars, averaged over ten simulated runs.}
\label{graph2}
\end{center}
\end{figure*}

\section{Routing methods}

We will be examining several local routing algorithms in this city.

\subsection{Random routing}

This routing algorithm is the most basic of them all. When an
intersection sees a neighboring car, it will choose one of the streets
it borders at random which the car did not come from and will send the
car in that direction. This routing algorithm is akin to wandering
around the city in no organized manner.

\subsection{Sidewalk-Only routing}

This routing algorithm takes advantage of the state inside of the
Sidewalks which border the streets.  Sidewalks build a local map of
the buildings near them. They store an $n$ length array of 2-bit
numbers, where $n$ is the number of building types in the city. This
array stores the distance of this Sidewalk from the building of each
type, measured in city blocks (see Fig.\ref{fig2}). This
local-city-block map is populated using Algorithm \ref{alg1}.

\begin{algorithm}
  \If{I border a building}
  {
    Set my map[building type] to 0
  }
  \For{each building type $t$}
  {
    Get the minimum $m$ of my neighbor's maps for $t$
    Set my map[$t$] to \textsc{MIN}(map[$t$], $m$).
    \\
    \If{There is a Sidewalk across the street from me, $s$}
    {
      Set my map[$t$] to \textsc{MIN}(map[$t$], ($s$[$t$]$ + 1$)).
    }
  }
  \label{alg1}
  \caption{Sidewalk Mapping.}
\end{algorithm}

This map is ultimately read by an Intersection when a Car is
waiting. The Intersection examines the Sidewalks surrounding
neighboring Streets and places the Car on the Street which is between
the blocks closest to its destination. If a car just came from this
direction, it will pick the second best choice, since making a car
perform a U-turn will never help it approach its destination unless it
is facing a dead-end.

Sidewalk-Only routing is prone to problems. When an intersection
decides to send a car down a dead end, it does not remember this and
cars of this type will to be sent to this dead-end every time they
arrive.

\begin{figure*}[ht]
\centering
\includegraphics[width=\textwidth]{city.eps}
\caption{\footnotesize
         A city after its City Growth stage on a medium \MFMs grid.}
\label{fig3}
\end{figure*}

\subsection{Intersection-Canalization routing}

Intersection-Canalization routing builds upon Sidewalk-Only
routing. The intersections are now given a small routing table which
remembers the last direction that it sent a car of each
type. Canalization prevents the problem that Sidewalk-Only routing
creates by re-evalutaing its routing choices less often and trusting
its memory of the city. Training traffic lights using methods more
complicated than canalization also proves to be
successful\citep{tubaishat2007adaptive} which seems to imply that a
smarter traffic light may be more correct.

\section{Results}

These three routing algorithms each ran for ten simulated runs, each
run generating its own city from a single street atom. The results
from each run were then averaged and plotted into Fig.\ref{graph1} and
Fig.\ref{graph2}. These cities were generated with parameters which
placed buildings densely (see Fig.\ref{fig3}), as is the case with
enviornments like New York City.

\subsection{Random routing}

It may be surprising to hear that randomly routing cars around these
cities is an algorithm that performs relatively well. Over ten runs,
the limiting behavior of the random routing algorithm suggests that
cars reach their destinations 91\% of the time without running out of
gas. The density of the city is most likely what helps these cars in
the long run because, although the building types are uniformly
distributed, city blocks are never far apart from blocks which have
similar buildings. However, this also means that one in ten dispatched
cars does not reach its destination before it runs out of gas.

The cars that do reach their destinations do it in a relatively short
amount of time, at an average of 29.4 events after being dispatched.

\subsection{Sidewalk-Only routing}

Routing cars using the Sidewalk-Only technique is an impressive
improvement over the Random routing technique. Even with the dead-end
faults that this algorithm exhibits described earlier, dispatched cars
following road signs reach their destinations at a rate of 98.2\%
after the city growth stage. This is an improvement from nearly
$\frac{1}{10}$ cars not making it to their destinations to less than
$\frac{1}{50}$ cars. This algorithm helps nearly five times as many
vehicles reach their destination.

Destination accuracy is not the only success shown by Sidewalk-Only
routing over Random routing; the average time taken for a car to reach
its destination decreases to 20.05 events, which is a 29.11\% decrease
in gas usage.

\subsection{Intersection-Canalization routing}

Routing cars using the Intersection-Canalization technique yields an
improvement over Sidewalk-Only routing, mainly because it avoids
sending many cars down dead-ends in the city. However, this technique
is only slightly better at Sidewalk-Only routing in getting cars to
their destinations, at a rate of 98.22\% after the city growth stage
and a short training time, an 0.02\% increase from Sidewalk-Only
routing.

Although cars are routed with only a small increase in correctness,
success is found when calculating the average time taken for a car to
reach its destination, which in this case is 17.7 events. This is a
15\% decrease in gas usage from Sidewalk-Only routing. This means that
on average, every car in the city is can operate with only 85\% as
much fuel as was needed in Sidewalk-Only routing.

\section{Conclusion}

These routing algorithms show that, in an environment which is new to
the traffic being routed or has very limited visibility, a routing
system that uses street signs and intersection canalization is rather
effective at helping traffic get to where it needs to go. These
increases in efficiency may seem small, but over time more people are
spending far less time traveling than people who are hopelessly lost
otherwise.

As stated earlier, this routing method does not seem to be applicable
in a real city because of the large amount of information that people
are able to access at any given time. However, considering that these
elements are rather simple, this method works well with the limited
resources given by the \MFM. The small bit fields used on the \MFMs
also make these routing systems less effective, considering that
another 20 bits in each atom would allow for the sidewalk maps to
extend from seeing 3 blocks away to seeing 7 blocks away. These
limitations are what developers of the \MFMs must be wary of and ready
to work around.

We can show that all of our design constraints listed earlier have all
been satisfied by Intersection-Canalization routing. Clearly, the
first consideration is satisfied by sidewalk mapping. This routing
method is fast, because every car is routed in $O(n)$ time where $n$
is the number of building types (and currently, there cannot be more
than 24 building types given the atom body size limitations of the
\MFM). It is accurate, becase 98.2\% of cars arrive safely at their
destinations. Is is simple, since all routing decisions are made using
the simple algorithm described by Algorithm\ref{alg1}. Finally, it is
flexible, since the unused data inside of each car (67 bits if we do
not track gas usage, or 59 bits if we do) is large enough to be
considered a general-use packet for any kind of data
transmission. Finally, the use of self-organizing streets helps
increase the robustness of the city past what we would hope to get out
of a self-assembled city \citep{SelfOrgConcept}.

Considering that this system takes all of our design considerations
into account, we can see that this is an effective routing algorithm
for any kind of information. It can be seen that a city can be
construced in a way that allows traffic to carry data across tile
boundaries, effectively allowing this routing system to route data
between other computational parts of the \MFM (for instance, this
system can be placed on one end of a \textsc{Demon Horde
  Sort}\citep{AckleyALIFE} to route sorted data to another part of the
machine).

\section{Future Work}

In the future on a new build of the \MFM, it would be interesting to
study the effects that larger atom bodies have on these routing
methods. As a whole, larger atom bodies on the \MFMs would allow for
even more complicated routing methods. The adaptive traffic lights
studied in \citep{tubaishat2007adaptive} could theoretically be
implemented, as well as a host of other traffic simulations. This
study shows that small bit fields work, but leaves us wondering if
more state could improve these routing methods.

The \MFMs is still a young architecture which is very much in
development. However, it can be seen by this and other projects that
it is a promising architecture that should be used (maybe after
certain parameters like atom sizes are tweaked) for further
research. I encourage anyone who wishes to use a cellular automata in
the future to try their hand at using the \MFM, as it scales well and
can handle any general-purpose cellular automata.

On top of the routing research done in this paper, this project shows
that the \MFMs (or, rather, the \MFMs simulator) is able to produce
visually stunning results. In the future it would be interesting to
create other visual projects on this architecture.



\section{See Also}
The source code for this project is provided as an open-source fork of
the \textsc{Movable Feast Machine v2} codebase, available at:\\
\textit{http://github.com/sixstring982/MFMv2-city}





\section{Acknowledgements}

I would like to thank \textsc{UNM} Professor Dave Ackley for allowing
me to aide in the research of the Movable Feast Machine over the past
year and for proofreading this paper. I would also like to thank
Google for funding this research.

\footnotesize
\bibliographystyle{apalike}
\bibliography{example}

\end{document}

%% \section{Self-Organization in Evolution}

%% The idea that the evolutionary process occurs in spurts, jumps, and
%% bursts rather than gradual, slow and continuous changes has been
%% around for over 75 years \citep{WIL}, but has gained prominence as
%% ``punctuated equilibrium'' through the work of \citet{GE77,GE93}. The
%% general idea is that evolutionary innovations are not bestowed upon an
%% existing species as a whole, gradually, but rather by the emergence of
%% {\em one} better adapted mutant which, by its superiority, serves as
%% the seed of a new breed that sweeps through an ecological niche and
%% supplants the species previously occupying it. The global dynamics
%% thus has a microscopic origin, as shown experimentally, e.g., in
%% populations of {\it E. Coli} \citep{ECL96}.

%% Such avalanches can be viewed in two apparently contradictory ways. On
%% the one hand we may consider the wave of extinction touching all
%% species that are connected by their ecological relations, a process
%% akin to percolation and therefore suitably described by the language
%% of second-order critical phenomena \citep{BS}. Such a scenario relies
%% on the {\em coevolution} of species (to build their ecological
%% relations) and successfully describes power-law distributions obtained
%% from the fossil record \citep{SB96,BP96}. There is, on the other hand,
%% a description in terms of {\em informational} avalanches that does not
%% require coevolution and leads to the same statistics, as we show
%% here. Rather than contradicting the aforementioned picture
%% \citep{NFST}, we believe it to be complementary.

%% In the following, we set up a scenario in which {\em information} is
%% viewed as the agent of self-organization in evolving and adapting
%% populations. Information is, in the strict sense of Shannon theory, a
%% measure of correlation between two ensembles: here a population of
%% genomes and the environment it is adapting to. As described elsewhere
%% \citep{IAL}, this correlation grows as the population stores more and
%% more information about the environment via random measurements,
%% implementing a very effective {\em natural Maxwell demon}. Any time a
%% stochastic event increases the information stored in the population, a
%% wave of extinction removes the less adapted genomes and establishes a
%% new era. Yet, information cannot leave the population as a whole,
%% which therefore may be thought of as protected by a {\em
%% semi-permeable membrane} for information, the hallmark of the Maxwell
%% demon. Let us consider this dynamics in more detail.

%% The simple living systems we consider here are populations of
%% self-replicating strings of instructions, coded in an alphabet of
%% dimension ${\cal D}$ with variable string length $\ell$. The total
%% number of possible strings is exponentially large. Here, we consider
%% the subset of all strings currently in existence in a finite
%% population of size $N$, harboring $N_g$ different types, where
%% $N_g\ll{\cal D}^\ell$. Each {\em genotype} (particular sequence of
%% instructions) is characterized by its replication rate $\epsilon_i$,
%% which depends on the sequence only, while its survival rate is given
%% by $\epsilon_i/\langle \epsilon\rangle$, in a ``stirred-reactor''
%% environment that allows a mean-field picture. This average replication
%% rate $\langle \epsilon\rangle$ characterizes the fitness of the
%% population as a whole, and is given by
%% \begin{eqnarray}
%% \langle \epsilon\rangle=\sum_i^{N_g}\frac{n_i}N \epsilon_i\;,
%% \end{eqnarray}
%% where $n_i$ is the {\em occupation number}, or frequency, of genotype
%% $i$ in the population. As $N_g$ is not fixed in time, the average
%% depends on time also, and is to be taken over all genotypes currently
%% living. The total abundance, or size, of a genotype is then
%% \begin{eqnarray}
%% s_i=\int_0^\infty n_i(t)\, dt=\int_{T_c}^{T_e}n_i(t)\, dt\;,
%% \label{size}
%% \end{eqnarray}
%% where $T_c$ is the time of creation of this particular genotype, and
%% $T_e$ the moment of extinction. Before we obtain this distribution in
%% Avida, let us delve further into the statistical description of the
%% extinction events.

%% At any point in time, the fate of every string in the population is
%% determined by the craftiness of the best adapted member of the
%% population, described by $\epsilon_{\rm best}$. In this simple,
%% finite, world, which does not permit strings to affect other members
%% of the population except by replacing them, not being the best reduces
%% a string to an ephemeral existence. Thus, every string is
%% characterized by a {\em relative} fitness, or {\em inferiority}
%% \begin{eqnarray}
%% E_i=\epsilon_{\rm best}-\epsilon_i
%% \end{eqnarray}
%% which plays the role of an {\em energy} variable for strings of
%% information {IAL}. Naturally, $\langle E\rangle=0$ characterizes the
%% {\em ground state}, or vacuum, of the population, and strings with
%% $E_i>0$ can be viewed as occupying {\em excited} states, soon to
%% ``decay'' to the ground state (by being replaced by a string with
%% vanishing inferiority). Through such processes, the dynamics of the
%% system tend to minimize the average inferiority of the population, and
%% the fitness landscape of replication rates thus provides a Lyapunov
%% function. Consequently, we are allowed to proceed with our statistical
%% analysis. Imagine a population in equilibrium, at minimal average
%% inferiority as allowed by the ``temperature'': the rate (or more
%% precisely, the probability) of mutation. Imagine further that a
%% mutation event produces a new genotype, fitter than the others,
%% exploiting the environment in novel ways, replicating faster than all
%% the others. It is thus endowed with a new best replication rate,
%% $\epsilon_{\rm best}^{\rm new}$, larger than the old ``best'' by an
%% amount $\Delta \epsilon$, and redefining what it means to be
%% inferior. Indeed, all inferiorities must now be {\em renormalized}:
%% what passed as a ground state ($E=0$) string before now suddenly finds
%% itself in an excited state. The seed of a new generation has been
%% sown, a phase transition must occur. In the picture just described,
%% this is a first-order phase transition with latent heat
%% $\Delta\epsilon$ (see Fig.\ref{fig1}), starting at the ``nucleation''
%% point, and leading to an expanding {\em bubble} of ``new phase''.


%% \begin{figure}[t]
%% \begin{center}
%% \includegraphics[width=2.1in,angle=-90]{fig1.eps}
%% \caption{``Energies'' (inferiorities) of strings in a first-order
%%   phase transition with latent heat $\Delta\epsilon$.}
%% \label{fig1}
%% \end{center}
%% \end{figure}

%% This bubble expands with a speed given by the Fisher velocity
%% \begin{eqnarray}
%% v\sim\sqrt{D\Delta\epsilon}\;, \label{eq4}
%% \end{eqnarray}
%% where $D$ is the diffusion coefficient (of information) in this
%% medium, until the entire population has been converted \citep{CHU}.
%% This marks the end of the phase transition, as the population returns
%% to equilibrium via mutations acting on the new species, creating new
%% diversity and restoring the {\em entropy} of the population to its
%% previous value. This prepares the stage for a new avalanche, as only
%% an equilibrated population is vulnerable to even the smallest
%% perturbation. The system has returned to a critical point, driven by
%% mutations, self-organized by information.

%% Thus we see how a first-order scenario, without coevolution, can lead
%% to self-organized and critical dynamics. It takes place within a
%% single, finite, ecological niche, and thus does not contradict the
%% dynamics taking place for populations that span many niches. Rather,
%% we must conclude that the descriptions complement each other, from the
%% single-niche level to the ecological web. Let us now take a closer
%% look at the statistics of avalanches in this model, i.e., at the
%% distribution of genotype sizes.


%% \section{Exponents and Power Laws}

%% \hyphenation{ap-proximated}

%% In this particular system avalanche size can be approximated
%% by the size $s$ of the genotype that gave rise to it,
%% Eq.~(\ref{size}).  We shall measure the distribution of these sizes
%% $P(s)$ in the Artificial Life system Avida, which implements a
%% population of self-replicating computer programs written in a simple
%% machine language-like instruction set of ${\cal D}=24$ instructions,
%% with programs of varying sequence length. In the course of
%% self-replication, these programs produce mutant off-spring because the
%% {\tt copy} instruction they use is flawed at a rate $R$ errors per
%% instruction copied, and adapt to an environment in which the
%% performance of {\em logical} computations on externally provided
%% numbers is akin to the catalysis of chemical reactions \citep{OBA}. In
%% this {\em artificial chemistry} therefore, successful computations
%% accelerate the metabolism (i.e., the CPU) of those strings that carry
%% the {\em gene} (code) necessary to perform the trick, and any program
%% discovering a new trick is the seed of another avalanche.

%% Avida is not a stirred-reactor environment (although one can be
%% simulated). Rather, the programs live on a two-dimensional grid, each
%% program occupying one site. The size of the grid is finite, and chosen
%% in these experiments to be small enough that avalanches are generally
%% over before a new one starts. As is well-known, this is the condition
%% {\em sine qua non} for the observation of SOC behavior, a separation
%% of time scales which implies that the system is driven at
%% infinitesimal rates.

%% Let $\tau$ denote the average duration of an avalanche. Then, a
%% separation of time scales occurs if the average time between the
%% production of new seeds of avalanches is much larger than $\tau$. New
%% seeds, in turn, are produced with a frequency $\langle\epsilon\rangle
%% P$, where $\langle\epsilon\rangle$ is again the average replication
%% rate, and $P$ is the mutation probability (per replication period) for
%% an average sequence of length $\ell$,
%% \begin{eqnarray}
%% P=1-(1-R)^\ell\;.
%% \end{eqnarray}
%% For small enough $R$ and not too large $\ell$ (so that the product
%% $R\ell$ is smaller than unity) we can approximate
%% $P\approx R\ell$, and infinitesimal driving occurs in the limit
%% \begin{eqnarray}
%% \langle \epsilon\rangle R\ell \ll\frac1\tau\;.\label{cond}
%% \end{eqnarray}
%% Furthermore
%% \begin{eqnarray}
%% \tau\sim\frac{L}v
%% \end{eqnarray}
%% with $L$ the diameter of the system and $v$ a typical Fisher velocity.
%% The fastest waves are those for which the latent heat is of the order
%% of the new fitness, i.e., $\Delta\epsilon\sim\epsilon$, in which case
%% $v\approx \epsilon$ \citep[because $D\sim\epsilon$ in
%% Eq.~(\ref{eq4}),][]{CHU}, and a separation of time scales is assured
%% whenever
%% \begin{eqnarray}
%% \frac1{R\ell}\gg {L}\;,
%% \end{eqnarray}
%% that is, in the limit of vanishing mutation rate or small population
%% sizes. For the $L=60$ system used here, this condition is obeyed (for
%% the fastest waves) only for the smallest mutation rate tested and
%% sequence lengths of the order of the ancestor.


%% \begin{figure}[t]
%% \includegraphics[width=2.3in, angle=90]{fig2.eps}
%% \caption{Fitness of the dominant genotype in the population, $\epsilon_{\rm best}$ as a function of time (in updates).}
%% \label{fig2}
%% \end{figure}


%% In the following, we keep the population size constant (a $60\times60$
%% grid) and vary the mutation rate. From the previous arguments, we
%% expect true scale-free dynamics only to appear in the limit of small
%% mutation rates.  As in this limit avalanches occur less and less
%% frequently, this is also the limit where data are increasingly
%% difficult to obtain, and other finite size effects can come into play.
%% We shall try to isolate the scale-free regime by fitting the
%% distribution to a power law
%% \begin{eqnarray}
%% P(s)\sim s^{-D(R)}\label{power}
%% \end{eqnarray}
%% and monitor the behavior of $D$ from low to high mutation rates.

%% In Fig.~\ref{fig2}, we display a typical history of $\epsilon_{\rm
%% best}$, i.e., the fitness of the dominant genotype.\footnote{As the
%% replication rate $\epsilon$ is exponential in the bonus obtained for a
%% successful computation, $\epsilon_{\rm best}$ increases exponentially
%% with time.}  Note the ``staircase'' structure of the curve reflecting
%% the ``punctuated'' dynamics, where each step reflects a new avalanche
%% and concurrently an extinction event. Staircases very much like these
%% are also observed in adapting populations of {\it E. Coli}
%% \citep{LT94}.

%% As touched upon earlier, the Avida world represents an environment
%% replete with information, which we encode by providing bonuses for
%% performing logical computations on externally provided (random)
%% numbers. The computations rewarded usually involve two inputs $A$ and
%% $B$, are finite in number and listed in Table~1. At the end of a
%% typical run (such as Fig.~\ref{fig2}) the population of programs is
%% usually proficient in almost all tasks for which bonuses are given
%% out, and the genome length has grown to several multiples of the
%% initial size to accommodate the acquired information.

%% \begin{table}[h]
%% \center{
%% \begin{tabular}{|c|c|c|c|}\hline
%% Name & Result & Bonus $b_i$ & Difficulty\\ \hline\hline
%% Echo & I/O   & 1 & --\\
%% Not  & $\neg A$ & 2 & 1 \\
%% Nand & $\neg(A\wedge B)$ & 2 & 1 \\
%% Not Or & $\neg A \vee B$ & 3 & 2 \\
%% And  &  $ A \wedge B $   & 3 & 2 \\
%% Or   &  $ A \vee B $     & 4 & 3 \\
%% And Not & $A\wedge\neg B$& 4 & 3 \\
%% Nor  & $\neg(A\vee B)$   & 5 & 4 \\
%% Xor  & $ A\ {\rm xor}\ B$ &   6 & 4 \\
%% Equals &$\neg(A\ {\rm xor}\ B)$&6& 4 \\ \hline
%% \end{tabular}
%% }
%% \vskip 0.25cm
%% \caption{Logical calculations on random inputs $A$ and $B$ rewarded,
%% bonuses, and difficulty (in minimum number of {\tt nand} instructions
%% required). Bonuses $b_i$ increase the speed of a CPU by a factor
%% $\nu_i=1+2^{b_i-3}$.}
%% \end{table}

%% Because the amount of information stored in the landscape is finite,
%% adaptation, and the associated avalanches, must stop when the
%% population has exhausted the landscape.  However, we shall see that
%% even a `flat' landscape (on which evolution is essentially neutral
%% after the sequence has optimized its replicative strategy) gives rise
%% to a power law of genotype sizes, as long as the programs do not
%% harbor an excessive amount of ``junk'' instructions.  A typical
%% abundance distribution (for the run depicted in Fig.~\ref{fig2}) is
%% shown in Fig.~\ref{fig3}.


%% \begin{figure}[ht]
%% \begin{center}
%% \includegraphics[width=2.25in, angle=90]{fig3.eps}
%% \caption{Distribution of genotypes sizes $P(s)$ fitted to a power law
%%   (solid line) at mutation rate $R=0.004$.}
%% \label{fig3}
%% \end{center}
%% \end{figure}


%% As mentioned earlier, we can also turn {\em off} all bonuses listed in
%% Tab.~1, in which case fitness is related to replicative abilities
%% only. Still, avalanches occur (within the first 50,000 updates
%% monitored) due to minute improvements in fitness, but the length of
%% the genomes typically stays in the range of the ancestor, a program of
%% length 31 instructions. We expect a change of dynamics once the
%% ``true'' maximum of the local fitness landscape is reached, however,
%% we did not reach this regime in the experiments presented here. The
%% distribution of genotype sizes for the flat landscape is depicted in
%% Fig.~\ref{fig4}.


%% \begin{figure}[!tbp]
%% \begin{center}
%% \includegraphics[width=2.25in, angle=90]{fig4.eps}
%% \caption{Distribution of genotypes sizes $P(s)$ for a landscape devoid
%%   of the bonuses listed in Tab.~1, at mutation rate $R=0.003$.} \label{fig4}
%% \end{center}
%% \end{figure}


%% Clearly then, even such landscapes (flat with respect to all other
%% activities except replication) are not neutral. Indeed, it is known
%% that neutral evolution, where the chance for a genotype to increase or
%% decrease in number is even, leads to a power law in the abundance
%% distribution with exponent $D=1.5$ \citep{ABH}.


%% \begin{figure}[t]
%% \begin{center}
%% \includegraphics[width=2.2in, angle=90]{fig5.eps}
%% \vskip 0.25cm
%% \caption{Fitted exponent of power law for 34 runs at mutation rates
%%   between $R=0.0005$ and $R=0.01$ copy errors per instruction
%%   copied. The error bars reflect the standard deviation across the
%%   sample of runs taken at each mutation rate. The solid line is to
%%   guide the eye only.
%% }
%% \label{fig5}
%% \end{center}
%% \end{figure}


%% In order to test the dependence of the fitted exponent $D(R)$
%% [Eq.~(\ref{power})] on the mutation rate, we conduct a set of
%% experiments at varying copy-mutation rates from $0.5\times10^{-3}$ to
%% $10\times10^{-3}$ and take data for 50,000 updates. Again, a ``best''
%% genotype is not reached after this time, and we must assume that
%% avalanches were still occurring at the end of these runs. Furthermore,
%% in some runs we find that a genotype comes to dominate the population
%% (usually after most `genes' have been discovered) which carries an
%% unusual amount of junk instructions. As mentioned earlier, such
%% species produce a distribution that is exponentially suppressed at
%% large genotype sizes (data not shown). To avoid contamination from
%% such species, we stop recording genotypes after a plateau of fitness
%% was reached, i.e., if the population had discovered most of the
%% bonuses. Furthermore, in order to minimize finite size effects on the
%% determination of the critical exponent, we excluded from this fit all
%% genotype abundances larger than 15, i.e., we only fitted the smallest
%% abundances. Indeed, at larger mutation rates the higher abundances are
%% contaminated by a pile-up effect due to the toroidal geometry, while
%% at lower mutation rates a scale appears to enter which prevents
%% scale-free behavior. We have not, as yet, been able to determine the
%% origin of this scale.

%% In the results reported here, we show the dependence of the fitted
%% exponent $D$ as a function of the mutation rate $R$ used in the run,
%% which, however, is a good measure of the mutation probability $P$ only
%% at small $R$ and if the sequence length is not excessive. As a
%% consequence, data points at large $R$, as well as runs where an
%% excessive sequence length developed, carry a systematic error.
