Information Technology Reference
In-Depth Information
Artificially Evolved Asynchronous Cellular
Automata for the Density Task
Marco Tomassini and Mattias Venzi
Computer Science Institute, University of Lausanne,
1015 Lausanne, Switzerland.
Abstract.
In this paper we study the evolution of asynchronous au-
tomata for the density task. We compare our results with those obtained
for synchronous automata and we describe the influence of various asyn-
chronous update policies on the computational strategy. We also inves-
tigate how synchronous and asynchronous cellular automata behave un-
der noisy conditions and show that asynchronous ones are more fault-
tolerant.
1 Introduction
Cellular automata(CAs) are well-known and widely used sytems [10]. In this
work we concentrate on the customary simultaneous i.e,
synchronous
updating of
the CA cells. This update mode is conceptually simple and it is easier to deal with
in mathematical terms. However, perfect synchronicity is only an abstraction:
if CAs are to model physical or biological situations or are to be considered
physically embodied computing machines then the synchronicity assumption is
untenable. In fact, in any spatially extended system signals cannot travel faster
than light. Hence, it is impossible for a signal emitted by a global clock to reach
any two computing elements at exactly the same time. In this study we relax
the synchronicity constraint and work with various kinds of
asynchronous
CA
updating modes on a well-known problem: density classification by a CA. The
few existing studies on asynchronous CAs have shown that asynchronous update
often gives rise to completely different time evolutions for the CA. For instance,
cyclic attractors are no longer possible and generally there is a loss of the rich
structures commonly found in synchronous CAs (see e.g. [1,4]).
In systems withmany components faulty behavior is a common occurrence.
In the second part of the paper we compare the dynamics of synchronous and
asynchronous CAs for the density task in the presence of random errors in order
to ascertain their respective robustness.
The paper is organized as follows. The following section 2 summarizes def-
initions and facts about standard CAs and their asynchronous counterparts.
Section 3 deals with the artificial evolution of asynchronous CAs for the density
task and compares their behavior and solution strategies with those of known
synchronous CAs. In section 4 we study their fault-tolerance aspects. Section 5
presents our conclusions and hints to further work.
