Olivier Bouré

Nazim Fatès

Vincent Chevrier
email: vincent.chevrier@loria.fr

First steps on asynchronous lattice-gas models with an application to a swarming rule

Keywords: Asynchronous cellular automata, Lattice-Gas cellular automata, Robustness, Swarming behaviour

Lattice-gas cellular automata are often considered as a particular case of cellular automata in which additional constraints apply, such as conservation or spatial exclusion of particles. But what about their updating? How to deal with non-perfect synchrony? Novel definitions of asynchronism are proposed that respect the specificity of lattice-gas models. These definitions are then applied to a well-known swarming rule in order to explore the robustness of the model to perturbations of its updating.

Introduction

In the field of discrete dynamical systems, cellular automata (CA) are widely used as a tool for the simulation of natural phenomena and as a model of parallel computing. Their discrete and spatially-extended structure makes them a computationally simple model yet capable of displaying a wide range of complex behaviours. While initial studies only considered a simultaneous updating of all components, recent years have seen an increasing interest in asynchronous CA models, where the perfect synchrony hypothesis is relaxed. We are here particularly interested in robustness, which characterises the stability of the behaviour when external disturbances and structural changes are applied. In the case of asynchronism, robustness boils down to exploring how much of the CA behaviour is related to the synchronous scheme, and how much comes intrinsically from the individual rule [START_REF] Ingerson | Structure in asynchronous cellular automata[END_REF]. Thus, we observed in previous works a variety of behaviours that arise from different updating schemes, including phase transitions [START_REF] Bouré | Robustness of Cellular Automata in the Light of Asynchronous Information Transmission[END_REF][START_REF] Fatès | An experimental study of robustness to asynchronism for elementary cellular automata[END_REF].

In particular, studies on asynchronous CA have revealed the existence of synchrony-dependent behaviours we call synchronous singularities, that is, behaviours which stability depends on the synchronicity of the model. Examples include the periodic patterns of the Game of Life [START_REF] Blok | Synchronous versus asynchronous updating in the "Game of Life[END_REF][START_REF] Fatès | Does Life resist asynchrony?[END_REF], of several Elementary Cellular Automata [START_REF] Fatès | An experimental study of robustness to asynchronism for elementary cellular automata[END_REF], or even the spatially-extended Prisoner's Dilemma [START_REF] Grilo | Effects of asynchronism on evolutionary games[END_REF].

I P

Figure 1: Synchronous singularity in a lattice-gas cellular automaton. A black triangle represents one particle present in a channel, and white an empty channel.

Considering those examples, one may wonder whether such observations can be only made in systems with an ad hoc deterministic transition rule or whether it can occur for models of natural phenomena.

Our aim here is to tackle the robustness question in the scope of lattice-gas models, in which particles travel through the lattice. As an introductionary example, consider the following pattern uncovered in a previous work [START_REF] Bouré | Observation of novel patterns in a stressed lattice-gas model of swarming[END_REF]: particles are displaced according to a synchronous updating scheme which consists of the successive application of two rules, the interaction step (I) -which reorganises the particles within a cell to maximise their alignment with the particles of the neighbours -and the propagation step (P) -which displaces particles towards the corresponding neighbours. Paradoxically, in this pattern particles are all opposing the directions of their direct neighbours, in spite of the alignmentfavouring local rule (see Fig. 1 and more details in Sec. 3).

A step-by-step look at the evolution of this pattern may let us think that this behaviour requires a deterministic updating rule. However, what is outstanding is that it has been observed to self-organise (a) with a stochastic local rule, (b) from a random initial configuration. Thus the question: if such a pattern can form outside of a deterministic model, how is it related to the perfect synchrony of the system? And how can we question this property in lattice-gas models in order to probe the robustness to asynchronism?

In Sec. 2, we confront the notion of asynchronism to the constraints and hypotheses of lattice-gas cellular automata and propose several definitions of an asynchronous updating scheme. In Sec. 3, we precise further the individual rules considered for our model and compare the observed patterns in the synchronous and asynchronous versions. Finally in Sec. 4, we briefly discuss on the role of asynchronism in discrete dynamical systems, based on our definitions and experimental results.

Defining asynchronous lattice-gas cellular automata

There exist a wide range of interpretations and definitions given to asynchronism, and even more diverse resulting behaviours (see for example [START_REF] Bandini | An analysis of different types and effects of asynchronicity in cellular automata update schemes[END_REF][START_REF] Bouré | Robustness of Cellular Automata in the Light of Asynchronous Information Transmission[END_REF] and ref. therein). The problem we are tackling here is that the system we want to "make asynchronous" is a lattice-gas cellular automaton which, in spite of its compatibility with the classical CA definition, includes additional hypotheses that may not be conserved when changing the updating scheme. Let us now present how we tackle this problem formally.

Definition of lattice-gas cellular automata

The lattice-gas cellular automaton (LGCA) we are interested in is a particular CA, where:

• the cellular space L = {Z/L•Z} 2 is a 2-dimensional square lattice of length L with periodic boundary conditions.

• the neighbourhood (n i ) i ∈[ [START_REF] Bandini | An analysis of different types and effects of asynchronicity in cellular automata update schemes[END_REF][START_REF] Bouré | Robustness of Cellular Automata in the Light of Asynchronous Information Transmission[END_REF]] = {(1, 0); (0, 1); (-1, 0); (0, -1)} associates to a cell c ∈ L the set of its 4 nearest neighbours.

In a LGCA, each cell is connected to its neighbours via channels through which particles can travel. Cell configurations x c = (x i (c)) i ∈[ [START_REF] Bandini | An analysis of different types and effects of asynchronicity in cellular automata update schemes[END_REF][START_REF] Bouré | Robustness of Cellular Automata in the Light of Asynchronous Information Transmission[END_REF]] are therefore represented as a vector of the numbers of particles contained by each of its channels x i (c) ∈ N. The dynamics of LGCA is determined by the successive application of two global transitions:

1. The interaction step reorganises particles within cells according to a transition function f I , which applies to the configuration of a cell and its neighbourhood:

∀c ∈ L, x I c = f I ( x c , x c+n1 , . . . , x c+n4 ). (1)
2. The propagation step displaces particles from the channels of a cell to the corresponding neighbours:

∀c ∈ L, ∀i ∈ [[1, 4]], x P i (c) = x I i (c -n i ). (2)
In addition, we consider two fundamental constraints which we want to keep valid under an asynchronous updating scheme: the particle exclusion -channels may contain at most one particle, and are therefore considered as either empty (state 0) or full (1) -and the particle conservation -particles must always be conserved when they interact and propagate1 .

