An analysis of different types and effects of asynchronicity in cellular automata update schemes

Abstract

This paper introduces the problematics deriving from the adoption of asynchronous update schemes in CA models. Several cellular automata update schemes and a tentative classification of such schemes are introduced and discussed. In order to analyze the effects of the different update schemes, a class of simple CA—called One neighbor binary cellular automata (1nCA)—is then introduced. An overview of the general features of 1nCA is described, then the effects of six different updates schemes on all the class of 1nCA are described.

1 Introduction

A fundamental feature of Cellular Automata models is the fact that time is considered as discrete and state updates occur synchronously and in parallel. Nevertheless, this assumption can be quite restrictive on the class of phenomena that can be modeled and several authors have argued that asynchronous models are viable alternatives to synchronous ones and suggest that asynchronous models should be preferred where there is no evidence of a global clock in the modeled reality (Paolo et al. 2000). Moreover, as argued in Schönfisch and de Roos (1999), sometimes the modeling activity is aimed at achieving a form of “model stability” for which the qualitative results of the model depend only on the basic assumptions derived from the modeled system, and they are not to be ascribed to the actual details of the employed model, such as the update scheme of a CA.

In general, when cells updating does not take place simultaneously we talk about an asynchronous CA; this term thus does not state any precise property of this kind of model, it essentially expresses the fact that a property (i.e., synchronicity in cells updates) is not valid. One of the main aims of this paper is to clarify that there are substantially different ways in which a CA can be asynchronous and to present an investigation of the these different ways and their implications on the overall system dynamics, by defining and adopting a specific sample CA model for this purpose.

One of the first works proposing an asynchronous updating scheme is described in Kanada (1994): the model is characterized by different cell updating schemes, basically sequential ones, in which a single cell is updated at each time step. The order of the updating sequence is defined as one of the following three methods: Random order, Fixed Random Order, and Interlaced order.

In Page (1997), issues and implications of asynchronous update schemes is analyzed from the point of view of modeling economical systems: in this approach, cells that benefit most (according to some utility function) update their state first. This incentive based update approach, however, is clearly more suited to characterize agent–based models, since the extrapolation of a “utility from updating” function is much more natural in models comprising self-interested entities as first class abstractions rather than simple cells.

In Cornforth et al. (2005) the adopted notion of agent is instead much more similar to CA cells; three classes of update scheme are identified in this work: Synchronous Update, Random Asynchronous (RAS), and Ordered Asynchronous (OAS). The first scheme is the traditional CA updating scheme; according to the RAS scheme, at any given time individuals to be updated are selected at random according to some probability distribution. In the OAS update process, the updating of individual states follows a systematic pattern. The authors consider a total of six update patterns, including two RAS schemes and three OAS scheme: Synchronous Scheme, Random Independent (RAS) , Random Order (RAS), Cyclic (OAS), Clocked (OAS), and Self-Sync. The author chose to implement local synchronicity by using a coupled oscillator approach. The period of each timer is adjusted after an update so as to more closely match the period of other cells in its neighborhood.

Another relevant study about the effects of asynchronicity in a CA model is described in Fatès et al. (2005): in particular, the authors focus on the robustness of one dimensional asynchronous CAs characterized by a RAS scheme.

In addition to CA models, a relevant area in which issues and implications of updating schemes have been analyzed is related to random boolean networks Darabos et al. (2007), a model in which not only timing but also spatial constraints are relaxed when compared to traditional CA.

Finally, in addition to the above mentioned works taking an agent-based modeling approach, it is worth mentioning the fact that agent activation issues have been considered both from a general situated agents perspective (Bandini et al. 2005), in application situations considering both the specification and implementation of simulation systems (Bandini and Vizzari 2006) and the definition of protocols for distributed systems (Fang et al. 2005).

