Information Technology Reference
In-Depth Information
Fig. 1. A synchronous CA having
reached a cyclic attractor.
Fig. 2. A fixed point reached by an
asynchronous CA. The initial state is
the same of the synchronous one.
2.1 Asynchronous Dynamics
Accordingly to the most accepted terminology [6,10,13], a CA is asynchronous
if cells can update their state independently from each other, rather than all
together in parallel, according to a dynamics that can be either step-driven or
time-driven .
In step-driven dynamics, a kind of global daemon is introduced, whose job
is to choose at each time step one (and only one)cell to update. In time-driven
dynamics, each cell is assumed to have an “internal clock” which wakes up the cell
and makes it update. Also, time-driven dynamics provides for a more continuous
notion of time. The updating signal for a cell can be either deterministic (e.g.,
every time steps)or probabilistic (e.g., the probability that the cell update its
state is uniformly distributed), and the next state of a cell is selected on the
basis of the current state of neighboring cells.
In the experiments presented in this paper, CA have an asynchronous time-
driven dynamics: at each time step, a cell has a probability λ a to wake up and
update its state. The update of a cell has been implemented as atomic and
mutually exclusive among neighbors, without preventing non-neighbor cells to
update their state concurrently.
In general, it has been observed that the asynchronous CA exhibits behaviors
which are very different from the ones of their synchronous counterparts, both
in terms of transient and final attractor. Both the dynamics have the same fixed
points [13], i.e., attractors that are fixed points under synchronous dynamics
are fixed points also under asynchronous dynamics and vice versa. Nevertheless,
trajectories in the state space and basins of attraction can be very different
and some of the final attractors reached under asynchronous dynamics may be
reached with lower probability under synchronous one.
 
Search WWH ::




Custom Search