Which asynchronism?

For this work, we will consider α-synchronism [START_REF] Fatès | An experimental study of robustness to asynchronism for elementary cellular automata[END_REF][START_REF] Bouré | Robustness of Cellular Automata in the Light of Asynchronous Information Transmission[END_REF] which follows the general definition: at any time step, each component updates according to the regular transition function with probability α, or remains unchanged using the identity function with probability 1 -α. This updating scheme provides us with a useful control parameter, the synchrony rate α, allowing for a continuous control of the updating scheme from evolution in perfect synchrony (α = 1) to quasi-sequential updates (α → 0). The global transition function of LGCA from a time t to t + 1 is constituted of two steps, interaction and propagation, applied successively to all cells. When we want to apply asynchronism, we need to properly define the meaning of "updating" and "remaining unchanged" in terms of computation. Does asynchronism apply to the sole interaction? The propagation? Shall we consider these transitions as correlated, independent?

To address this issue, we propose as a starting point three possible implementations of asynchronism:

(1) Asynchronous interaction : the interaction is applied with a probability α I , called the interaction rate. The propagation is always applied.

(2) Asynchronous propagation : the interaction is always applied, but the propagation is applied with a probability α P , called the propagation rate.

(3) Correlated interaction and propagation : for each cell, interaction and propagation are both applied with a probability α C , otherwise none of them is applied.

However, if the asynchronous interaction (1) can be implemented without problem as the interaction rule itself is particle-conserving, desynchronising the propagation (2, 3) is not a straightforward operation and requires further reflexion.

Conserving particles during the propagation.

Let us first consider the case where asynchronous propagation is simply determined as the application of the transition rule with probability α P , and identity function with probability 1 -α P . In LGCA models, there is no actual means for a given cell to know whether its neighbours are selected for update or not. This is problematic as we need this type of information to decide whether to propagate the state of a channel or not (see Fig. 2-b and-c).

There exist several model adaptations that can solve this issue: for instance, by adding specific states which keep cells synchronized [START_REF] Peper | Self-timed cellular automata and their computational ability[END_REF] or by using additional steps to perform validity checks (e.g. transactional CA [START_REF] Spicher | From reactive multiagents models to cellular automata -illustration on a diffusion-limited aggregation model[END_REF]). Similarly, our proposition here consists in modifying the point of view of the asynchronous propagation function by considering no longer the cells but the channels as the base components of the system. We first select randomly the cells which are to be updated, and then determine from non-selected cells which channels are free, and thus updated, and which are blocked and remaining unchanged. We now specify the formal definitions of asynchronous interaction and propagation using selection functions. (b,c) the asynchronous case without the particle-conserving changes and (d,e) our proposition for an asynchronous propagation.

Definition of an asynchronous

LGCA

2.3.1 Interaction step.
We introduce a selection function ∆ I : N → P(L) which associates to each time t the subset of cells to be updated during the interaction step, where each cell has a probability α I to be selected. The interaction transition function becomes ∀t ∈ N, ∀c ∈ L, N = {n 1 , . . . , n 4 }:

x I c = f ∆I ( x c , x c+n1 , . . . , x c+n4 ) = f I (. . .) if c ∈ ∆ I (t) x c otherwise. (3)
When α I = 0, the system is ballistic, i.e. particles always go straight.

Propagation step.

First, we need to determine which cells update, and which remain unchanged.

Similarly to asynchronous interaction, we introduce a selection function ∆ P : N → P(L) which returns for time t the subset of cells to be updated during the propagation step, where each cell has a probability α P to be selected. In addition, we define B t ⊂ [ [START_REF] Bandini | An analysis of different types and effects of asynchronicity in cellular automata update schemes[END_REF][START_REF] Bouré | Robustness of Cellular Automata in the Light of Asynchronous Information Transmission[END_REF]] × L as the set of blocked channels, which will remain unchanged between times t and t + 1. To build this set, we state that a channel (i, c) t (channel i of cell c at time t) is blocked if it contains a particle (x t i (c) > 0), and if one of the two conditions is true: (C1) its containing cell c is not selected for update, or (C2) its destination channel is blocked. We thus have:

(i, c) t ∈ B t if x t i (c) > 0 and      c / ∈ ∆ P (t) (C1) or (i, c + n i ) t ∈ B t (C2)
The construction of B t describes a general relation between particles. It can be implemented with a recursive algorithm: once a channel is blocked because of condition (C1), the chain of the channels that "point" to this one must be also blocked if they contain a particle because of condition (C2) (see Fig. 2-e). The propagation transition function therefore becomes:

x P i (c) =      x I i (c) if (i, c) ∈ B t 0 if (i, c) / ∈ B t and (i, c -n i ) ∈ B t x I i (c -n i ) otherwise. (4)
When α P = 0, the particles are never propagated and thus never leave their cell.

Observation on a swarming rule

The model of swarming we present here is borrowed from a compilation of biological models by Deutsch et al. [6, ch. 8]. It describes a probabilistic swarming interaction rule in which the particles of a cell tend to align themselves with the neighbourhood predominant directions. The probability for a given cell configuration x c to reorganise into x I c is given by:

P ( x c → x I c ) = 1 Z exp σ • J c ( x I ) • D c ( x) • δ( x c , x I c ) (5)
where:

• Z is the normalisation factor, so that x I c P ( x c → x I c ) = 1.

• σ ∈ Z is the alignment sensitivity.

• J c ( x I ) is the flux in cell c, the resulting vector of particle directions.

• D c ( x) is the director field, the sum of cell x c neighbours' flux.

• δ( x c , x I c ) = 1 if cell configurations x c and x I c have same number of particles, 0 otherwise. This ensures conservation of particles.

Starting from a random initial configuration of density ρ, where ρ is the probability for each channel to contain a particle, we need only to set the parameter to determine the local interaction rule. This limits the parametric space to the σ/ρ plane, allowing for a complete exploration of the different qualitative behaviours that the model may display.

Recapitulation of the synchronous behaviour

The main interest of the swarming model is that, in spite of a simple and stochastic interaction rule, a variety of qualitatively different behaviours can arise. In particular, it has been previously established that, using the two control parameters σ and ρ, two phases may emerge, chaotic and organised [START_REF] Deutsch | Cellular Automaton Modeling of Biological Pattern Formation[END_REF].

In recent work, we reported that the organised phase can display several stable patterns of global particle organisation [START_REF] Bouré | Observation of novel patterns in a stressed lattice-gas model of swarming[END_REF] (see Fig. 3):