The aim of this paper is to provide a comprehensive analysis of different asynchronous update schemes and to evaluate the effect of their adoption in a simplified CA model; the paper is organized as follows: the following section formally introduces a comprehensive set of relevant updating schemes, while Sect. 3 introduces One neighbor binary cellular automata (1nCA), the simple model in which the different update schemes will be exhaustively tested. Section 4 presents a classification of all the possible update rules that can be adopted in the 1nCA model. Section 5 describes the effects of the adoption of the different update schemes for this model, while conclusions and future developments end the paper.

2 A classification of update schemes

In order to classify the update schemes, we define the following parameters:

• p ^(t) _i determines the period between two successive updates of the cell i at the time step t, i.e. how many time steps the cell i will wait in order to be updated. The value of p can change during the time, e.g., in the Self-Sync update scheme.

• l ^(t) _i determines the length of the updating (in terms of time steps) of the cell i at the time step t, i.e., after how many time steps the neighbor cells taking into account the new state during their update.

• d _i , determines the delay (in terms of time step) before the first update.

• U ^(t) is the set of cells beginning the update process at the at the time step t simultaneously.

• u ^(t) = |U ^(t)| is the number of cells starting the update process at the time step t.

Given the above parameter, whose meaning is exemplified in Fig. 1, a set of relevant update schemes will now be presented and discussed. For each update scheme, we give a formal definition that are successively employed for the classification of the update schemes.

Fig. 1

A schematic representation of the parameters adopted to describe the update schemes: left a sample one dimensional CA composed of four cells is shown, right a sample update diagram is used to clarify the meaning of the parameters adopted to describe the update schemes

2.1 Relevant update schemes

2.1.1 Synchronous scheme

All individuals are updated in parallel at each time step; the updating of a cell takes 1 time step. Formally, this update scheme can be characterized as follows:

$$ \begin{aligned} \forall \, t\in{\mathbb{Z}}, t >& 0,\, \forall \, i \in {\mathbb{Z}}, \leq i < N{:}\\ p^{(t)}_{i} =& 1,\, l^{(t)}_{i} = 1,\, d_i = 0,\, u^{(t)} = N \end{aligned} $$

2.1.2 Random independent

At each time step, one and only one cell, chosen at random, is updated; the updating of a cell takes 1 time step. A formal characterization of this update scheme is the following:

$$ \begin{aligned} \forall \, t \in {\mathbb{Z}}, t >& 0,\, \forall \, i \in {\mathbb{Z}},\, 0 \leq i < N{:}\\ l^{(t)}_{i} =& 1, \, u^{(t)} = 1, \, \exists \, t,i: p^{(t)}_{i} > 1 \end{aligned} $$

An example of Random Independent update scheme, related to a 1D CA composed of four cells, is shown in Fig. 2.

Fig. 2

An example of Random Independent update scheme, related to a 1D CA composed of four cells

2.1.3 Random order

All nodes are updated in random order. After the updating of all the nodes, the order is changed. The updating of each cell takes 1 time step. The maximum length of the update period is less than 2 N. This update scheme can be formally described as follows:

$$ \begin{aligned} &\forall \, t \in {\mathbb{Z}}, t > 0,\forall \, i \in {\mathbb{Z}},\, 0 \leq i < N{:}\\ & p^{(t)}_{i} < 2N, \, l^{(t)}_{i} = 1, \, d_i < N, \, u^{(t)} = 1 \end{aligned} $$

An update interval [α, ω] so that ${ \forall z \in \mathbb{Z}, z > 0, \,\alpha = 1 + zN, \, \omega = (z + 1)N }$ can be defined. In every update interval, each cell is update exactly once:

$$ \begin{aligned} & \forall \, i \in {\mathbb{Z}}, 0 \leq i < N,\\ & \forall \, t_n \in {\mathbb{Z}}, \alpha \leq t_n \leq \omega, \, \forall \, t_m \in {\mathbb{Z}}, \alpha \leq t_m \leq \omega,\\ & c_i \in U^{(t_{n})}, \,c_i \in U^{(t_{m})} \Longleftrightarrow t_n = t_{m} \end{aligned} $$

