Encyclopedia of Complexity and Systems Science

Living Edition
| Editors: Robert A. Meyers

Asynchronous Cellular Automata

  • Nazim FatèsEmail author
Living reference work entry

Latest version View entry history

DOI: https://doi.org/10.1007/978-3-642-27737-5_671-2

Keywords

Asynchronous Cellular Automata Synchrony Rate Dennunzio Asynchronous Update Shift Rule 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Glossary

Configurations

These objects represent the global state of the cellular automaton under study. The set of configurations is denoted by Q , where Q is the set of states of the cells and ℒ is the space of cells. In this text, we mainly consider finite configurations with periodic boundary conditions. In one dimension, we use ℒ = ℤ/nℤ, the class of equivalence of integers modulo n.

Convergence

When started from a given initial condition, the system evolves until it attains a set of configurations from which it will not escape. It is a difficult problem to know in general what are the properties of these attractive sets and how long it takes for the system to attain them. In this text, we are particularly interested in the case where these sets are limited to a single configuration, that is, when the system converges to a fixed point. Fixed points play a special role in the theory of asynchronous cellular automata because synchronous and (classical) asynchronous models have the same set of fixed points. In some cases, reaching a fixed point can be interpreted as the end of a randomized computation.

De Bruijn graph (or diagram)

This is an oriented graph which allows one to represent all the overlaps of length n − 1 in words of length n. This graph is used to find some elementary properties of the convergence of asynchronous CA, in particular to determine the set of fixed points of a rule.

Elementary cellular automata

There are 256 one-dimensional binary rules defined with nearest-neighbor interactions; an update sets a cell state to a value that depends only on its three inputs – its own state and the states of its left and right neighbors. Using the symmetries that exchange 0 s and 1 s and left and right, these rules reduce to 88 equivalence classes.

Game of Life

This cellular automaton was invented by Conway in 1970. It is probably the most famous rule, and it has been shown that it can simulate a universal Turing machine. The behavior of this rule shows interesting phenomena when it is updated asynchronously.

Markov chain

A stochastic process that does not keep memory of the past; the next state of the system depends only on the current state of the system.

Reversibility

When the system always return to its initial condition, we say that it is reversible or, more properly speaking, that it is recurrent. Various interpretations of the notion of reversibility can be given in the context of probabilistic cellular automata.

Updating scheme

The function that decides which cells are updated at each time step. In this text, we focus on probabilistic updating schemes. Our cellular automata are thus particular cases of probabilistic cellular automata or interacting particle systems.

Article Outline

This text is intended as an introduction to the topic of asynchronous cellular automata and is presented as a path. We start from the simple example of the Game of Life and examine what happens to this model when it is made asynchronous (section “Introduction”). We then formulate our definitions and objectives to give a mathematical description of our topic (section “Defining Asynchrony in the Cellular Models”). Our journey starts with the examination of the shift rule with fully asynchronous updating, and from this simple example, we will progressively explore more and more rules and gain insights on the behavior of the simplest rules (section “Convergence Properties of Simple Binary Rules”). As we will meet some obstacles in having a full analytical description of the asynchronous behavior of these rules, we will turn our attention to the descriptions offered by statistical physics and more specifically to the phase transition phenomena that occur in a wide range of rules (section “Phase Transitions Induced by α-Asynchronous Updating”). To finish this journey, we will discuss the various problems linked to the question of asynchrony (section “Other Questions Related to the Dynamics”) and present some openings for the readers who wish to go further (section “Openings”).

Definition of the Subject

This article is mainly concerned with asynchronous cellular automata viewed as discrete dynamical systems. The question is to know, given a local rule, how the cellular automaton evolves if this local rule is applied to only a fraction of the cells. We are mainly interested in stochastic systems, that is, we consider that the updating schemes, the functions which select the cells to be updated, are defined with random variables. Even if there exists a wide range of results obtained with numerical simulations, we focus our discussion on the analytical approaches as we believe that the analytical results, although limited to a small class of rules, can serve as a basis for constructing a more general theory. Naturally, this is a partial view on the topic, and there are other approaches to asynchronous cellular automata. In particular, such systems can be viewed as parallel models of computation (see Th. Worsch’s article in this encyclopedia) or as models of real-life systems. Readers who wish to extend their knowledge may refer to our survey paper for a wider scope on this topic (Fatès 2014a).

Introduction

Cellular automata were invented by von Neumann and Ulam in the 1950s to study the problem of making artificial self-reproducing machines (Moore 1962). In order to imitate the behavior of living organisms, the design of such machines involved the use of a grid where the nodes, called the cells, would evolve according to a simple recursive rule. The model employs a unique rule, which is applied to all the cells simultaneously: this rule represents the “physics” of this abstract universe. The rule is said to be local in the sense that each cell can only see some subset of cells located at short distance: these cells form its neighborhood. In von Neumann’s original construction, all the cells are updated at each time step, and this basis has been adopted in the great majority of the cellular automata constructions. This hypothesis of a perfect parallelism is quite practical as it facilitates the mathematical definition of the cellular automaton and its description with simple rules or tables. However, it is a matter of debate to know if such a hypothesis can be “realistic.” The intervention of an external agent that updates all the components simultaneously somehow contradicts the locality of the model. One may legitimately raise what we could call the no-chief-conductor objection: “in Nature, there is no global clock to synchronise the transitions of the elements that compose a system, why should there be one in our models?”

However, this objection alone cannot discard the validity of the classical synchronous models. Instead, one may simply affirm that the no-chief-conductor objection raises the question of the robustness of cellular automata models. Indeed, at some point, the hypothesis of perfectly synchronous transitions may seem unrealistic, but we cannot know a priori if its use introduces spurious effects. There are some cases where a given behavior of a cellular automaton will only be seen for the synchronous case, and there are also cases where this behavior remains constant when the updating scheme is changed. In essence, without any information on the system, we have no means to tell what are the consequences of choosing one updating scheme or the other.

If we have a robust model, changes in the updating may only perturb slightly the global behavior of a system. On the contrary, if this modification induces a qualitative change on the dynamics, the model will be called structurally unstable or simply sensitive to the perturbations of its updating Scheme. A central question about cellular automata is thus to know how to assess their degree of robustness to the perturbations of their updating. Naturally, the same questions can be raised about the other hypotheses of the model: the homogeneity of the local rule, the regular topology, the discreteness of states, etc. (see, e.g., Problem 11 in Wolfram (1985)).

A First Experiment

In order to make things more concrete, we propose to start our examination with a simple asynchronous CA. We will employ the α-asynchronous updating scheme (Fatès and Morvan 2005) and apply the following rule: at each time step, each cell is updated with a probability α and is left in the same state with probability 1 – α. The parameter α is called the synchrony rate (see the formal definitions below) (Note that from the point of view of a given cell, all happens as if between two updates each cell was waiting a random time that follows a geometric law of parameter α.). The advantage of this definition is to control the robustness of the model by varying the synchrony rate continuously from the classical synchronous case α = 1 to a small value of α, where most updates will occur sequentially. We thus propose to examine the behavior of the α-asynchronous Game of Life. Figure 1 shows three different evolutions of the rule: the synchronous case (α = 1), an evolution with a little asynchrony (α = 0.98), and an evolution with a stronger asynchrony (α = 0.5).
Fig. 1

Configurations obtained with the α-asynchronous Game of Life for three values of the synchrony rate α and the same initial conditions. (Top) Synchronous updating, the system is stable at t = 50; (middle) small asynchrony introduced, the system is still evolving at t = 100; (bottom) α = 1/2, the qualitative behavior of the system has changed

The first observation is that the introduction of a small degree of asynchrony does not modify the qualitative behavior of the rule on the short term. However, one can predict that the long-term behavior of the rule will be perturbed because it is no longer possible to observe cycles. For example, the configuration with only three living cells in a row oscillates in the classical Game of life, but these oscillations only exist with a synchronous updating, and the configuration evolves to a totally different pattern when this perfect simultaneity is broken. Another important property to remark is that the new (asynchronous) system has the same fixed points as the original (synchronous) system. In fact, this is a quite general property that does not depend on the local rule. The reason is simple: if a configuration is a fixed point of the synchronous system, it means that all its cells are stable under the application of the local rule. Hence, if we select a subset of cells for an update, this subset will also be stable. Reciprocally, if any choice of cells gives a stable situation, then the whole system is also stable.