Checkerboard pattern (CB) : local groups of anti-aligned particles. Typically occurs for high densities (typically ρ ≈ 0.5).

Diagonal stripe pattern (DS) : a traveling compact diagonal shape of particles in two orthogonal directions, that loops over the lattice boundaries.

Clouds pattern (CL) : traveling competitive groups of aligned particles. Typically occurs for a high sensitivity (σ ≈ 3 -4).

It is interesting to note that these behaviours have been observed for systems of limited size and time, and can therefore be considered as metastable attraction basins. This means that once a behaviour is reached, the system will conserve it until random fluctuations make the system "escape" this behaviour. We now apply the different updating schemes to the system and try to determine whether these patterns are robust to perturbations of the updating. More particularly we are interested in whether their appearance depend on perfect synchrony.

Exploration of the asynchronous behaviour

As a preliminary study, we now propose to consider each of the three patterns independently, by setting the system in adequate initial condition of size (L = 20) and iterating the system for a large number of steps (t = 5000). We then observe if the expected pattern appears, and compare the results for different values of the different synchrony rates (α I , α P , α C ).

Asynchronous interaction.

Two observations can be made (see Fig. 4-a):

1. The checkerboard pattern is very sensitive to asynchronism. Indeed, a small but apparently not infinitesimal amount of asynchronism (α I ≈ 0.95) is sufficient to switch the behaviour to a diagonal stripe pattern which covers the lattice entirely.

2. For the diagonal stripe and the clouds patterns, as long as the amount of asynchronism remains small, the only effect on the pattern is to introduce additional noise. As soon as a critical value α I is reached, the clouds pattern becomes a diagonal stripe, and the diagonal strips becomes random.

Asynchronous propagation.

The three tested patterns displayed a sudden change of behaviour for a small amount of asynchronism (see Fig. 4-b).

1. The checkerboard pattern is very unstable and shifts to a global consensus on the directions of propagation. However, for higher the value of α P , it is possible for the pattern to "survive" for a few time steps.

2. The diagonal stripe still appears for high α P but is soon replaced by "semirandom" patterns, where some order regularly appears in some parts of the lattice and disappears, but never stabilises.

3. The clouds pattern is destabilised and transforms into one or several vertical or horizontal stripes of aligned particles.

These observations suggest a destructive effect of asynchronous propagation on all behaviours, even for a high propagation rate α P ≈ 0.95. However, this observation does not seem to hold for infinitesimal values of asynchrony (α P = 1 -), which let us think that our patterns have a minimal degree of robustness to asynchronous propagation.

Correlated interaction and propagation.

Similar experiments have been applied to the correlated updating scheme. The resulting behaviour is a mix of asynchronous interaction and asynchronous propagation:

1. For higher values of the synchronism rate (α C ≈ 0.95), the behaviour follows the sudden changes observed in the asynchronous propagation.

2. For lower values (α C ≈ 0.5), the swarming and identity interaction rules become equiprobable and, as particles do not gather in clusters any more, the system enters a random phase.

Considering how differently asynchronous interaction and asynchronous propagation effect on the system dynamics, and the synchrony rates for those changes were observed, this result is somehow "expected": the behaviour changes correspond more or less to the changes observed for each type of asynchronism.

Synthesis of the experiments.

Observations on the swarming model, which was thought rather robust in the first place due to the stochastic rule and self-organisation phenomena, highlighted the dependence between the type of asynchronism applied to the system and the stability of each pattern. For instance, we observed that there exist (1) differences between patterns in their robustness to asynchronism (e.g. diagonal stripe versus checkerboard under asynchronous interaction) and (2) differences between types of asynchronism in their effects on the system's behaviour (e.g. diagonal stripe under asynchronous interaction and propagation). Moreover, we ask whether there exists a fundamental change of behaviour between perfect synchrony (α = 1) and quasi-synchrony (α = 1 -). Indeed, as our system is stochastic, it is difficult to determine experimentally whether patterns such as the checkerboard can be considered as "synchronous singularities". For now, additional experiments must be conducted in deeper details, as our simulations were limited in space and time, in order to give a proper estimation of the robustness of the behaviour of this model.

Discussion

This paper presented a first definition of an asynchronous LGCA, which intends to extract from classical CA the idea of questioning the perfect synchrony, and adapt it to the definition and hypotheses of a lattice-gas model of swarming.

Although cellular automata and lattice-gas models share strong resemblances, the introduction of asynchronism managed to reveal an intrinsic difference. Indeed, cellular automata are based on cells that are updated according to the observation of their neighbours' state, whereas lattice-gas models intend to capture a transport of information between cells.

From this example we learned that a naive expression of asynchronismfor instance reproducing the classical definition from cellular automata -could compromise the constraints of the lattice-gas model: the conservation and spatial exclusion of particles imposed us to change the modelling point of view and consider channels as the base components of the updating scheme. However, many issues remain unexplored. For instance, according to our definitions, a single particle can block an entire array of particles, which may contradict the idea of locality of events in spatially-distributed computing.

The next step of this approach consists in building a model where particles are considered as autonomous agents, with their own perception and decision process.

Figure 2 :

 2 Figure 2: Representation of the propagation step along one channel direction in a sample of five cells, for different updating schemes and situations of particles. Darker cells are not selected for update. (a) is the synchronous classical case,(b,c) the asynchronous case without the particle-conserving changes and (d,e) our proposition for an asynchronous propagation.

Figure 3 :

 3 Figure 3: Spatial distribution of the different patterns in the sensitivity-density parametric plane.