An example of Random Order update scheme, related to a 1D CA composed of four cells, is shown in Fig. 3.

Fig. 3

An example of Random Order update scheme, related to a 1D CA composed of four cells

2.1.4 Cyclic

At each time step a node is chosen according to a fixed update order. The update scheme can be formally described as follows:

$$ \begin{aligned} & \forall \, t \in {\mathbb{Z}}, t > 0,\forall \, i \in {\mathbb{Z}},\, 0 \leq i < N{:}\\ & p^{(t)}_{i} = N, \, l^{(t)}_{i} = 1, \, d_i < N, \, u^{(t)} = 1 \end{aligned} $$

We can identify three subtypes of this update scheme:

• Random cyclic: the update order is decided at random during initialisation of the automaton. This update scheme correspond to the Kannada’s Fixed Random (Kanada 1994) and Cornforth’s Cyclic OAS (Cornforth et al. 2005).

• Fixed cyclic-sequential ordered: The update order is fixed in the automaton definition. The cells are updated one-by-one according to their natural order:

  $$ d_i = 1 + i; \, q^{t} = (t - 1)\,mod\,N; \, u^{(t)} = \{ c_{q^{t}} \}. $$

• Fixed cyclic-interlaced cyclic: also called Interlaced Order in Kanada (1994). The set of cell u ^(t) to be update at time step t is calculated as $q^{t} = C (t - 1) \ mod \ N;\, u^{(t)} = \{c_{q^{t}} \}$, where C is a parameter prime to N.

An example of Fixed Cyclic-Sequential Ordered update scheme, related to a 1D CA composed of four cells, is shown in Fig. 4.

Fig. 4

An example of Fixed Cyclic-Sequential Ordered update scheme, related to a 1D CA composed of four cells

2.1.5 Generic cyclic

It is a generalization of the cyclic update scheme, obtained relaxing the constraint on the updating length. In this update scheme, the updating length is limited only by the period. Formally, this update scheme can be described as follows:

$$ \begin{aligned} & \forall \, t \in {\mathbb{Z}},\, t > 0,\, \forall \, i \in {\mathbb{Z}}, \, 0 \leq i < N{:}\\ & p^{(t)}_{i} = N, \, l^{(t)}_{i} \leq p^{(t)}, \, d_i < N ,\, u^{(t)} = 1 \end{aligned} $$

2.1.6 Clocked

A timer is assigned to each cell, so that updating is autonomous and proceeds at different rates for different cells. The update frequency of each cells is fixed. The scheme can be formally described as follows:

$$ \begin{aligned} & \forall \, t \in {\mathbb{Z}},\, t > 0, \, \forall \, i \in {\mathbb{Z}}, \, 0 \leq i < N{:}\\ & p^{(t)}_{i} = p^{(0)}_{i}, \, l^{(t)}_{i} \leq p^{(0)}_{i}, \, d_i \leq p^{(0)}_{i} \end{aligned} $$

As subtype of the Clocked update scheme is the Equal Frequency Clocked. According to this update scheme, every cells has the same update frequency:

$$ \forall \, t \in {\mathbb{Z}}, \, t > 0, \, \forall \, i \in {\mathbb{Z}}, \, 0 \leq i < N: p^{(t)}_{i} = p^{(0)}_{0} $$

2.1.7 Generic clocked

It is a generalization of the cyclic update scheme, obtained relaxing the constraint on the fixed update frequency. The two subtypes of this update scheme are the Clocked and Variable Clocked. According to the Variable Clocked scheme, a timer is assigned to each cell, so that updating is autonomous and proceeds at different rates for different cells. The updating frequency is not fixed: $\exists t,i : p^{(t)}_{i} \neq p^{(0)}_{i}$. The Self-Sync update scheme is an example of Variable Clocked scheme. An example of Variable Clocked update scheme, related to a 1D CA composed of four cells is shown in Fig. 5.