The second important observation regards the evolution with α = 0.5: the global behavior of the system is completely overwhelmed! A new stationary behavior appears, and a pattern which resembles a labyrinth forms. This pattern is stable in some parts and unstable in some other parts of the grid. We will not enter here into the details on how this stability can be quantified, but it is sufficient to observe that, in most cases, this pattern remains for a very long time.

Questions

It may be argued that these observations are not that surprising, because if one modifies the basic definitions of a dynamical system, one naturally expects to see effects on its behavior. However, this statement is only partially true, as this type of radical modifications is not observed for all the rules. In fact, as Nakamura has shown, we can always modify a rule in order to make it insensitive to the variations of its updating scheme (Nakamura 1974, 1981). Formally, this amounts to show that any classical deterministic cellular automaton may be simulated by an asynchronous one. By “simulated” we mean that the knowledge of the evolution of the stochastic asynchronous system allows one to know the evolution of the deterministic original rule with a simple transformation (see Th. Worsch’s article). The idea of Nakamura is that each cell should keep three registers: one with its current state, one with its previous state, and one with a counter that tells if its local time is late, in advance or synchronized with the local time of its neighbors. There is of course an overhead in terms of simulation time and number of states which are used, and one may want to reduce this overhead as much as possible (Lee et al. 2004), but the point is that there are asynchronous rules which will evolve as their synchronous deterministic counterparts. As an extreme example, we can also think of the rule where each cell turns to a given state independently of its neighbor: the global evolution is easily predicted.

Partial robustness can also be observed with some simple rules. For example, let us consider the majority rule: cells take the state that is the most present in their neighborhood. Observing this rule on a two-dimensional grid with periodic boundary conditions shows that it is robust to the variations of α: roughly speaking, if we start from a uniform random initial condition, for 0.5 < α < 1, the system seems to always stabilize quickly on a fixed point. For smaller values of α, the only noticeable effect is a slowdown of the converge time. However, a modification also exists at the vicinity of α = 1: like for the Game of Life, as soon as a little asynchrony is present, cycles disappear.

These experiments indicate that there is something about asynchronous systems that deserves to be investigated. Since the first numerical simulations (Buvel and Ingerson 1984), a great number of approaches have been adopted to gain insights on asynchronous cellular automata. However, if we want to be convinced that these systems can be studied and understood theoretically, and despite their randomness, we need some analytical tools. The purpose of the lines that follow is to give a few indications on how the question of asynchrony in cellular automata can be dealt with theoretical tools from computer science and probability theory.

Defining Asynchrony in the Cellular Models

Literally, asynchronous is a word derived from the Ancient Greek ἀσυνχρονος, which simply means “not same time”. From this etymology, it follows that we cannot speak of a single model of asynchrony in cellular automata, but there is an infinity of models. In fact, one is allowed to speak of an asynchronous model as soon as there is some perturbation in the updating process of the cells (Note that asynchrony and asynchronism have been both used in the literature in an equivalent way. We will in general use the former for the modification of the updating and use the latter to designate a topic of research.).We voluntarily stay vague at this point in order to stress that one may imagine a great variety of situations where some irregularity occurs on the way the information is processed by the cells. For instance, we may examine what happens if all the transitions do occur at each time step but where the cells receive the state of their neighbors imperfectly.

In this text, we will restrict our scope to the most simple cases of asynchronous updating.

Mathematical Framework

Let ℒ ∈ ℤ d be the set of cells that compose a d-dimensional cellular automaton. The set of states that each cell may hold is Q. The collection of all states at a given time is called a configuration, and the configuration space is thus Q .

Let \( \mathcal{N}\in {\left({\mathrm{\mathbb{Z}}}^d\right)}^k \) be the neighborhood of the cellular automaton, that is, for \( \mathcal{N}=\left({n}_1,\dots, {n}_k\right) \), n i represents the vector between the central cell and its ith neighbor.

The local function of a cellular automaton is a function f: Q k Q which assigns to a cell c ∈ ℒ its new state q′ = f (q 1,…, q k ), where the tuple (q 1,…, q k ) represents the state of the neighbors of a cell c.

Starting from an initial configuration xQ , the classical evolution of the system gives a sequence of configurations that we denote by (x t ) t ∈ ℕ. This sequence is obtained by the recursive application of the global rule F : Q Q defined with x 0 = x and x t + 1 = F (x t ) such that:
$$ \forall c\in \mathrm{\mathbb{Z}},{x}_c^{t+1}=f\left({x}_{c+{n}_1}^t,\dots, {x}_{c+{n}_k}^t\right). $$

Now, to define an asynchronous cellular automaton , we need to introduce an updating scheme. Such a function takes the form \( \mathcal{U}:\mathrm{\mathcal{L}}\to \wp \left(\mathrm{\mathcal{L}}\right) \), where \( \wp (S) \) denotes the parts of S, that is, the set of all subsets of S (also denoted by 2 S ). For a given time step t ∈ ℕ, the set of cells that are updated at time t is represented by \( \mathcal{U}(t) \).