3 Figure 4 :

 34 Figure 4: Evolution of the main patterns for different interaction (propagation) rate values α I (α P , respectively). Configuations are obtained from random initial configurations run for 5000 steps for typical values of σ and ρ (DS: {σ = 1.5; ρ = 0.2}, CB: {σ = 1.5; ρ = 0.45}, CL: {σ = 4; ρ = 0.2}). The simulations and visualisations are realised with FiatLux, a CA simulator in Java (http: //fiatlux.loria.fr). 9

Note that our particle-oriented interpretation of the system resembles Totally Asymmetric Simple Exclusion Processes [?].


Olivier Bouré
email: olivier.boure@loria.fr

Nazim Fatès
email: nazim.fates@loria.fr

Vincent Chevrier
email: vincent.chevrier@loria.fr

Probing robustness of cellular automata through variations of asynchronous updating

Keywords: Asynchronous cellular automata, robustness, discrete dynamical systems, phase transitions, directed percolation

Typically viewed as a deterministic model of spatial computing, cellular automata are here considered as a collective system subject to the noise inherent to natural computing. The classical updating scheme is replaced by stochastic versions which either randomly update cells or disrupt the cell-to-cell transmission of information. We then use the novel updating schemes to probe the behaviour of Elementary Cellular Automata, and observe a wide variety of results. We study these behaviours in the scope of macroscopic statistical phenomena and microscopic analysis. Finally, we discuss the possibility to use updating schemes to probe the robustness of complex systems.

Introduction

Cellular automata (CA) are known as a model of computation based on the parallel evolution of cells according to their neighbourhood state. Originating from the study of self-replicating systems as introduced by von Neumann (1966), they are considered as an alternative to sequential computing models. Indeed, their spatially-extended and yet simple structure make them a suitable model for parallel computing and simulations of natural phenomena.

In their original form they are deterministic and synchronously evolved, that is, all components of the system are updated simultaneously. However, as natural computing supposes the use of non-classical methods involving a number of interacting components, the determinism of the model is somewhat incompatible with the presence of noise. This raises the question of the robustness of cellular automata, that is, the stability of the behaviour despite external disturbances, such as an asynchronous update or errors in transitions or interactions between cells. 1 This question was initially discussed by [START_REF] Ingerson | Structure in asynchronous cellular automata[END_REF] who "wanted to estimate how much of the behaviour of cellular automata comes from synchronous modeling and how much is intrinsic to the iteration process". For that purpose, they questioned the perfect synchrony hypothesis by randomising the transition function of Elementary Cellular Automata, and observed behavioural changes. From their observations they concluded that the updating scheme plays a fundamental role in the behaviour of the system. Since then, authors have tackled the question of whether cellular automata are robust to non-synchronous updating, either by keeping the same individual rule or adding adapted constructs [START_REF] Peper | Selftimed cellular automata and their computational ability[END_REF]. For instance, [START_REF] Grilo | Effects of asynchronism on evolutionary games[END_REF] investigated behaviour changes for asynchronous symmetric 2-player evolutionary games, such as the Prisoner's Dilemma. Similarly, models of cellular automata have been studied under asynchronous updating, such as Elementary Cellular Automata (Fatès andMorvan 2005, Regnault 2008) or the Game of Life [START_REF] Blok | Synchronous versus asynchronous updating in the "Game of Life[END_REF]Bergersen 1999, Fatès 2010) and revealed qualitatively different behaviours.

The definitions of asynchronous cellular automata used so far have mainly focused on either randomising the transition function or updating cells sequentially (Bandini et al. 2010a). But as asynchronism is first defined as a negation of synchronicity, several interpretations remain possible. Our approach, which shares the main ideas from the fields of spatially-extended computing (Gouaïch et al. 2005, Ackley and[START_REF] Ackley | Homeostatic architecture for robust spatial computing[END_REF] and autonomous agents (Bandini et al. 2010b), intends to consider cellular automata as a collective system where cells are autonomous components and their interactions are subject to perturbations. Instead of questioning whether cells are updated at each time step, we represent explicitly the perception by the cells of their neighbourhood, and consider failures in the cell-to-cell transmission of information.

Questioning the perfect synchrony hypothesis. Let us first consider an illustrative example: two planes are flying in opposing directions and at successive time steps must decide to go up or down in order to avoid collision. The decision function, the same for both planes, is deterministic: if the opposing plane goes down, then go up and vice versa. Here three types of updating schemes are considered (see Fig. 1):

(a) The perfect synchrony assumes that planes update their state simultaneously at each time step. An initial configuration with both planes going in the same direction inevitably results in a periodic cycle and a crash.

(b) However, when planes update their state with a given probability, the system finds a stable situation after a few time steps. This updating scheme is called asynchronous update.

(c) This time, planes do update their state at the same time, but the updated state of one plane is not always transmitted to the other. When one plane fails to transmit its new state, the system stabilises. We call this novel type of updating scheme asynchronous information transmission. As one can deduce from this simple example, both asynchronous updating schemes alter the long-term behaviour of the system, as they directly prevent the stability of the crash scenario of the synchronous case. However, their intrinsic difference also suggests that there may exist models which would react differently to each of them. We intend to use these updating schemes to probe cellular automata, that is, to study how each of the different updating schemes influences the behaviour of a set of cellular automata rules.

Asynchronous information transmission in cellular automata.

To study the effects of asynchronous information transmission on cellular automata, we propose a novel updating scheme, extending two features of the classical definition: (1) we extend the state space to take into account the internal state of the cell as well as how it is perceived by the neighbourhood and (2) we describe the updating process of the system in the frame of a cellular cycle, that is, the sequential application of two steps, (a) the local computation of the new state, and (b) the transmission of the updated state to the cells of the neighbourhood.

Extending a previous work [START_REF] Bouré | Robustness of Cellular Automata in the Light of Asynchronous Information Transmission[END_REF], we present a more general definition of asynchronous information transmission and a more complete study of Elementary Cellular Automata. In Sec. 2 we give a general formal definition of asynchronous information transmission for cellular automata. Then, an overview of our observations on asynchronous Elementary Cellular Automata is given in Sec. 3 and in Sec. 4, we present an analysis of phase transitions. Section 5 presents two case studies of a microscopic approach to the study of the effects on two models, which present different reaction depending on the asynchronism. Finally, we discuss our results in Sec. 6.

Asynchronous Cellular Automata

Definition of Cellular Automata

A cellular automaton is a discrete dynamical system defined by (L, Q, N , f ) where :

• L ⊂ Z d is the cellular space, where elements of L represent cells.

• Q is a finite set of states.

• N ⊂ L is a finite set of vectors called the neighbourhood, which associates to a cell the set of its neighbouring cells. N and L are such that for all c ∈ L and for all n ∈ N , the neighbour c + n is in L.

• f is the local transition rule, which defines the next state of a cell according to the state of this cell and the ones of its neighbours.

A configuration x t represents the state of the automaton at time t; it is defined as a function x t : L → Q which maps each cell to a state. Classically, cellular automata are synchronously updated, meaning that at each time the local transition rule is applied simultaneously to all cells. The global transition function is therefore defined as x t+1 = F (x t ), so that, for N = {n 1 , ..., n k }:

∀c ∈ L, x t+1 (c) = f x t (c), x t (c + n 1 ), ..., x t (c + n k ) .
Without loss of generality, we assume that the neighbourhood N does not contain the cell itself. This hypothesis is necessary to explicitly represent the flow of information between a cell and its neighbours. Note that this does not restrict the expressiveness of f since the current state of a cell x t (c) is always a parameter of f , possibly not taken into account in the transition function.

To give a proper definition of asynchronous information transmission, we need to extend the classical framework of cellular automata.

1. The cell update is represented by a two-step cell cycle (see Fig. 2):

• the state update step, where a cell changes its state according to the local transition function and its perception of the neighbourhood.

• the information transmission step, where the cell transmits the updated state to its neighbours.

2. The state space Q must be extended to distinguish:

• the eigenstate, that is, the actual, internal state of a cell in Q,

• a vector of m observation states, that is, m elements of Q that represent how a cell is perceived by its neighbours.

In the frame of this extension of cellular automata, we define three types of updating schemes (see Fig. 3 for schematic representations):

y' y y' R y' L t z' L x' R y' y x z x' z' x R z L x z x' z' y L y R t
Figure 2: Left: schematic representation of the classical update. Right: representation of the update as a cellular cycle, for a cell with two neighbours. A triplet {y L , y, y R } represents a cell with eigenstate y, and its observable states, for each of its neighbours (y L for left cell and y R for right). The classical transition corresponds to y ← f (x, y, z). However, for the cellular cycle, the transition is divided into the update step y ← f (x R , y, z L ) and the transmission step, which performs y L ← y and y R ← y .

α-synchronism (m = 0): at each time step, each cell is updated with a fixed probability α, or else left unchanged (no representation of perception).

β-synchronism (m = 1): each cell is updated at each time step, but the transmission of the new state to the whole neighbourhood is realized with a probability β.

γ-synchronism (m = k): each cell is updated at each time step, but the transmission to each neighbour is realized independently with a probability γ.

As a result, perturbations consist in applying one of the steps of the cell cycle with a probability defined as the synchrony rate. Remark that for the sake of simplicity, α, β and γ denote both the type of asynchronism and the associated synchrony rates.

Formal definition of the updating schemes

α-synchronism. We introduce a selection function ∆ α : N → P(L) which gives for time t the subset of cells to be updated, where each cell has a probability α to be selected. Note that when α = 1 the updating is fully synchronous and the system is deterministic. The global transition function becomes ∀t ∈ N, ∀c ∈ L, N = {n 1 , ..., n k }:

F ∆ (x t (c)) = f (x t (c), x t (c + n 1 ), ..., x t (c + n k )) if c ∈ ∆(t) x t (c) otherwise.
By contrast with asynchronous updating, asynchronous information transmission aims at modelling the disruption of the exchange of information about states between cells. We now give a framework for this new type of asynchronism, modifying the classical definition of cellular automata with adequate extensions.

L, Q, N , f ). First, the state space Q is extended to Q = Q × Q m in order to differentiate for a cell configuration x t (c), its eigenstate e t (c) ∈ Q and a vector of m observation states o t (c) ∈ Q m . Secondly, the transition function f is replaced by f = f tr •f u ,
that is, two functions applied sequentially to represent the actual update and the transmission of the state:

• f u : Q k+1 → Q is the update function; it computes the new eigenstate of a cell based on its eigenstate and the observation state of the neighbours, leaving the observation states unchanged:

f u e o , . o 1 , • • • , . o k = φ(e, o 1 , • • • , o k ) o (1)
where φ : Q × Q k → Q computes the new eigenstate based on the result of the local transition function f and the observation states for each neighbour.

• f tr : Q → Q is the transmission function; it carries out the "propagation" of the eigenstate e t (c) to the neighbourhood: this operation consists of replacing the values of observation states o t (c) of the cell by the eigenstate.

To this end, we introduce a set of random variables (θ t,c i ) t∈N,c∈L,i∈ [[1,m]] which represent the atomic transmissions of the eigenstate e t (c) to the i-th element of o t (c), such that:

∀t ∈ N, ∀c ∈ L, ∀i ∈ [[1, m]], θ t,c i (e, o) =
e with a probability P , o with a probability 1 -P ,

where P is the synchrony rate corresponding to the asynchronisms (α, β, γ).

The transmission function f tr is thus defined, for the configuration (e, o) of a cell c at time t, as a stochastic function such that:

f t,c tr e o =      e θ t,c
1 (e, o 1 ) . . .

θ t,c m (e, o m )      . ( 3
)
We now detail the two implementations of this definition:

β-synchronism. This asynchronism consists in considering perturbations as disruptions of the emission of the eigenstate by a cell. We represent the observation state by a single element of Q (m = 1), which is perceived by all neighbouring cells:

• the state of a cell, for a given configuration x t , is given by

x t (c) = (e t (c), o t (c)), where o t (c) ∈ Q . • φ(e, o 1 , • • • , o k ) = f (e, o 1 , • • • , o k ).
γ-synchronism. This asynchronism consists in considering the disruption of the transmission of a cell's eigenstate to each neighbour independently. As a consequence, the vector of observation states associates an element of Q for each element of the neighbourhood (m = k):

• the state of a cell, for a given configuration x t , is given by x t (c) = (e t (c), o t (c)), where o t (c) ∈ Q k .

• The transition function φ is given by:

φ(e, o 1 , • • • , o k ) = φ   e,    o 1,1 . . . o 1,k    , • • • ,    o k,1 . . . o k,k       = f (e, o 1,1 , • • • , o k,k ),
where o i,i (c) corresponds to the independent transmitted state to cell c from its i-th neighbour.

As we defined them, β-and γ-synchronism differ only in the representation of the observation states. Readers should note that, like α-synchronism, β-and γ-synchronism can be understood as classical probabilistic cellular automata with an extended state space [START_REF] Bouré | Robustness of Cellular Automata in the Light of Asynchronous Information Transmission[END_REF]).