Fig. 5

An example of Variable Clocked update scheme, related to a 1D CA composed of four cells

2.2 Cellular automata update schemes ontology

In this section we present a tentative classification of the previously presented update schemes. In order to manage the complexity deriving from the classification of the schemes according to different features (e.g. the number of cells updated at each time step, the maximum length of the update period) we defined a CA Update Scheme Ontology, a formal conceptualization expressed using the OWL 2 DL¹ language, a W3C endorsed format that can be adopted to define ontologies in terms of classes, properties, instances. This language allows defining relatively rich semantics for the above entities and it is able to represent and manage features like equality and inequality of instances, restrictions (not only related to domain and range, but also to cardinality) and other characteristics of properties, enumerated classes and other formal properties. We defined specific datatype properties to characterize each update scheme (e.g. hasClock, hasUpdateOrder, hasFixedPeriod, updatedCellsPerTimeStep); each scheme is characterized by a specific configuration of values for these properties.

We computed the class hierarchy using the Pellet² semantic reasoner, an open source Java reasoner for OWL 2 DL. A reasoner is a software able to infer logical consequences from a set of asserted axioms. An example of inference for an OWL DL reasoner is the computation of the class hierarchy. In other words, starting from the update schemes defined as OWL classes, the reasoner is able to inter how update scheme are related by subclass relationships. The result of this automatic classification activity is shown in Fig. 6; in particular, the diagram shows that several update schemes are subclasses of different other classes.

Fig. 6

A schematic representation of the classes of the CA Update Scheme ontology. The classes UpdateScheme and Asynchronous are not shown for simplicity

For instance, the traditional Synchronous update scheme is both an instance of the MultiCellUpdate scheme class and also an instance of the class of schemes characterized by the fact that cell update takes exactly one time step (UpdatingLength1). Analogously, RandomIndependent and RandomOrder are instances of the RandomUpdateScheme class, being characterized by a random component, but they are also instances of the Sequential update class because they update only one cell per time step.

3 One neighbor binary cellular automata

One neighbor binary cellular automata (1nCA) is a one-dimensional Cellular Automata, with two possible states per cell. Each cell has two neighbors, left and right, defined to be the adjacent cells on either side, but the update rule consider only one neighbor per step. The neighborhood includes the cell itself and the left or the right adjacent cell and alternates between these two situations at even and odd time steps.

The size of the neighborhood is always 2, so there are four possible patterns for the neighborhood and only 16 possible rules. The number of possible rules is small compared to the 256 possible rules of the Elementary Cellular Automata, so it is easier to exhaustively study the dynamic behavior of the all rules.

These 16 1nCA rules will be referred using the Wolfram notation, with the rule numbers followed by the ▵ symbol to avoid confusion with the Elementary Cellular Automata rules (e.g. “Rule 10” is an Elementary Cellular Automata rule, “Rule 10▵” is an 1nCA rule).

We call 1nCA the cellular automata ($\mathcal{L},\mathcal{S},\mathcal{N},\mathcal{F}$) where

• $\mathcal{L} = [c_{0}, c_{1}, \ldots , c_{n}]$ is an array of n cells,

• $\mathcal{S} = \{0, 1\}$ is the set of states (k = 2),

• $\mathcal{N}_c$ is neighborhood of the cell c and $\forall c : \mathcal{L}\,|\mathcal{N}_c |=2$,

• $f : \mathcal{S}^2 \rightarrow \mathcal{S}$ is a transition function.

Denoting the cell c at position i as c _i , the neighborhood $\mathcal{N}_{c_{i}}^{(t)}$ of the cell c _i at time t is defined as $\mathcal{N}_{c_{i}}^{(t)} = {[ c_i, n_{c_{i}}^{(t)} ]}$ where $n_{c_{i}}^{(t)}$ is the neighbor of the cell, given by