We obtain a new global rule, denoted by \( {F}_{\mathcal{U}}:\mathrm{\mathbb{N}}\times {Q}^{\mathrm{\mathcal{L}}}\to {Q}^{\mathrm{\mathcal{L}}} \) where \( {F}_{\mathcal{U}}\left(x,t\right) \) represents the image of x at time t given the updating scheme \( \mathcal{U}. \)The evolution of (x t ) t ∈ ℕ starting from xQ is now defined with x 0 = x and \( {x}^{t+1}={F}_{\mathcal{U}}\left({x}^t\right) \) such that:
$$ \forall c\in \mathrm{\mathbb{Z}},{x}_c^{t+1}=\left\{\begin{array}{ll}f\left({x}_{c+{n}_1}^t,\dots, {x}_{c+{n}_k}^t\right)& if\;c\in \mathcal{U}(t),\\ {}{x}_c^t& \mathrm{otherwise}.\end{array}\right. $$

The type of function \( \mathcal{U} \) defines the type of asynchronism in use. The first issue of distinction is between deterministic and stochastic (or probabilistic) functions. In this text, we will focus on stochastic functions. Indeed, since asynchronism is often thought of as an unpredictable aspect of the system, stochastic systems have been more intensively studied. One finds only a small number of studies which use deterministic systems. Examples of such studies can be found in Cornforth et al. (2005), Schönfisch and de Roos (1999) where the authors have considered, for example, the effects caused by updating cells sequentially from left to right. As one may expect, such approaches often lead to curious phenomena: the information spreads in a nonnatural way because a single sequence of updates from left to right suffices to change the state of the whole system. More interesting are even-odd updating schemes where one updates the even cells and, in the next step, the odd cells. A famous example of such model is the Q2R model (Vichniac 1984): although the local rule of this system is deterministic, using a random initial condition makes it evolve with the same density as the Ising model (see, e.g., Kari and Taati (2015) for a recent development).

In fact, we can remark that in general it is not difficult to transform an asynchronous system into a synchronous one: in many cases, adding more states is sufficient. For example, for the even-odd updating, we may mark the even and odd cells with a flag up and down, respectively, and make this flag “flip” at each time step. Similarly, an ordered updating may be simulated in a synchronous model by moving a token in a given order. However, such direct transformations are not always possible: for example, Vielhaber has proposed an original way of achieving computation universality by selecting the cells to update (Vielhaber 2013), and this construction cannot be transformed into a deterministic cellular automaton by the mere addition of a few internal states.

Randomness in the Updating

In the case where the updating scheme \( \mathcal{U} \) is a random variable, then the evolution of the system is a stochastic process , and if \( \mathcal{U} \) does not depend on time, it is a Markov chain (a memoryless system). In order to be perfectly rigorous in the formal description of the system, advanced tools from probability theory are necessary. A good example on how to properly use these mathematical objects and their properties can be found in a survey by Mairesse and Marcovici (2014). However, for the sake of simplicity, one may still use the usual notations and consider that the sequences (x t ) t ∈ ℕ are formed by configurations rather than probability distributions.

We can now define the two major asynchronous updating schemes:
  • α-asynchronous updating scheme: let α ∈ (0, 1] be constant called the synchrony rate. Let \( {\left({\mathrm{\mathcal{B}}}_i^t\right)}_{i\in \mathrm{\mathcal{L}},t\in \mathrm{\mathbb{N}}} \) be a sequence of independent and identically distributed Bernoulli random variables of parameter α. The evolution of the system with an α-asynchronous updating scheme is then given by:
    $$ {x}^0=x\, \mathrm{and}\, \forall i\in \mathrm{\mathbb{Z}},{x}_i^{t+1}=\left\{\begin{array}{ll}f\left({x}_{i+{n}_1}^t,\dots, {x}_{i+{n}_k}^t\right)& \mathrm{if}\;{\mathrm{\mathcal{B}}}_i^t=1,\\ {}{x}_c^t& \mathrm{otherwise}.\end{array}\right. $$
  • Fully asynchronous updating scheme: in the case where ℒ is finite, let (S t ) t ∈ ℕ be a sequence of independent and identically distributed random variables that select an element uniformly in ℒ. The evolution of the system is given by:
    $$ {x}^0=x\, \mathrm{and}\, \forall i\in \mathrm{\mathbb{Z}},{x}_i^{t+1}=\left\{\begin{array}{ll}f\left({x}_{i+{n}_1}^t,\dots, {x}_{i+{n}_k}^t\right)& \mathrm{if}\;i={S}_t,\\ {}{x}_c^t& \mathrm{otherwise}.\end{array}\right. $$

Note that in most cases, authors do not use the indices i and t for \( \left({\mathrm{\mathcal{B}}}_i^t\right) \) or (S t ) and simply consider that there is one function that is used at each time step and for each cell.

We do not enter here into the details of how we can generalize these definitions (see, e.g., Dennunzio et al. (2013)). We point the work of Bouré et al. on asynchronous lattice-gas cellular automata to underline that adding asynchrony to the cellular models which have more structure than the classical ones can be a nontrivial operation if one wants to maintain the properties of these models (e.g., conservation of the number of particles) (Bouré et al. 2013a). Similar difficulties arise when agents can move on the cellular grid, and one needs to define some procedures to solve the conflicts that may occur when several agents want to modify simultaneously the same cell (Belgacem and Fatès 2012; Chevrier and Fatès 2010).

Convergence Properties of Simple Binary Rules

We have seen that a central question in the study of asynchronous cellular automata was to determine their convergence properties. In particular one may wonder, given a simple binary rule, what we can predict about its possible behavior. Is it converging to a given fixed point? In which time in average? And if so, what kind of “trajectory” the system will follow to attain a stable state (if any)? The lines that follow aim at presenting the mathematical tools to answer these questions.

Expected Convergence Time to a Fixed Point

Recall that one major modification caused by the transformation of a cellular automaton from synchronous to asynchronous updating is the removal of cycles: cycles are replaced by some attractive sets of configurations (see below for a more precise description). Let us examine this property on a simple case. We work on a finite one-dimensional system and denote the set of cells by ℒ = ℤ/nℤ, where n is the number of cells. We employ a fully asynchronous updating scheme described by a sequence of independent and identically distributed random variables (S t ) which are uniform on ℒ (one cell is selected at each time step). The local rule depends only on the state of the cell itself and its left and right neighbors; we have \( \mathcal{N} \) = {1, 0, 1}. Recall that for an initial condition xQ , the evolution of the system is thus described by (x t ) t ∈ ℕ such that x 0 = x and x t + 1 = F (x t ) such that \( \forall i\in \mathrm{\mathcal{L}},{x}_i^{t+1}=f\left({x}_{i-1}^t,{x}_i^t,{x}_{i+1}^t\right) \) if i = S t and \( {x}_i^{t+1}={x}_i^t \) otherwise.

To evaluate the converge time of given rule, we proceed as in the theory of computation and define the “time complexity” of this rule as the function which estimates the amount of time taken by the “most expensive” computation of size n (see Th. Worsch’s article in this encyclopedia). Let ℱ denote the set of fixed points of a rule, and let T (x) denote the random variable which represents the time needed to attain a fixed point: T (x) = {min t: x t ∈ ℱ}. In order to have a fair comparison with the synchronous update, we consider that one time step corresponds to n updates, and we introduce the rescaled time τ (x) = T (x)/n. The “complexity measure” of a rule is then given by the worst expected convergence time (WECT): \( W\; ECT(n)=\max \left\{\mathbb{E}\left\{\tau (x)\right\};x\in {Q}^{\mathrm{\mathcal{L}}}\right\} \).

Two Notations for ECAs

Following a convention introduced by Wolfram, it is common to identify each ECA f with a decimal code W (f) which consists in converting the sequence of bits formed by the values of f to a decimal number: W (f) = f(0, 0, 0).20 + f(0, 0, 1).21 + ⋯ + f(1, 1, 1).27. We now introduce another notation of ECA rules, which consists in identifying an ECA rule f with a word which consists in a collection of labels from {A, B,…, H} where each label identifies an active transition, that is, a couple ((x, y, z), f(x, y, z)) such that f(x, y, z) ≠ y. The mapping between labels and transition is given in Table 1.
Table 1

Notation by transitions. Left, table of transitions and their associated labels. Right, symmetries of the ECA space (see text for explanations)

A

B

C

D

000

001

100

101

010

011

110

111

E

F

G

H

For example, let us consider the XOR rule f(x, y, z) = xyz, where ⊕ denotes the usual XOR operator. The decimal code associated to this rule is 150. The active transitions of this rule are 001 → 1 (B), 100 → 1 (C), 011 → 0 (F), and 110 → 0 (G). The four other transitions are passive, that is, they do not change the state of the central cell. We thus obtain the new code: BCFG.

Given the transition code of a rule, one can easily deduce the symmetric rules: to obtain the rule where the left and right directions are permuted, it is sufficient to exchange the letters B and C and to obtain the symmetric rule where the states 0 and 1 are permuted, on exchanges the letters A and E, B and F, C and G and H (see Table 2, right).
Table 2

Left, summary of the effect of each transition on a fully asynchronous ECA. Right, summary of the combinations of two (active or inactive) transitions

A

Stability of 0-regions

 

B

B 01-frontiers move left

No A+ no H doubly quiescent rule

C

10-frontiers move right

D

Absorption of 0-regions

B+ F random walk of the 01-frontiers

E

Absorption of 1-regions

F

01-frontiers move right

C + G random walk of the 10-frontiers

G

10-frontiers move left

H

Stability of 1-regions

 
In the case of a fully asynchronous updating, the notation by transitions also allows us to decompose the behavior of the local rule as follows:
  • If a rule does not have A (resp. H) in its code, the size of a 0-region (resp. a 1-region) may increase or decrease by 1, but this region cannot be broken.

  • Transitions B and F control the movements of the 01-frontiers: B (resp. F) moves this frontier to the left (resp. to the right). If both transitions are present, the 01-frontier performs a non-biased random walk.

  • Similarly, transitions C and G control the movements of the 10-frontiers.

  • Transition D (resp. E) controls the fusion of 1-regions (resp. 0-regions): the absence of D (resp. E) implies that the 0-regions (resp. 1-regions) cannot disappear.

These properties are summed up on Table 2, left.

In addition, the code by transitions can be used to produce a complementary useful view on configurations by transforming a configuration xQ in a configuration \( \tilde{x}\in {\left\{\mathrm{a},\dots, \mathrm{h}\right\}}^{\mathrm{\mathcal{L}}} \), where each cell is labeled with a, b, … if the transition A, B, … applies on it. An example of such transformation is shown in Fig. 2, left. This transformation can be done directly, but it is also interesting to consider the de Bruijn graph (or diagram), which allows one to do this transformation by reading one symbol at a time, from left to right, and by following the edge with the label that was read (see Fig. 2, right). This graph is useful for determining various properties of cellular automata. For example, the fixed points of rule are made by the cycles which do not contain a node with an active transition. For any configuration x, if we write by a, b, … the respective number of a’s, b’s, … of \( \tilde{x} \), then the following relations can be easily obtained: b = c; f = g; |x| 01 = b + d = e + f; |x|10 = c + d = e + g; |x| 01 = |x| 10.
Fig. 2

(left): Example of two binary configurations and their images by the transition code. The upper configuration is obtained by updating the lower configuration on the cell indicated with an arrow. (Right) De Bruijn graph with the correspondence between binary sequences of length 3 and transitions A, , H. The label on the edges shows the next letter that is given in input when reading a binary sequence from left to right

A Starting Example

Let us take the shift rule f(x, y, z) = z as a first example of ECA. The Wolfram code and the transition code of this rule are 150:BCFG. As it can be seen from the space-time diagrams shown in Fig. 3, although the local rule is elementary, the evolution of the system is quite puzzling at first sight. The diagrams show that, starting from the same initial condition, the system may reach either the fixed point 0 = 0 or the fixed point 1 = 1 and that the convergence time is subject to a high variability. A little close-up on the behavior of the rule allows us to discover that the number of regions of 0 s or 1 s can only decrease. Indeed, it is impossible to create a new state inside a region of homogeneous state. More precisely, a change of state can only occur on the boundaries between regions: if such a boundary is updated, it moves one cell to the left.
Fig. 3

Space-time diagrams showing the evolution of the shift rule for a ring of n cells, with n = 20. Cells in blue and white, respectively, represent states 0 and 1. Time goes from bottom to top. Each row shows the state of the system after n random updates. This convention is kept in the following

Let us examine what happens for an initial condition xQ with only two regions: we have |x| 01 = 1, where |x| 01 is the function which counts the number of occurrences of the pattern 01 in x. To calculate the probability to reach a given fixed point, we introduce the stochastic process (X t ) which counts the number of 1’s in a configuration: X t = |x t | 1, where |x| 1 is the function which counts the number of occurrences of 1’s. It can easily be verified that (X t ) is a Markov chain whose graph is shown in Fig. 4. Note that this is not immediate and this property is not true for any initial condition. The values X t = 0 and X t = n are the absorbing states of the Markov chain and represent the convergence of the asynchronous cellular automaton to its respective fixed points 0 and 1. We can thus calculate the probability p 1(k) to reach the fixed point 1 given an initial condition x such that |x| 1 = k. This can be done by recurrence by noting that p(0) = 0, p(n) = 1, and p(k) = ϵp(k − 1) + (1 2ϵ)p(k) + ϵp(k + 1), where ϵ = 1/n is the probability to update a cell. The solution is p(i) = ϵi = i/n. In other words, the probability to reach the fixed point 1 is exactly the density of the initial configuration.
Fig. 4

Representation of the Markov chain that counts the number of 1 s. The constant ϵ = 1/n represents the probability to update a cell at a given time step

Let us now estimate the average number of time steps that it will take to reach one of the two fixed points. Recall that T(x) = min {t ∈ ℕ : x t ∈ {0, 1}}. As the Markov chain is finite and has two absorbing states, T is almost surely finite. The average of T depends only on the number of 1 s of the initial condition. With a small abuse of notation, we can denote by T i the average convergence time from an initial condition with i cells in state 1; we have the following recurrence equation: T 0 = T n = 0 and ∀i ∈ {1,, n − 1},
$$ {T}_i=\varepsilon \left({T}_{i-1}+1\right)+\left(1-2\varepsilon \right)\left({T}_i+1\right)+\varepsilon \left({T}_{i-1}+1\right) $$
(1)
$$ =1+\varepsilon {T}_{i-1}-\left(1-2\varepsilon \right){T}_i+\varepsilon {T}_{i+1} $$
(2)

The solution of this system is T i = i(n − i)/2ε. Since ε = 1/n, we can write ∀i ∈ {0,, n}, T i ≤ n 3/8; in other words, for the configurations with only two zones, the average number of updates needed to attain a fixed point is at most cubic in n.

Martingales

How can we deal with the other configurations? If we start from a configuration x with k 1-regions and k > 1, the probability to increase or decrease by 1 the number of 1 s is . The evolution of the system can no longer be described by the Markov chain in Fig. 4. Indeed, the value ϵ needs to be replaced by ϵ′ = , but, as k is not constant, this process is no longer a Markov chain. As seen in Fig. 4, the frontiers of the regions will perform random walks until a region disappears, which will make ϵ′ decrease again and so on until we reach one of the two fixed points. In order to determine the convergence time τ (x), one could estimate the average “living time” of a configuration with k-regions. However, this is a difficult problem because this living time strongly depends on the size of each region.

It is easier to note that the process (X t ) defined with X t = |x t | 1 is a martingale, that is, a stochastic process whose average value is constant over time. The theory of martingales allows us to find the probability p 1(x) to reach the fixed point 1 from x and the average time of convergence \( \mathbb{E}\left\{\tau (x)\right\} \). For the sake of brevity, we skip the details of the mathematical treatments and write down directly the results that are exposed in Fatès et al. (2006a): (a) the probability of reaching the fixed point 1 is still equal to the initial density, p 1 (x) = |x| 1/n, and (b) the rescaled average time also scales quadratically with \( n:\mathbb{E}\left\{\tau (x)\right\}\le {\left|x\right|}_1\left(n-{\left|x\right|}_1\right)/2 \).

We thus have an upper bound on the WECT which is WECT (n) ≤ n 2/8, and, considering the initial condition x = 0 n/21 n/2, we obtain the lower bound WECT (n) ≥ n 2/8. We can thus write WECT (n) = \( \mathcal{O} \)(n 2) where \( \mathcal{O} \) expresses the equivalence up to a constant. We thus say that the shift has a quadratic convergence time or, for short, that it is quadratic.

A Relationship with Computational Problems

In fact, since the convergence of the asynchronous shift depends on the initial density, one may consider this process as a particular kind of decentralized computation. For the sake of brevity, we will not develop this point here, but we simply indicate to the readers interested by this issue that similar stochastic rules have been used to solve the density classification problem (see, e.g., (de Oliveira 2014; Fatès 2013b; Fukś 2002) and de Oliveira’s article in this encyclopedia).

From the Shift to Other Quadratic Rules

We now examine step by step how to generalize the example of the asynchronous shift given above to a wider class of rules.

With the decomposition described above, we can readily deduce that the Markov chain described for counting the number of 1 s for the shift rule (BDEG) also applies for rule CG, for which the 10-frontier performs a non-biased random walk and for rule BCDEFG, for which the two frontiers perform a random walk.

In a second time, we can ask what happens if we change the code of these rules by removing the transition D of their code, that is, we set 101 → 0 and make the transition D inactive. This transformation implies that the 0-regions can no longer disappear, while the 1-regions may disappear if an isolated 1 is updated (010 → 0). As a consequence, the fixed point 1 is no longer reachable, and the system will almost surely converge to the fixed point 0 for an initial condition different from 1. The system will thus most of the time behave as a regular martingale, but sometimes it will “bounce” on an isolated 0. Is the average convergence time still quadratic? The answer is positive: even though the behavior cannot be described (simply) by a martingale, it is possible to “save” the previous results and still obtain a quadratic scaling of the WECT. Interested readers may refer to our study on fully asynchronous doubly quiescent (A quiescent state is a state q such that the local rule f obeys f(q,…, q) = q.) rules for the mathematical details (Fatès et al. 2006a).

Functions with a Potential

In the previous paragraph, we started from the shift rule (BDEG), showed that it had a quadratic WECT, an then indicated that five other rules had a similar qualitative behavior and a quadratic WECT. The other rules were obtained by making the transition D inactive or by changing the behavior of the frontiers, as long as this movement remained a non-biased random walk (Fig. 5).
Fig. 5

Space-time diagrams showing the evolution of four rules with a quadratic worse expected convergence time (WECT) .

We now propose to examine what happens if we dare to “touch” a transition that breaks the random movement of the frontiers. Concretely, let us make the transition B inactive: we obtain the minimal representative rule DEG (168). The evolution of this rule is displayed in Fig. 6; it can be seen that the evolution of the rule is less “spectacular” than the quadratic rules. The size of the 1-regions regularly decreases until all the regions disappear and the system reaches the fixed point 0. It is easy to see that in the case where the initial condition does not contain an isolated 0, the evolution of the number of 1 s is a non-increasing function. Now, let us consider the function ϕ : Q → ℕ defined by ϕ(x) = |x| 1 + |x| 01. Writing (X t ) = ϕ(x t ), one can verify that the evolution of (X t ) is non-increasing. Indeed, if a transition D is applied, the number of 1 s increases by 1, but the number of regions also decreases by 1. Moreover, we have that X t = 0 implies that x t = 0. The function ϕ can thus be named a potential: it is a positive, non-increasing function of the current state of the system, which equals to zero when the system has attained its attractive fixed point. This argument can be applied for showing a linear WECT for the following four rules (G is active) 136:EG, 140:G, 168:DEG, and 172:DG and the following four rules (F and G are active) 128:EFG, 132:FG, 160:DEFG, and 164:DFG.
Fig. 6

Space-time diagrams showing two evolutions of two rules with a linear worse expected convergence time (WECT)

Interestingly, a similar type of convergence can also be obtained by adding an active transition to the shift rule. For example, let us consider ECA BDEFG (162). Its evolution is shown in Fig. 6. One should observe that the 01-frontiers perform a non-biased random walk, while the 10-frontier tends to move to the left. This means that the 1-regions have a tendency to decrease, but their evolution is no longer monotonous as in the case of rule DEG. It can be shown that if we take back the function ϕ(x) = |x| 1 + |x| 01 and X t = ϕ(x t ), then (X t ) is a super-martingale, that is, its average value decreases in average. This property and other conditions ensuring that it cannot stay too “static” imply that its convergence time scales linearly with the ring size n (Fatès et al. 2006a). Indeed, for any configuration that is not a fixed point, the quantity \( \mathbb{E}\left\{{X}^{t+1}-{X}^t\left|{x}^t\right.\right\} \) is negative. The same method can be applied for showing the convergence in linear time for the rule 130:BEFG.

Non-polynomial Types of Convergence.

For the sake of brevity, we will not go here into the details but only indicate the other classes of convergence that were exhibited. Readers may consult Fatès et al. (2006a) for detailed arguments.
  • The rules 200:E and 232:DE have a logarithmic WECT. This can be shown with the same techniques as for the convergence of the coupon-collector process (Fatès et al. 2006a).

  • The rule 154:BCEG has an exponential WECT. This comes from a kind of paradox: the rule has a tendency to increase the number of 1 s, but its only fixed point 1 is not reachable. The only way it can converge is by reaching the fixed point 0, a phenomenon that is very unlikely.

  • The rules 134:BFG, 142:BG, 156:CG, and 150:BCFG are non-converging. This is because in all these rules, transitions D and E are inactive and, at the same time, the frontiers are not static.

Other Elementary Rules

The question of classifying the other ECA rules, where no state or only one state is quiescent, is still open. Some conjectures have been stated from experimental observations, but they still deserve an in-depth analysis (Fatès 2013a). In particular, there are currently only partial results for all the rules which are conjectured to converge “very rapidly,” that is, in logarithmic time (Fatès 2014b).

From Fully Asynchronous to α-Asynchronous Updating

What happens if one uses a partially synchronous updating scheme instead of a totally asynchronous one? Regnault et al. have extended the convergence results of the doubly quiescent ECA to the case of α-asynchronous updating (Fatès et al. 2006b). The possibility of having simultaneous updates of neighboring cells creates additional “local movements,” and the behavior of these rules is more difficult to analyze. In particular, the authors have identified four phenomena that are specifically related to the α-asynchronous updating: the shift, the fork, the spawn, and the annihilation. These phenomena are shown in Fig. 7.
Fig. 7

New phenomena observed with the α-asynchronous updating of linear CA (From the work of Fatès et al. (2006b))

The authors developed an interesting analytical framework (potential functions, masks, etc.) and succeeded in giving bounds on the convergence of 19 (minimal) doubly quiescent rules, leaving the question open for five other rules. The various rules show different kinds of scaling relations of the WECT, depending on α and n. If we consider the dependence on n only, the families of functions are the same as those obtained for fully asynchronous dynamics, that is, logarithmic, linear, quadratic, exponential, and infinite. However, there are rules whose type of converge varies from the fully asynchronous updating to α-asynchronous updating. For example, rule 152:CEG, which is quadratic with a fully asynchronous updating (see above), becomes linear for α-asynchronous updating. Two rules, namely, ECA 146:BCEFG and 178:BCDEFG, were conjectured to display a phase transition: their type of converge may change from polynomial to exponential depending on whether the α is greater or lower than a particular critical value. This property was partially proved by Regnault in a thorough study of ECA 178, where the polynomial and exponential convergence times were formally obtained for extrema values of the synchrony rate (Regnault 2013). Ramos and Leite recently studied a generalization of this model where the asynchronous case appears as a special case of the family of probabilistic cellular automata that are studied (Ramos and Leite 2017).

Two-Dimensional Rules

The study of the convergence properties of simple two-dimensional rules has been carried out for the so-called totalistic cellular automata , where the local rule only depends on the number of 1 s in the neighborhood (Fatès and Gerin 2009). For the von Neumann neighborhood (the cell and its four nearest neighbors), there are 26 such rules. Their WECT were also analyzed for the fully asynchronous updating, and all rules but one was found to fall into the previous classes of convergence. One remarkable exception was given by the epidemic rule, where a 0 turns into a 1 if it has a 1 in its neighborhood and then will always remain a 1. This rule has a WECT which scales as \( \varTheta \left(\sqrt{n}\right). \) Even though this scaling property can be intuitively understood from the dynamics of the rule, which merely amounts to “contaminating” neighboring cells, proving the class of convergence was a difficult task. It is only recently that a proof has been proposed by Gerin, who succeeded in applying subtle combinatorial arguments to obtain upper and lower bounds on the time of convergence (Gerin 2017).

The minority rule received a special attention. Indeed, when updated asynchronously, it has the ability to create patterns which can take the form of checkerboard or stripes. The behavior of this rule with an asynchronous updating was analyzed in the case of von Neumann and Moore neighborhood (the cell and its eight nearest neighbors) (Regnault et al. 2009, 2010). Regnault et al. noticed that the convergence to the fixed point was not uniform: the process can be separated in two phases – first the “energy” decreases rapidly, and then the system stays in a low-energy state where it will progressively approach the fixed point by moving the unstable patterns, thanks to the random fluctuations. It is an open question to know to which extent this type of behavior can be found in other contexts, e.g., lattice-gas cellular automata (Bouré et al. 2013b).

The convergence properties can thus be determined quite precisely but only for a family of simple binary cellular automata rules. It is an open problem to find such analytical tools. As far as the α-asynchronous updating is concerned, the results are even more restricted. As we will see in the following, this is not so surprising because the behavior of some rules sometimes requires the introduction of tools from advanced statistical physics.

Phase Transitions Induced by α-Asynchronous Updating

The Game of Life

We propose to come back to the phenomenon observed in Fig. 1 (see p. 4). Blok and Bergersen were the first authors to give a precise explanation of the change of behavior in the Game of Life, the phenomenon that was described in the introductory part of this article. They identified the existence of a second-order phase transitio n (Informally, in statistical physics, phase transitions are defined by the existence of a discontinuity in the values taken by a macroscopic parameter, called the order parameter, when system is submitted to a continuous variation of a control parameter. First-order transitions are those for which the discontinuity appears directly on the order parameter, while second-order phase transitions (or continuous phase transitions) are those where the derivative of the order parameter is infinite.) which separates two qualitatively different behaviors: a high-density steady state with vertical and horizontal stripes and low-density steady state with avalanches (Blok and Bergersen 1999). They measured the critical value of the synchrony rate at α c 0.906 and showed that near the critical point, the stationary density d obeyed a power law of the form d ∼ (α − αc) β . It is well known in the field of statistical physics that the values taken by the power laws are not arbitrary and that various systems of unrelated fields may display the same critical exponents (see F. Bagnoli’s article in this encyclopedia). The class of systems which share the same values of exponents is called a universality class, and in the case of the Game of Life, Blok and Bergersen found that its phase transition was likely to belong to the universality class of directed percolation (also called oriented percolation or Reggeon field theory).

These measures were later confirmed by a set of more precise experiments (Fatès 2010), and the critical value of the synchrony rate was measured at α c ≈ 0.911. Moreover, for the Game of Life, the critical phenomenon was shown to be robust to the introduction of a small degree of irregularity in the grid. This phase transition was also observed for other lifelike rules (Fatès 2010).

Elementary Cellular Automata

In the first experiment where the whole set of ECAs was examined with an α-asynchronous updating (Fatès and Morvan 2005), some rules were observed to display an abrupt variation of the density for a given value of the synchrony rate α. This phenomenon was later studied in detail, and this critical phenomenon was identified for ten (non-equivalent) rules. As for the Game of Life, we are here in the presence of second-order phase transitions which belong to the directed percolation universality class (Fatès 2009). The values of the measured critical synchrony rates are reported in Table 3.
Table 3

Critical synchrony rates for the ECA with a phase transition

ECA

6

18

26

38

50

58

106

134

146

178

α c

0.283

0.714

0.475

0.041

0.628

0.340

0.815

0.082

0.675

0.410

It is a puzzling question to know why these ten rules are specifically producing such critical phenomena. Some insights to this question were given in a study of the local-structure approximations of the rules, that is, a generalization of the mean-field approximation to correlations of higher order (Fukś and Fatès 2015). This study revealed that it was possible to predict the occurrence of a phase transition, but it was not possible to use it to correctly approximate the value of the critical synchrony rate (Fig. 8). Another possible approach would be to analyze the branching-annihilating phenomenon in a specific way, with small-size Markov chains, for instance, but this remains an open path of research.
Fig. 8

Local structure approximations obtained for various approximation levels of order k (see Fukś and Fatès (2015) for details). For the sake of readability of the results, the cases k = 7 and k = 8 are omitted. The plot in red (labelled “exp”) shows the experimental steady-state density obtained for a ring size of n = 40,000 cells after 10,000 time steps

Other Questions Related to the Dynamics

In order to broaden our view of asynchronous cellular automata, we now briefly mention some other problems which have been studied with analytical tools.

Reversibility

The question of reversibility amounts to knowing if it is always possible to “go back in time” and to knowing if any configuration has a unique predecessor. This question is undecidable in general, but there are some sets of rules for which one can tell whether a rule is reversible or not (see Morita (2008) for a survey on this question). In the context of random asynchronous updating, the question cannot be transposed in a direct way because the evolution of the system is not one to one (otherwise we would have a deterministic system).

To date, two different approaches have been considered for finite systems. Wacker and Worsch proposed to examine the transition graph of the Markov chain of the asynchronous system (Wacker and Worsch 2013). A rule is said to be phase-space invertible if there exists another rule – possibly itself – whose transition graph is the “inverse” of the graph of the original rule. By “inverse” it is meant that the directions of the transitions are reversed. In other words, the probabilities to go from x to y are identical if one permutes x and y. Interestingly, the authors show that the property of being phase-space invertible is decidable for one-dimensional fully asynchronous cellular automata.

Another approach has been proposed by Sethi et al.: to interpret the reversibility of a system as the possibility to always go back to the initial condition (Sethi et al. 2014). The problem then amounts to deciding the recurrence property of the Markov chain. This allows the authors to propose a partition of the elementary cellular automata according to their recurrence properties and to show that among the 88 non-equivalent rules, there are 16 rules which are recurrent for any ring size greater than 2 and 2 rules which are recurrent for ring sizes greater than 3 (Fatès et al. 2017). These rules are listed in Table 4. For the recurrent rules, the structure of the transition graph was analyzed as well as the number of connected components of this graph, that is, the number of communication classes of the rules. It was found that the number of classes of communication varies greatly from one rule to another: some rules have an exponential number, while others have a constant number; the most interesting examples were obtained for the rules with an “intermediary” behavior. For example, for rule 105:ADEH, the number of communication classes is 2 for an odd ring size n and is equal to n/2 + 3 when n is divisible by 4 and to n/2 when n is even and not a multiple of 4. It is an open question to generalize these results to other types of rules or to other types of updating schemes.
Table 4

Wolfram codes and transition codes of the 16 recurrent rules (From Fatès et al. (2017)). The two separate rules are recurrent for n ≠ 3

35:ABDEFGH

38:BDFGH

43:ABDEGH

46:BDGH

51:ABCDEFGH

54:BCDFGH

57:ACDEGH

60:CDGH

62:BCDGH

105:ADEH

108:DH

134:BFG

142:BG

150:BCFG

156:CG

204:I

33:ADEFGH

41:ADEGH

  

These results are encouraging, and it is rather pleasant to note that contrarily to the problem of convergence seen above, deciding the recurrence properties of an ECA can be achieved. It is thus interesting to see to which extent these results apply to a broader class of systems, including infinite-size systems.

Coalescence

In the experimental study of the α-asynchronous ECA (Fatès and Morvan 2005), a strange phenomenon was noticed for ECA 46, almost by chance: though this rule does not converge to a fixed point and remains in a chaotic-like steady state, its evolution does not seem to depend on the initial condition. All seems to happen as if the evolution of the rule was only dictated by the sequence of updates that is applied. This phenomenon, named coalescence , can be observed in Fig. 9: if we start from two different initial conditions of the same size and apply the same updates on the two systems, they quickly synchronize and adopt the same evolution. This is a particular kind of synchronization where no desynchronization is possible: after the coalescence has occurred, the two trajectories remain identical as the local rules are deterministic. The question is to know under which conditions coalescence happens and how long does it take in average for two different initial conditions to “merge” their trajectories.
Fig. 9

Rapid coalescence phenomenon for ECA 46 with fully asynchronous updating. The same updates are applied on two systems with two different random initial conditions (left and middle). The right diagram shows the agreement and disagreement of the two systems. Cells in white and light gray, respectively, show agreement on state 0 or 1, while red and green show disagreement (the order is not important)

Rouquier and Morvan have studied experimentally this phenomenon for the 88 ECA with α-asynchronous updating (Rouquier and Morvan 2009). They discovered an unexpected richness of behavior: some rules coalesce rapidly and others slowly, some never coalesce, some even display phase transitions, etc. Insights have been given by Francès de Mas on this question, and a classification of the convergence time has been given from both the observation of space-time diagrams and an analysis of the behavior (de Mas 2017). It is still an open question to provide a complete mathematical analysis of these systems and to issue a proof that coalescence can indeed happen in a linear time with respect to the ring size.

Other Problems

There are many other problems which have led to various interesting experimental or theoretical works. For instance, Gacs (2001) and then MacAuley and Mortveit (2010, 2013; Macauley et al. 2008) have provided a deep analysis on the independence of the trajectories of an asynchronous with regard to the updating sequence. Chassaing and Gerin analyzed the scaling relationships that would lead to an infinite-size continuous framework (Chassaing and Gerin 2007). This framework is also analyzed in detail by Dennunzio et al., who examined how the theory of measure can be applied to one-dimensional systems defined on an infinite line (Dennunzio et al. 2013, 2017).

As an example of a possible application of the use of these dynamical systems, we mention the work of Das et al., who proposed to use such models for pattern classification (Sethi et al. 2016), and the work of Takada et al., who designed asynchronous self-reproducing loops (Takada et al. 2007a). These are only some entry point to the literature on this topic, and we refer again to our survey paper for a wider scope (Fatès 2014a).

Openings

We have seen that the randomness involved in the asynchronous updating create an amazing source of new questions on cellular automata. After more than two decades of continued efforts, this topic shows signs of maturity, and although it remains in large part a terra incognita, there are some insights on how asynchronous cellular automata can be studied with a theoretical point of view. A set of analytical tools are now available, and when the analysis fails to answer all the questions, one can carry out numerical simulations. Readers should now be convinced that asynchronous cellular automata are by no means some “exotic” mathematical objects but constitute a thriving field of research. The elements we presented here are only a small part of this field and should be completed by a more extensive bibliographical work. Before closing this text, we want to present a few questions that are currently investigated.

Defining Asynchrony

As mentioned in the introduction, asynchrony is a concept that can be defined with a great variety of forms. For example, the notion of α-asynchronous updating scheme needs to be generalized to go beyond the simple homogeneous finite case. This has led to propose the use of some measure-theoretic tools to define m-asynchronous cellular automata to include the cases of nonhomogeneous probabilities of updating, infinitesimal ones, etc. (Dennunzio et al. 2012, 2013).

To complete this point, let us underline that Bouré et al. have proposed to examine the case where the randomness occurs not on the moments of updating but on the possibility to miss the information from one or several neighbors (Bouré et al. 2012). Interestingly, the study of these new updating schemes, named β- and γ-asynchronous updating schemes, shows that their behavior partially overlaps with α-asynchronous systems but also reveals some novel and unexpected behaviors (e.g., other rules show a phase transitions).

Asynchronous Models

The theoretical results obtained so far do not tell us what is a good model of asynchrony in general. Since cellular automata are defined with a discrete of time and space, it is not straightforward to decide a priori to use a synchronous updating, or a fully asynchronous one, or a partially synchronous one. In fact, the most reasonable position would be to test various updating schemes on a rule and to examine if it is robust or sensitive to these modifications. Although this critical attitude has been quite rare so far, a good example of such a study has been provided by Grilo and Correia, who made a systematic study of the effects of the updating in the spatially extended evolutionary games. This question rose after the criticisms made by Huberman and Glance (1993) to the model proposed by Nowak and May (1992). We think that exploring more systematically these issues on real-world models could help us understand to which extent the simplifications operated in a model are justified or are a potential source of artifacts (see Fatès (2014a) for other examples).

Experimental Approaches and Theoretical Questions

The questions of how to measure the behavior of asynchronous systems are of course primordial. Among the various approaches, let us mention that Silva and Correia have shown the importance of taking into account the time-rescaling effects when using experiments (Silva and Correia 2013). Louis has underlined that the efficiency of a simulation may greatly vary depending on the different regimes that may occur in a simulation (Louis 2015). Recently, Bolt et al. have raised the problem of identification: if one is given space-time diagrams with missing parts, how can one find the rule which generated this piece of information? (Bolt et al. 2016). (See also A. Adamatzky’s article in this encyclopedia for the general problem of identification.)

New Models of Computation

As mentioned earlier, it is no surprise if the computing abilities of general asynchronous cellular automata are the same as those of their deterministic counterparts. However, as shown by various authors, the question becomes much more delicate if one asks how to simulate an asynchronous system by another asynchronous system or if one wants to design asynchronous systems which hold good computing abilities and use a limited number of states (Takada et al. 2007b; Worsch 2013).

On the technological side, let us mention the work of Silva et al. on modeling the interactions between (static) robots which need to be synchronized (Silva et al. 2015). Lee, Peper, and their collaborators aimed at developing asynchronous circuits which are designed with simple local rules (Peper et al. 2003). Such Brownian cellular automata (Lee and Peper 2008) exploit the inherent fluctuations of the particles to perform asynchronous computations (Lee et al. 2016b; Peper et al. 2010). They represent a potential source of major technical innovations, in particular with the possibility of implementing such circuits with DNA reaction-diffusion systems (Yamashita et al. 2017) or single electron tunneling techniques (Lee et al. 2016a).

Cross-References

Bibliography

  1. Belgacem S, Fatès N (2012) Robustness of multi-agent models: the example of collaboration between turmites with synchronous and asynchronous updating. Complex Syst 21(3):165–182MathSciNetzbMATHGoogle Scholar
  2. Blok HJ, Bergersen B (1999) Synchronous versus asynchronous updating in the “game of life”. Phys Rev E 59:3876–3879ADSCrossRefGoogle Scholar
  3. Bolt W, Wolnik B, Baetens JM, De Baets B (2016) On the identification of α-asynchronous cellular automata in the case of partial observations with spatially separated gaps. In: De Tré G, Grzegorzewski P, Kacprzyk J, Owsinski JW, Penczek W, Zadrozny S (eds) Challenging problems and solutions in intelligent systems. Springer, pp 23–36Google Scholar
  4. Bouré O, Fatès N, Chevrier V (2012) Probing robustness of cellular automata through variations of asynchronous updating. Nat Comput 11:553–564MathSciNetCrossRefzbMATHGoogle Scholar
  5. Bouré O, Fatès N, Chevrier V (2013a) First steps on asynchronous lattice-gas models with an application to a swarming rule. Nat Comput 12(4):551–560MathSciNetCrossRefzbMATHGoogle Scholar
  6. Bouré O, Fatès N, Chevrier V (2013b) A robustness approach to study metastable behaviours in a lattice-gas model of swarming. In: Kari J, Kutrib M, Malcher A (eds) Proceedings of automata’13, volume 8155 of lecture notes in computer science. Springer, Gießen, Germany, pp 84–97Google Scholar
  7. Buvel RL, Ingerson TE (1984) Structure in asynchronous cellular automata. Physica D 1:59–68MathSciNetGoogle Scholar
  8. Chassaing P, Gerin L (2007) Asynchronous cellular automata and brownian motion. In: DMTCS proceedings of AofA’07, volume AH. Juan les Pins, France, pp 385–402Google Scholar
  9. Chevrier V, Fatès N (2010) How important are updating schemes in multi-agent systems? An illustration on a multi-turmite model. In: Proceedings of AAMAS ‘10. International Foundation for Autonomous Agents and Multiagent Systems, Richland, pp 533–540Google Scholar
  10. Cornforth D, Green DG, Newth D (2005) Ordered asynchronous processes in multi-agent systems. Physica D 204(1–2):70–82ADSMathSciNetCrossRefGoogle Scholar
  11. de Mas JF (2017) Coalescence in fully asynchronous elementary cellular automata. Technical report, HAL preprint hal-01627454Google Scholar
  12. de Oliveira PPB (2014) On density determination with cellular automata: results, constructions and directions. J Cell Autom 9(5–6):357–385MathSciNetzbMATHGoogle Scholar
  13. Dennunzio A, Formenti E, Manzoni L (2012) Computing issues of asynchronous CA. Fundamenta Informaticae 120(2):165–180MathSciNetzbMATHGoogle Scholar
  14. Dennunzio A, Formenti E, Manzoni L, Mauri G (2013) m-asynchronous cellular automata: from fairness to quasi-fairness. Nat Comput 12(4):561–572MathSciNetCrossRefzbMATHGoogle Scholar
  15. Dennunzio A, Formenti E, Manzoni L, Mauri G, Porreca AE (2017) Computational complexity of finite asynchronous cellular automata. Theor Comput Sci 664:131–143MathSciNetCrossRefzbMATHGoogle Scholar
  16. Fatès N (2009) Asynchronism induces second order phase transitions in elementary cellular automata. J Cell Autom 4(1):21–38MathSciNetzbMATHGoogle Scholar
  17. Fatès N (2010) Does life resist asynchrony? In: Adamatzky A (ed) Game of life cellular automata. Springer, London, pp 257–274CrossRefGoogle Scholar
  18. Fatès N (2013a) A note on the classification of the most simple asynchronous cellular automata. In: Kari J, Kutrib M, Malcher A (eds) Proceedings of automata’13, volume 8155 of lecture notes in computer science. Springer, Netherlands, pp 31–45.  https://doi.org/10.1007/s11047-013-9389-2
  19. Fatès N (2013b) Stochastic cellular automata solutions to the density classification problem – when randomness helps computing. Theory Comput Syst 53(2):223–242MathSciNetCrossRefzbMATHGoogle Scholar
  20. Fatès N (2014a) A guided tour of asynchronous cellular automata. J Cell Autom 9(5–6):387–416MathSciNetzbMATHGoogle Scholar
  21. Fatès N (2014b) Quick convergence to a fixed point: a note on asynchronous elementary cellular automata. In: Was J, Sirakoulis GC, Bandini S (eds) Proceedings of ACRI’14, volume 8751 of lecture notes in computer science. Krakow, Poland, Springer, pp 586–595Google Scholar
  22. Fatès N, Gerin L (2009) Examples of fast and slow convergence of 2D asynchronous cellular systems. Old City Publishing. J Cell Autom 4(4):323–337. http://www.oldcitypublishing.com/journals/jca-home/
  23. Fatès N, Morvan M (2005) An experimental study of robustness to asynchronism for elementary cellular automata. Complex Syst 16:1–27MathSciNetzbMATHGoogle Scholar
  24. Fatès N, Morvan M, Schabanel N, Thierry E (2006a) Fully asynchronous behavior of double-quiescent elementary cellular automata. Theor Comput Sci 362:1–16MathSciNetCrossRefzbMATHGoogle Scholar
  25. Fatès N, Regnault D, Schabanel N, Thierry E (2006b) Asynchronous behavior of double-quiescent elementary cellular automata. In: Correa JR, Hevia A, Kiwi MA (eds) Proceedings of LATIN 2006, volume 3887 of lecture notes in computer science. Valdivia, Chile, Springer, pp 455–466Google Scholar
  26. Fatès N, Sethi B, Das S (2017) On the reversibility of ecas with fully asynchronous updating: the recurrence point of view. To appear in a monography edited by Andrew Adamatzky – Preprint available on the HAL server, id: hal-01571847Google Scholar
  27. Fukś H (2002) Nondeterministic density classification with diffusive probabilistic cellular automata. Phys Rev E 66(6):066106ADSCrossRefGoogle Scholar
  28. Fukś H, Fatès N (2015) Local structure approximation as a predictor of second-order phase transitions in asynchronous cellular automata. Nat Comput 14(4):507–522MathSciNetCrossRefGoogle Scholar
  29. Gács P (2001) Deterministic computations whose history is independent of the order of asynchronous updating. Technical report – arXiv:cs/0101026Google Scholar
  30. Gerin L (2017) Epidemic automaton and the eden model: various aspects of robustness. Text to appear in a monography on probabilistic cellular automata. SpringerGoogle Scholar
  31. Huberman BA, Glance N (1993) Evolutionary games and computer simulations. Proc Natl Acad Sci U S A 90:7716–7718ADSCrossRefzbMATHGoogle Scholar
  32. Kari J, Taati S (2015) Statistical mechanics of surjective cellular automata. J Stat Phys 160(5):1198–1243ADSMathSciNetCrossRefzbMATHGoogle Scholar
  33. Lee J, Peper F (2008) On brownian cellular automata. In: Adamatzky A, Alonso-Sanz R, Lawniczak AT, Martínez GJ, Morita K, Worsch T (eds) Proceedings of automata 2008. Luniver Press, Frome, pp 278–291Google Scholar
  34. Lee J, Adachi S, Peper F, Morita K (2004) Asynchronous game of life. Phys D 194(3–4):369–384MathSciNetCrossRefzbMATHGoogle Scholar
  35. Lee J, Peper F, Cotofana SD, Naruse M, Ohtsu M, Kawazoe T, Takahashi Y, Shimokawa T, Kish LB, Kubota T (2016a) Brownian circuits: designs. Int J Unconv Comput 12(5–6):341–362Google Scholar
  36. Lee J, Peper F, Leibnitz K, Ping G (2016b) Characterization of random fluctuation-based computation in cellular automata. Inf Sci 352–353:150–166CrossRefGoogle Scholar
  37. Louis P-Y (2015) Supercritical probabilistic cellular automata: how effective is the synchronous updating? Nat Comput 14(4):523–534MathSciNetCrossRefGoogle Scholar
  38. Macauley M, Mortveit HS (2010) Coxeter groups and asynchronous cellular automata. In: Bandini S, Manzoni S, Umeo H, Vizzari G (eds) Proceedings of ACRI’10, volume 6350 of lecture notes in computer science. Springer, Ascoli Piceno, Italy, pp 409–418Google Scholar
  39. Macauley M, Mortveit HS (2013) An atlas of limit set dynamics for asynchronous elementary cellular automata. Theor Comput Sci 504:26–37. Discrete mathematical structures: from dynamics to complexityMathSciNetCrossRefzbMATHGoogle Scholar
  40. Macauley M, McCammond J, Mortveit HS (2008) Order independence in asynchronous cellular automata. J Cell Autom 3(1):37–56MathSciNetzbMATHGoogle Scholar
  41. Mairesse J, Marcovici I (2014) Around probabilistic cellular automata. Theor Comput Sci 559:42–72. Non-uniform cellular automataMathSciNetCrossRefzbMATHGoogle Scholar
  42. Moore EF (1962) Machine models of self-reproduction. Proc Symp Appl Math 14:17–33. (Reprinted in Essays on cellular automata, Burks AW (ed), University of Illinois Press, 1970)CrossRefzbMATHGoogle Scholar
  43. Morita K (2008) Reversible computing and cellular automata – a survey. Theor Comput Sci 395(1):101–131MathSciNetCrossRefzbMATHGoogle Scholar
  44. Nakamura K (1974) Asynchronous cellular automata and their computational ability. Syst Comput Controls 5(5):58–66MathSciNetGoogle Scholar
  45. Nakamura K (1981) Synchronous to asynchronous transformation of polyautomata. J Comput Syst Sci 23(1):22–37MathSciNetCrossRefzbMATHGoogle Scholar
  46. Nowak MA, May RM (1992) Evolutionary games and spatial chaos. Nature 359:826–829ADSCrossRefGoogle Scholar
  47. Peper F, Lee J, Adachi S, Mashiko S (2003) Laying out circuits on asynchronous cellular arrays: a step towards feasible nanocomputers? Nanotechnology 14(4):469ADSCrossRefGoogle Scholar
  48. Peper F, Lee J, Isokawa T (2010) Brownian cellular automata. J Cell Autom 5(3):185–206MathSciNetzbMATHGoogle Scholar
  49. Ramos AD, Leite A (2017) Convergence time and phase transition in a non-monotonic family of probabilistic cellular automata. J Stat Phys 168(3):573–594ADSMathSciNetCrossRefzbMATHGoogle Scholar
  50. Regnault D (2013) Proof of a phase transition in probabilistic cellular automata. In: Béal MP and Carton O (eds) Proceedings of developments in language theory, volume 7907 of lecture notes in computer science. Springer, Marne-la-Vallée, France, pp 433–444Google Scholar
  51. Regnault D, Schabanel N, Thierry E (2009) Progresses in the analysis of stochastic 2D cellular automata: a study of asynchronous 2D minority. Theor Comput Sci 410(47–49):4844–4855MathSciNetCrossRefzbMATHGoogle Scholar
  52. Regnault D, Schabanel N, Thierry E (2010) On the analysis of “simple” 2d stochastic cellular automata. Discrete Math Theor Comput Sci 12(2):263–294MathSciNetzbMATHGoogle Scholar
  53. Rouquier J-B, Morvan M (2009) Coalescing cellular automata: synchronization by common random source for asynchronous updating. J Cell Autom 4(1):55–78MathSciNetzbMATHGoogle Scholar
  54. Schönfisch B, de Roos A (1999) Synchronous and asynchronous updating in cellular automata. Biosystems 51:123–143CrossRefGoogle Scholar
  55. Sethi B, Fatès N, Das S (2014) Reversibility of elementary cellular automata under fully asynchronous update. In: Gopal TV, Agrawal M, Li A, Cooper B (eds) Proceedings of TAMC’14, volume 8402 of lecture notes in computer science. Springer, Chennai, India, pp 39–49Google Scholar
  56. Sethi B, Roy S, Das S (2016) Asynchronous cellular automata and pattern classification. Complexity 21:370–386ADSMathSciNetCrossRefGoogle Scholar
  57. Silva F, Correia L (2013) An experimental study of noise and asynchrony in elementary cellular automata with sampling compensation. Nat Comput 12(4):573–588MathSciNetCrossRefGoogle Scholar
  58. Silva F, Correia L, Christensen AL (2015) Modelling synchronisation in multirobot systems with cellular automata: analysis of update methods and topology perturbations. In: Sirakoulis GC, Adamatzky A (eds) Robots and lattice automata, volume 13 of emergence, complexity and computation. Springer International Publishing, Springer. pp 267–293Google Scholar
  59. Takada Y, Isokawa T, Peper F, Matsui N (2007a) Asynchronous self-reproducing loops with arbitration capability. Phys D Nonlinear Phenom 227(1):26–35ADSMathSciNetCrossRefzbMATHGoogle Scholar
  60. Takada Y, Isokawa T, Peper F, Matsui N (2007b) Asynchronous self-reproducing loops with arbitration capability. Phys D 227(1):26–35MathSciNetCrossRefzbMATHGoogle Scholar
  61. Vichniac GY (1984) Simulating physics with cellular automata. Phys D Nonlinear Phenom 10(1):96–116ADSMathSciNetCrossRefzbMATHGoogle Scholar
  62. Vielhaber M (2013) Computation of functions on n bits by asynchronous clocking of cellular automata. Nat Comput 12(3):307–322MathSciNetCrossRefzbMATHGoogle Scholar
  63. Wacker S, Worsch T (2013) On completeness and decidability of phase space invertible asynchronous cellular automata. Fundam Informaticae 126(2–3):157–181MathSciNetzbMATHGoogle Scholar
  64. Wolfram S (1985) Twenty problems in the theory of cellular automata. Phys Scr T9:170ADSMathSciNetCrossRefzbMATHGoogle Scholar
  65. Worsch T (2013) Towards intrinsically universal asynchronous CA. Nat Comput 12(4):539–550MathSciNetCrossRefzbMATHGoogle Scholar
  66. Yamashita T, Isokawa T, Peper F, Kawamata I, Hagiya M (2017) Turing-completeness of asynchronous non-camouflage cellular automata. In: Dennunzio A, Formenti E, Manzoni L, Porreca AE (eds) Proceedings of AUTOMATA 2017, volume 10248 of lecture notes in computer science. Springer, Milan, Italy, pp 187–199Google Scholar

Copyright information

© Springer Science+Business Media LLC 2018

Authors and Affiliations

  1. 1.LORIA UMR 7503Inria Nancy – Grand EstNancyFrance