Let us now observe how these updating schemes affect the behaviours of cellular automata using a well-known set of rules.

Preliminary observations

We now apply β-and γ-synchronism to one of the simplest classes of cellular automata, the Elementary Cellular Automata, and compare the resulting behaviours1 to the dynamics of α-synchronism.

Elementary Cellular Automata (ECA). An ECA is a one-dimensional binary cellular automaton with nearest-cell neighbourhood. It is defined with (L, N , {0, 1} , f ) where:

• L = Z/LZ is a 1-dimensional ring of length L,
• N = {-1, +1}, i.e. the left and right neighbours,

• the local transition function f : Q 3 → Q. It is common to designate each ECA by the decimal code W = f (0, 0, 0) • 2 0 + f (0, 0, 1) • 2 1 + ... + f (1, 1, 1) • 2 7
. Through the use of left/right reflexion and 0/1 complementarity, it is possible to narrow down the study of the ECA space to 88 classes, each represented by the rule of smallest number.

In the following, initial conditions are constructed by setting the value of the eigenstates randomly and uniformly in {0, 1}. As we consider the disruption of information transmission as a perturbation, we set the values of the observable states equal to the eigenstate, thus assuming that no error exists at initial time.

Experimental protocol. It is well known that the classification of ECA rules is a difficult problem, due to the richness and the complexity of the encountered behaviours (see e.g. Wolfram classes in [START_REF] Culik | Undecidability of CA classification schemes[END_REF]). Similarly, studies on α-synchronism have suggested that there is no straightforward correlation between Wolfram classes and their robustness to α-synchronism (see [START_REF] Fatès | Asynchronism induces second order phase transitions in elementary cellular automata[END_REF]. As β-and γ-synchronism define new updating mechanisms, they raise the question of whether they have the same effects than α-synchronism. As an analytical prediction of behaviour is a difficult problem [START_REF] Fukś | Orbits of bernoulli measure in asynchronous cellular automata[END_REF], we first decide to probe the entire ECA rule space experimentally2 .

In order to facilitate the comparison of the effects between different asynchronism, we will classify ECA rules according to their response to asynchronism, that is, an observation of the behaviour as a function of the perturbation applied. To estimate the response of ECA, we here use two methods (see Fig. 4 for visualisations):

1. We visually compare the space-time diagrams obtained by displaying the values of eigenstates over a few time steps. This approach provides a good idea on the changes of behaviour, but cannot hold as a formal classification criterion.

ECA 51 synchronous α=0.8 β=0.8 2. We quantify the behaviour using an order parameter, the density, defined as the ratio of cells with eigenstate 1. We give an estimation of the asymptotic density, by letting a system of size L = 2000 evolve for 5000 steps, and then averaging the parameter value for 100 steps.

Results. For the vast majority of rules, neither the space-time diagram nor the density profile allow to qualify any change of behaviour between α-synchronism and the two other types of asynchronism. However, some rules show remarkable changes, as illustrated by the examples of Fig. 4:

• The space-time diagrams of rule ECA 51 (NOT rule) shows a trivial example of a qualitative difference between α-and β-synchronism. Indeed, as the transition function does not actually depend on the state of the neighbourhood, ECA 51 is perfectly robust to asynchronous information transmission.

• For rules like ECA 51 and ECA 57, the initial value of the density parameter is conserved for all values of the synchrony rate. However, this observation is not representative of the behaviour as a quick comparison of their space-time diagrams reveals that it is radically different.

• For rules with a behaviour similar to ECA 45, the density shows a slight difference between α-, β-and γ-synchronism.

• Finally, some rules show a discontinuity in the plot profile of the density, such as for ECA 6, 50, 58, suggesting that a qualitative change of behaviour occurs for a critical value of the synchrony rate. This change is confirmed by the observation of the space-time diagrams (see Fig. 5).

In Tab. 1, we collect rules according to the type of response obtained for the density parameter and divide them into three categories: (a) a brutal change of 3, 4, 9, 12, 19, 22, 33, 35, 36, 44, 45, 46, 54, 62, 72, 76, 104, 108, 110, 122, 132, 152, 164, 172 (c) No observable difference 0, 1,2,5,7,8,10,11,13,14,15,23,24,25,27,28,29,30,32,34,37,40,41,42,43,51,56,57,60,73,74,77,78,90,94,105,126,128,130,136,138,140,142,150,154,156,160,162,168,170,178,184,200,204,232 behaviour occurs for at least one of the asynchronisms, (b) a difference of level or slope can be observed and (c) no difference can be observed. The observation of a qualitative change of behaviour is a strong evidence of non-robustness, and conveniently, it is quantifiable. To clarify further how updating schemes affects cellular automata, we choose to focus on this category and study these discontinuities in the context of statistical physics.

Study of phase transitions

The occurrence of phase transitions is probably one of the most remarkable phenomena that arises in asynchronous cellular automata: in such models, there exists a non-trivial value of the synchrony rate, the critical threshold, which separates two distinct "phases": a passive phase for which the system converges to an homogeneous fixed point of 0s, and an active phase where the system the system does not converge to a fixed point but nevertheless oscillates around a fixed density. In our case, different discontinuities appear depending upon the updating scheme used:

(a) for the rules ECA 18, 26, 50, 106, 146, a phase transition occurs for all three types of asynchronism, (b) for the rules ECA 6, 38, 134, a phase transitions is observed only for α-synchronism, (c) a phase transition can be observed for α-and β-synchronous ECA 58, but not for γ-synchronism.

A first observation is that all these rules show a discontinuity for α-synchronism, but not necessarily for the two others. For the α-synchronous case, these abrupt changes were identified by [START_REF] Fatès | Asynchronism induces second order phase transitions in elementary cellular automata[END_REF] as phase transitions, which belong to the directed percolation (DP) universality class. This means that these models follow the same characteristic power laws at criticality (see [START_REF] Hinrichsen | Nonequilibrium critical phenomena and phase transitions into absorbing states[END_REF]. These rules were then classified into two categories3 : The straight line follows a power law f (t) = K × t -δ with the critical exponent δ = 0.1595. Measures are averaged over 32 automata of size 10000.

• the DP hi class comprises all ECA with a "positive" phase transition: the active phase occurs for high values of the synchrony rate, and the passive phases for lower values. This class is made of ECA 18,26,50,58,106,146.

• the DP low class gathers ECA with a "negative" phase transition: active and passive phases are reversed in order. It is made of ECA 6, 38, 134.

The existence of a correlation between these classes and the rules' response in β-synchronism is an interesting question, which remains as an open problem.

Quantification of the critical behaviour. Because all drastic changes in β-synchronism also belong to the DP hi class, we conjectured that all observed discontinuities are caused by phase transitions which belong to the directed percolation universality class. To verify this hypothesis for β-and γ-synchronism, we reused the same experimental protocol described by [START_REF] Fatès | Asynchronism induces second order phase transitions in elementary cellular automata[END_REF] for αsynchronism:

1. We fix the synchrony rate, start from a random initial configuration and let it evolve for a given number of steps.

2. We monitor the evolution of the density for a long simulation time until we observe a sub-critical or super-critical behavior. In a log-log plot such as Fig. 6, a concave curve occurs for the passive phase and a convex curve for the active phase. As we expect the order parameter to follow a power law K.t -δ near criticality, the curve at critical value should appear as a straight line of slope -δ.

3. We repeat the experiment with a value of the synchrony rate closer to the critical point until a satisfactory precision is reached.

Figure 6 presents the results of this experiment for β-synchronous ECA 50. For this particular example, the asymptotic behaviour at critical threshold follows a power law K.t -δ with δ ∼ 0.1595, which is the characteristic exponent for the directed percolation universality class in 1 + 1 dimensions [START_REF] Hinrichsen | Nonequilibrium critical phenomena and phase transitions into absorbing states[END_REF].

Using successive experiments with different synchrony rates, we measured the critical value for each asynchronism with a precision of 10 -3 . Table 2 lists the values of the critical synchrony rates; all measured values of the critical exponent δ show good evidence of directed percolation.

To sum up, these experiments reveal a strong connection between α-and β-synchronism for the DP hi class, which contrasts with the results obtained for the DP low class and the exception of γ-synchronous ECA 58. This is already an interesting result, as we have identified phenomena that are exclusive to each asynchronism. A potential use of these differences is that they can be used as a "signature" of the updating scheme. In order to understand the origin of these differences, we now propose to study these models at a lower level.

Microscopic approach

In this section, we focus on the study of the local evolution of cells under αand β-synchronous updating schemes, using three examples that represent different responses to asynchronism: ECA 50 for the DP hi class, ECA 6 for the DP low class, and ECA 58 as an exception to the DP hi class. Note that these approaches are not aimed at giving a full proof of the observed behaviour, but rather to give us an insight on how different types of asynchronism may produce different responses.

First case study: ECA 50

ECA 50 is defined by the following transition table: The study of this rule reveals a paradoxal response to α-and β-synchronism: if the evolution of the density parameter suggests that directed percolation phenomena occurs in both cases, a quick inspection of the space-time diagrams over a few time steps clearly shows a radical difference in the local behaviours (see Fig. 4 page 9). This suggests that the local behaviour differs from one asynchronism to the other.

Describing patterns. By looking at the β-synchronous space-time diagrams, we perceive a kind of periodicity in the organisation of states that does not appear for α-synchronism. In particular, configurations divide up in large patterns of cells with consecutive or alternated eigenstates 0 and 1, which appear or disappear with random events:

• The checkerboard region are defined as a group of spatially alternated eigenstates. Under a synchronous scheme they will flip all their states, thus drawing a "checkerboard" over a few time steps (see Fig. 7-a).

• The particles separate checkerboard regions; they are formed by pairs of cells with identical eigenstates (i.e. 00 and 11), which both flip when updated (see Fig. 7-a).

• Occasionally, random anomalies appear, that is, groups of three or more cells with eigenstates 0 that perturbate the regularity of the two previous patterns. Typically, this results in the appearance of "white holes" in the patterns above (Fig. 7-b). When these anomalies include particles, they can displace them spatially (Fig. 7-c) or even annihilate them by pairs (Fig. 7-d). Remark that as the synchrony rate β gets smaller, the size of anomalies and their frequency of appearance increase.

Consequence on the global behaviour. As a result of the observed microscopic behaviour, we can deduce that the asymptotic behaviour will converge to one of the following configurations:

• if β is below the critical value, anomalies take over other patterns until they cover the entire lattice. This scenario corresponds to the convergent phase as observed by the density parameter in the previous section.

• if β is high enough and strictly inferior to 1, anomalies continue to appear but checkerboard regions will "repair" them in a few time steps. Instead, particles follow a spatial non-biased random walk until they meet and annihilate. After long simulation times, the checkerboard pattern will cover the entire lattice.

To sum up, this behaviour, derived from the stability of checkerboard patterns under β-synchronism, is a novel property exclusively observed for this updating scheme, and suggests that the behaviour of ECA 50 is indeed qualitatively different in α-and β-synchronism.

Second case study: ECA 6

ECA 6 shows a peculiar behaviour under different asynchronisms: a phase transition occurs for the α-synchronous version but it is not observed for βsynchronism (see Fig. 8). The transition table of the rule is: 000 001 010 011 100 101 110 111 0 1 1 0 0 0 0 0

In order to understand the mechanism involved in the dynamics of this rule, one needs to analyse the evolution of cells states at a microscopic level. To simplify the description of configurations of ECA 6, we propose to consider branches as contiguous groups of 1-cells surrounded by 0-cells. Under synchronous updating, these branches shift regularly but when noise is introduced, variations can occur in the form of delays, creation, destruction of branches.

Behaviour in α-synchronism. In order to describe the qualitative behaviour of α-synchronous ECA 6, we analyse two "events": the destruction or the creation of a branch, and determine which event is more likely to occur depending on the value of the synchrony rate α. Two mechanisms need to be highlighted:

1. We first consider the case of a single branch and start to build the graph of the possible evolutions, with their associated probabilities (see Fig. 9). We see that for all values of the synchrony rate α, the creation of a new branch ("birth") is more probable than its destruction ("death").

α α 3 +2α(1-α) 2 1-α α 2 (1-α)
\Birth"

α 2 (1-α)
\Death"

α 2 (1-α)+(1-α) 3 α(1-α) 2 α 3 (1-α) α(1-α) 3
\Death"

α 2 (1-α) 2 } α 3 (1-α)
\Birth"

Figure 9: A sample of transition graph which illustrates the possible evolutions from a single branch in α-synchronous ECA 6. Here, by considering only groups of four cells, we find that the probability of "Birth" events is higher than "Death" events.

2. On contrary, when two branches are separated by only one cell, the right branch can be destroyed (see the synchronous case of Fig. 10). As the distance between branches varies due to random updates, multiple possibilities to destruct branches exist through this process.

For values of the synchrony rate α close to 1, the probabilities to create or destroy branches are almost equal. On the other hand, the probability to destruct branches through their interactions is high as, for high α, this phenomenon happens almost surely as soon as the distance between branches becomes critical. However, for low values of α, the opposite behaviour occurs: as bigger clusters of continuous 1s appear more often, it becomes more probable to create new branches than to destroy them, thus overcoming the effect of interactions branches. This behaviour is confirmed by experiments, for which the behaviour remains active and the density parameter converges to a fixed value (see Fig. 4 page 9).

To sum up, studying the local dynamics of ECA 6 allows us to understand better why two different phases may occur for different values of α. We now intend to consider the β-synchronous case in order to investigate why the phase transition does not exist.

Novel mechanisms under β-synchronism. Because of the extension of the state space, to study the dynamics of β-synchronous updating using the previous approach is difficult. However, comparing the mechanism involved behind the creation of branches gives an insight on why the non-converging phase does not exist for β-synchronism.

Let us consider the examples given in Fig. 10, where creation of branches are visualized under two updating schemes. In the α-synchronous case, as soon as an isolated 1 is created, it remains stable (case a). However, in the βsynchronous case, branches are created when a cell changes its eigenstate to 0 but keeps its observable as 1 (light gray cells). These branches have a short life expectancy, as (1) they cannot activate neighbouring cells until some space is created between branches and (2) they disappear as soon as they finally manage Light gray cells represent state (0, 1) and green/darker gray state (1, 0).

to update their observable state to 0 (case b). The only means to create branches in β-synchronous ECA 6 occurs for low values of the synchrony rate β (case c): in that case, the branch will survive sufficiently long time for some space to be created and then it will survive like a normal branch. The arguments above do not formally constitute a proof, but this first analysis may provide a possible explanation for a difference of behaviour between α-and β-synchronism.

The case of ECA 58

The observations made on ECA 58 are probably one of the most surprising result of this study: among all ECA, it is the only rule that displays a qualitative difference of behaviour between β-and γ-synchronism (see Fig. 11). To this date, it is not understood why the behaviour of ECA 58 changes between the two updating schemes. This issue is justified by several factors: 1. First, proving that the absence of a passive phase is a much more difficult problem than proving its existence. The complexity of establishing such a proof is also greatly increased by the fact that the state space is larger (with observation states).

2. Second, β-and γ-synchronism follow similar mechanisms. Indeed, they differ only in the sense that in β-synchronism, cell-to-cell transmission of the same neighbourhood are correlated.

3. Finally, it should be noted that although the rule ECA 58 differs only by one bit from ECA 50, it is sufficient to introduce novel patterns that limits the use of previous techniques: must be conducted in order to confirm this difference of behaviour, and novel approaches must be elaborated in order to find possible divergences between βand γ-synchronism.

Discussion

This paper presented a formalism for a new type of asynchronism in cellular automata, called asynchronous information transmission. We compared this type of perturbation to α-synchronism for Elementary Cellular Automata. We then highlighted specific examples for which directed percolation phenomena occur, and observed different responses to each asynchronism:

• For ECA 50, the macroscopic behaviour is conserved, but a microscopic analysis of the dynamics reveals novel properties for β-synchronism.

• For ECA 6, β-synchronism introduces modifications in the microscopic dynamics, which alter qualitatively the macroscopic behaviour.

• For ECA 58, a qualitatively different response is observed for β-and γsynchronism.

The implications of these observations seem promising: in spite of the resemblance of the responses of most ECA, for each updating scheme we could find at least one example where the behaviour differs from the other updating schemes. This observation supports the idea that the behaviour of cellular automata can sometimes be largely determined by the updating scheme. This echoes recent results obtained for a biological model with a stochastic transition rule [START_REF] Bouré | First steps on asynchronous lattice-gas models with an application to a swarming rule[END_REF]). However, it is still an open question to predict how the updating scheme influences the behaviour of cellular automata and why phase transitions appear