$$ n_{c_{i}}^{(t)} = \left\{\begin{array}{ll} c_{i+1} & \hbox{ if } t\,\hbox{is even} \\ c_{i-1} & \hbox{otherwise}\\ \end{array}\right. $$

The neighborhood of the cell c _i at different time steps is shown in Fig. 7.

Fig. 7

The neighborhood of the cell c _i at different time steps

Following the Wolfram’s notation, the rules are characterized by a sequence of binary values ($\beta_i \in S$) associated with each of the four possible patterns for the neighborhood. The transition function is defined as:

$$ f(c_i, n_{c_i}^{(t)}) = \left\{\begin{array}{ll} \beta_0 & \hbox{ if } c_i = 0, n_{c_{i}}^{(t)} = 0 \\ \beta_1 & \hbox{ if } c_i = 0, n_{c_{i}}^{(t)} = 1 \\ \beta_2 & \hbox{ if } c_i = 1, n_{c_{i}}^{(t)} = 0 \\ \beta_3 & \hbox{ if } c_i = 1, n_{c_{i}}^{(t)} = 1 \\ \end{array}\right. $$

As shown in Fig. 8, there are 16 possible transition functions, identified by a rule number $R = \sum_{i=0}^{3} \beta_{i}2^{i}$.

Fig. 8

Representation of the 16 1nCA transition rules

The configuration of a cellular automata is a mapping $q : \mathcal{L} \rightarrow \mathcal{S}$ which assigns to each cell of the array $\mathcal{L}$ a state from $\mathcal{S}$. We denoted with q _t the configuration of a cellular automata at time t; in particular $q_t = [s_0,s_1,\ldots,s_n] \in \mathcal{S}^{n}$ (16) where n is the number of cells of $\mathcal{L}$. Given an initial configuration q ₀, the evolution of an automaton is represented by a sequence of configurations $q_0 \rightarrow q_1 \rightarrow q _ 2 \rightarrow \cdots \rightarrow q_t$. A deterministic finite cellular automaton eventually falls into a cycle (with period p > 1) or a fixed point (p = 1):

$$\begin{aligned} & q_t \rightarrow q_{t+1} \rightarrow q_{t+2} \rightarrow \cdots \rightarrow q_{t+p}\\ & q_{t} = q_{t+p};\, q_{t+1} =q_{t+p+1};\ldots; q_{t+p} =q_{t+2p} \end{aligned} $$

We defined two constant configurations $\overline{0}$ and $\overline{1}$ as: $\overline{0} = [0,0,\ldots,0] \in \mathcal{S}^{n}; \,\, \overline{1} = [1,1,\ldots,1] \in \mathcal{S}^{n}$.

4 1nCA rules classification

In the following section a classification of the 1nCA Rules is presented. A central issue in the theory of cellular automata is the classification, i.e. understanding how cellular automata can be meaningfully grouped according to their structure and behavior. There are mainly two approach for the classification of the cellular automata: the direct way, called Phenotypic Classification, to classified cellular automata is to observe their behavior through the spatial-temporal patterns they generates out of several random initial conditions, and then to use statistical metrics to quantify the observed behavior (Li et al. 1990). Another approach, called Genotypic Classification, is based on the analysis of the automaton transition rules.

There are several works (e.g., Gutowitz et al. 1987; Li and Packard 1990; Sutner 1990; Wolfram 1983; Wuensche 1999) focusing on the classification of the one dimensional cellular automata and in particular on the Elementary Cellular Automata. In this section we present an approach of genotypic classification applied to the 1nCA. The idea of a genotypic classification of cellular automata is to divide a population of automata into groups according to the intrinsic properties of the rules. The aim is that some features of the cellular automata behaviors are predictable on the basis of a genotypic classification.

4.1 Totalistic rules

A cellular automaton is called totalistic if the value of a cell depends only on the sum of the values of its neighbors at the previous time step, and not on their individual values (Wolfram 1983). Therefore, half of the possible rules for 1nCA are totalistic. The sum n of the neighborhood cells is computed $n = c_{i}+n_{c_{i}}^{(t)}$ and 0 ≤ n ≤ 2. The following rules are totalistic:

Rule 0▵	f(n) = 0
Rule 1▵	$f(n) = \left\{ \begin{array}{ll} 1 & \hbox{ if } n = 0 \\ 0 & \hbox{ if } n = 1 \\ 0 & \hbox{ if } n = 2 \\ \end{array} \right.$
Rule 6▵	$f(n) = \left\{ \begin{array}{ll} 0 & \hbox{ if } n = 0 \\ 1 & \hbox{ if } n = 1 \\ 0 & \hbox{ if } n = 2 \\ \end{array} \right.$
Rule 7▵	$f(n) = \left\{ \begin{array}{ll} 1 & \hbox{ if } n = 0 \\ 1 & \hbox{ if } n = 1 \\ 0 & \hbox{ if } n = 2 \\ \end{array} \right.$
Rule 8▵	$f(n) = \left\{ \begin{array}{ll} 0 & \hbox{ if } n = 0 \\ 0 & \hbox{ if } n = 1 \\ 1 & \hbox{ if } n = 2 \\ \end{array} \right.$
Rule 9▵	$f(n) = \left\{ \begin{array}{ll} 1 & \hbox{ if } n = 0 \\ 0 & \hbox{ if } n = 1 \\ 1 & \hbox{ if } n = 2 \\ \end{array} \right.$
Rule 14▵	$f(n) = \left\{ \begin{array}{ll} 0 & \hbox{ if } n = 0 \\ 1 & \hbox{ if } n = 1 \\ 1 & \hbox{ if } n = 2 \\ \end{array} \right.$
Rule 15▵	f(n) = 1

4.2 Neighbor-independent and self-independent

A rule is Neighbor-Independent if the value of a cell depends only on its own previous value and not on the value of the neighbors. Formally, a rule is Neighbor-Independent if $\forall s \in \mathcal{S}, f(s, 0) = f(s, 1)$ so, according to the definition of the transition function, a rule is Neighbor-Independent if β₀ = β₁, β₂ = β₃

A rule is Self-Independent if the value of a cell depends only on the value of the neighbors and not on its own previous value. Formally, a rule is Self-Independent if $\forall s \in \mathcal{S}, f(0, s) = f(1, s)$ so, according to the definition of the transition function, a rule is Self-Independent if β₀ = β₂, β₁ = β₃.

According to this criterion the 1nCA rules can therefore be characterized as follows:

• Neighbor-Independent rules: Rule 0▵, Rule 3▵, Rule 12▵, Rule 15▵;

• Self-independent rules: Rule 0▵, Rule 5▵, Rule 10▵, Rule 15▵.

4.3 λ-Parameter

An even cruder piece of information about a rule is the number of non-quiescent outputs in a rule-table. For the 1nCA this parameter is equal to the number of β parameters that are equal to one and it can be calculated as $c =\sum\nolimits_{i=0}^{3} \beta_{i}$

Langton (1990) proposed the so called λ-parameter as an order-chaos parameter for CA. This parameter measures the density of non-quiescent (not zero) outputs in a rule-table. For the 1nCA the λ-parameter can be calculated as: $\lambda = {{c}\over {k^n}} = {{1}\over {4}} \sum\nolimits_{i=0}^{3} \beta_{i}$ where k is the number of states and n is the neighborhood size. λ varies between 0 (order) to 0.5 (chaos) to 1 (order). As λ is increased from 0 to 0.5 (or decreased from 1 to 0.5), the automata move from having the most homogeneous rule tables to having the most heterogeneous.

Langton presented evidence that there is some correlation between the λ parameter and the behavior of an “average” Cellular Automata on an “average” initial configuration (Langton 1990): the behavior was characterized in terms of quantities such as single-site entropy, two-site mutual information, difference-pattern spreading rate, and average transient length. Generally the correlation is quite good for very low and very high λ values, which predict fixed-point or short-period behavior. However, for intermediate λ values, there is a large degree of variation in behavior (Mitchell et al. 1993).

The values of the λ parameter for all the 1nCA rules are shown in Table 1.

Table 1 The 1nCA rules characterized according to the λ parameter

4.4 Sensitivity

Binder (1993, 1994) proposed the sensitivity parameter μ, motivated by the observation that the Wolfram classes are characterized by its sensitivity to changes in the state of a unique cell of the neighborhood of the transition rule.

Sensitivity is defined as the number of changes in the outputs of the transition rule, caused by changing the state of each cell of the neighborhood, one cell at a time, over all possible neighborhoods of the rule being considered: $\mu = {{1}\over {nm}} \sum\nolimits_{n} \sum\nolimits_{j = 1}^{m} {{\delta f}\over {\delta s_j}}$ where m is the number of cells in the neighborhood and n is the number of possible neighborhoods in the rule table. For 1nCA, m = 2, and n = 2^m = 4. The Boolean derivate for Cellular Automata (Vichniac 1990) ${{\delta f}\over {\delta s_j}}$ is equal to 1 if $f(s_1, \ldots, s_j, \ldots) \neq f(s_1,\ldots, \neg s_j, \ldots)$, otherwise is equal to 0.

The sensitivity parameter takes on three different values: 0, 0.5, and 1. The sensitivity parameter helps to relatively discriminate null and chaotic behaviors: the null behavior happens in rules with low sensitivity and the chaotic behavior happens in rules with high sensitivity. Fixed-point and periodic behaviors are concentrated around 0.5.

The value of the sensitivity parameter for the 1nCA rules is presented in Table 2.

Table 2 The values of the sensitivity parameter for the 1nCA rules

4.5 Rule density

The rule density is another very simple parameter introduced to describe rules behavior. The rule density, Rρ, is computed as $R\rho = (\lambda - {{1}\over {2}} ) 2^{(\beta_3-\beta_0)} + \displaystyle{{1}\over {2}}.$

Roughly speaking, rule density indicates the average fraction of sites whose value is one in the rule dynamic evolution. The rule density value is comprised between zero and one. A value of zero indicates that a rule converges (for most of the initial configurations) to zero state in all the cells, a value of one indicates a convergence to one. The rule density value for the 1nCA rules is shown in Table 3.

Table 3 The values of the rule density for all the rules

4.6 Rules symmetries

One mean of verification of the consistence of the rule density parameter (and also the other parameters) is the use of symmetries: if two rules are conjugate, the rule density of one rule is equals to 1 − Rρ of the other rule.

In Fatès (2003) the author defines the reflected, conjugate and reflected conjugate symmetries for the Elementary Cellular Automata. The only possible symmetry for the 1nCA is when f ^*, the conjugate rule of f, is defined as

$$ \forall(c_i,n_{c_i}) \in {\mathcal{S}}^{2} , f^{*}(c_i,n_{c_i}) = f(\neg c_l, \neg n_{c_i}) $$

where $\neg$ denotes the operation of changing the zeros into ones and ones into zeros. The β^* parameters of the conjugate rule are defined as $\beta^{*}_{3} = \neg \beta_0; \, \beta^{*}_{2} = \neg \beta_{1}; \, \beta^{*}_{1} = \neg \beta_{2}; \, \beta^{*}_{0} = \neg \beta_{3}$.

We identified 6 classes of rules, shown in Table 4, according to the symmetries: we can group in one class all the rules that are symmetric (reflected, conjugated or reflected conjugated). The classes are named according to the lowest member index. Each class is formed by totalistic or non-totalistic rules.

Table 4 The rules divided according to the symmetries

This kind of classification of the 1nCA is important because we can restrict the study of the dynamic behavior to only one member of each class and the behavior of the other members can be simply inferred according to the symmetric relations.

5 Effects of asynchronicity in 1nCA

In this section we present the effects of several relevant update schemes on 1nCA automata dynamic evolutions. In Fig. 9 the time evolutions of all the 16 rules according with synchronous update scheme and periodic boundaries conditions, starting from an initial random configuration of 60 cells.

Fig. 9

60 steps of the time evolution of all the 16 1nCA with the default synchronous update scheme and periodic boundaries conditions starting from an initial random configuration of 60 cells

We tested the following update schemes on all the 1nCA rules; more precisely, we analyzed the behavior of representatives of the symmetry classes identified in Sect. 4.6:

• Synchronous

• Random cyclic

• Equal frequency clocked

• Random order

• Random independent

In the following section the outcomes of this analysis will be shown for rules belonging to rules of class 6▵T, given their particular sensitiveness to the choice of a different update scheme and to the significant difference in the overall system dynamics. A summary of the results of the overall analysis will be given in Sect. 5.2.

5.1 Class 6▵T

This section describes an analysis of the dynamic evolution of 1nCA belonging to the Class 6▵. The rules of this class are Rule 6▵ (Rρ = 0.5, λ = 0.5,  μ = 1) and Rule 9▵ (Rρ = 0.5, λ = 0.5,  μ = 1).

The dynamic behaviors of the Rule 6▵ using different update schemes are shown in Fig. 10. The rules of this class are Chaotic: these rules are characterized by the exponential divergence of its cycle length with the system size, and for the instability with respect to perturbations. If the number of cells is finite, for the Synchronous, Random Cyclic, and Equal Frequency Clocked schemes, the evolution eventually falls into a cycle (with period p > 1) or a fixed point (p = 1). The configuration $\overline{0}$ is the fixed point of the Rule 6▵, the configuration $\overline{1}$ is the fixed point of the Rule 9▵. These configurations are fixed points also using the Random update schemes.

Fig. 10

Time space diagrams of Rule 6▵ using different update schemes starting from a random initial configuration

Changing update scheme has dramatic effect on the rule of this class. As shown in Fig. 11, with the Synchronous update scheme, the Rule 6▵ produces a dynamic evolution similar to the Sierpinski Triangle fractal. This typical shape is not present with any of the other update schemes.

Fig. 11

Time space diagrams of Rule 6▵ using different update schemes starting from a single seed

Moreover if the automaton has periodic boundaries conditions and the number of cells is a power of two, starting from an initial configuration, the evolution of the synchronous automata eventually reaches the fixed point. The automata with the other update schemes does not present this behavior.

5.2 Summary of effects of asynchronicity in 1nCA

We can classify the 1nCA rules according to the impact of the choice of a different update schemes on the dynamic evolution of the model. Comparing the dynamic behavior of the same automata adopting the synchronous update scheme and a different asynchronous update scheme, we identified the following four classes of asynchrony influence:

• AS1: not influenced by the update schemes, the dynamic behavior does not change varying the update scheme;

• AS2: the Random Independent update scheme perturbs the dynamic behavior;

• AS3: the Random Independent and Random Order update schemes perturb the dynamic behavior;

• AS4: any asynchronous update scheme perturbs the dynamic behavior.

The 1nCA rules can be classified into the above categories as shown in Table 5: the table also reports the rule classification according to existing approaches [and more precisely Wolfram’s and Li and Packard’s (1990) classifications], as well as to other classifications introduced in Sect. 4.

Table 5 Summary of 1nCA rules classification according both to the

6 Conclusions

The paper has presented a discussion on asynchronicity in CA models, comparing different types of update scheme and proposing an ontology to classify them. The implications of the different update schemes have been presented by introducing a very simple CA based model and testing it adopting different update schemes. Future developments of this work, in the vein of Fatès and Morvan (2005), are aimed at evaluating the possibility to define asynchronous models in which some global dynamic properties are preserved even adopting different asynchronous update schemes.