Figure 1 :

 1 Figure1: Different updating schemes applied to a rudimentary collision avoidance system. Black planes represent actual states, and in the case (c), white planes denotes how they are perceived by the opposite plane.

Figure 3 :

 3 Figure3: Example of the time cycle for a 3-cell sample for three perturbations of the updating scheme: α-synchronous (left), β-synchronous (middle) and γsynchronous (right) (0 is represented in white, 1 in gray). The applied rule is ECA 50 (see Sec. 3).

Figure 4 :Figure 5 :

 45 Figure4: A sample of the observations made on ECA rules on asynchronous updating schemes. The plot show the profile of the density parameter as a function of the synchrony rate (black line for α, red/dark gray for β, and green/light gray line for γ). All diagrams start from the same initial configuration. Time goes from bottom to top.

Figure 6 :

 6 Figure 6: Phase transition analysis for β-synchronous ECA 50 on a log-log plot. The straight line follows a power law f (t) = K × t -δ with the critical exponent δ = 0.1595. Measures are averaged over 32 automata of size 10000.

Figure 7 :

 7 Figure 7: Patterns appearing in space-time diagrams of β-synchronous ECA 50.

Figure 8 :

 8 Figure 8: Samples of space-time diagrams of ECA 6 under different values of synchrony rates α and β. Note the active phase occurring for α = 0.3.

Figure 10 :

 10 Figure 10: Branching phenomenon in ECA 6 under α-and β-synchronism.Light gray cells represent state (0, 1) and green/darker gray state (1, 0).

Figure 11 :

 11 Figure 11: Comparative observation of the behaviour of ECA 58 under β-and γsynchronism. According to quantitative experiments, the sub-critical behaviour for β occurs for β < 0.289 whereas the γ-synchronous version does not seem to converge to an all 0 configuration.

Table 1

 1

	: Classification of the minimal ECA per observed difference of behaviour,
	using the density parameter.
	(a) Discontinuity	6, 18, 26, 38, 50, 58, 106, 134, 146
	(b) Other different
	response

Table 2 :

 2 Measurements of the critical synchrony rates for different rules and asynchronisms.

	Class	ECA	α c	β c	γ c
		18	0.714 0.749 0.655
		26	0.475 0.526 0.406
	DP hi	50 58	0.628 0.601 0.487 0.340 0.289 -
		106	0.815 0.848 0.813
		146	0.675 0.732 0.635
		6	0.283	-	-
	DP low	38	0.041	-	-
		134	0.082	-	-

Because of the proximity of their definitions, the effects of β-and γ-synchronism on CA behaviours are expected to be similar in most cases. Therefore γ-synchronism will only be mentioned when a difference with β-synchronism is observed.

The complete set of results can be found at: http://www.loria.fr/ ~boure/eca.

For the sake of conciseness, we choose to put the third class DP 2 aside, as it displays a phase transition in ECA 178, but for an order parameter different than density.

in some automata and not in others (e.g. [START_REF] Fatès | Does Life resist asynchrony? In Game of Life Cellular Automata[END_REF]. By resuming the exploration of the field of updating schemes, we bring to light new examples of behaviour alterations appearing under different perturbations.

Probing a model to reveal its specificities. The approach we followed used the updating scheme as a "probing tool" to explore the behaviour of cellular automata. By subjecting models to different kinds of updating scheme and observing the resulting behaviour, we gained insight on (1) the models' properties -by highlighting to which perturbation they are robust to -and (2) the updating schemes themselves, by underlining the properties they affect, or the novel phenomena that they introduce.

Updating schemes as a component. To this date, studies on complex systems have mainly focused on a variation of the individual rules considering a single updating scheme. Our conclusion is that, in studies of complex systems, the updating scheme should hold a modular position in order to allow a scrutiny of the behaviour that is orthogonal to the exploration of the transition rule space.