Asynchronous cellular automaton
Encyclopedia
Cellular automata, as with other multi-agent system
models, usually treat time as discrete
and state
updates as occurring synchronously. The state of every cell in the model is updated together, before any of the new states influence other cells. In contrast, an asynchronous cellular automaton is able to update individual cells independently, in such a way that the new state of a cell affects the calculation of states in neighbouring cells.
Implementations of synchronous updating can be analysed in two phases. The first, interaction, calculates the new state of each cell based on the neighbourhood and the update rule. State values are held in a temporary store. The second phase updates state values by copying the new states to the cells.
In contrast, asynchronous updating does not necessarily separate these two phases: in the simplest case (fully asynchronous updating), changes in state are implemented immediately. We can summarise this difference as follows
where
is the vector of states of the elements at time 
, 
is a temporary copy used in the updating, 
is the index to an individual element, 
is the total number of elements in the model, and 
is a function that calculates the new state of an element based on the current state of the elements in set 
, where 
.
The synchonous approach assumes the presence of a global clock
to ensure all cells are updated together. While convenient for preparing computer systems
, this is an unrealistic assumption if the model is intended to represent, for example, a living system where there is no evidence of the presence of such a device.
A general method repeatedly discovered independently (by K. Nakamura in the 1970s, by T. Toffoli in the 1980s, and by C. L. Nehaniv in 1998) allows one to emulate exactly the behaviour of a synchronous cellular automaton via an asynchronous one constructed as a simple modification of the synchronous cellular automaton (Nehaniv 2002). Correctness of this method however has only more recently been rigorously proved (Nehaniv, 2004). As a consequence, it follows immediately from results on synchronous cellular automata that asynchronous cellular automata are capable of emulating, e.g., Conway's Game of Life
, of universal computation, and of self-replication
(e.g., as in a Von Neumann universal constructor
).
Moreover, the general construction and the proof also applies to the more general class of synchronous automata networks (inhomogeneous networks of automata over directed graphs, allowing external inputs – which includes cellular automata as a special case), showing constructively how their behaviour may be asynchronously realized by a corresponding asynchronous automata network.
is to the updating scheme. Any interesting behaviour disappears in the asynchronous case. Harvey and Bossomaier (1997) pointed out that stochastic updating in random boolean networks results in the expression of point attractor
s only: there is no repeatable cyclic behaviour, although they introduced the concept of loose cyclic attractors. Kanada (1994) has shown that some one-dimensional CA models that generate non-chaotic patterns when updated synchronously generate edge of chaos
patterns when randomised. Orponen (1997) has demonstrated that any synchronously updated network of threshold logic units (see Artificial neuron
) can be simulated by a network that has no constraints on the order of updates. Sipper et al. (1997) investigated the evolution of non-uniform CAs that perform specific computing tasks. These models relax the normal requirement of all nodes having the same update rule. In their models, nodes were organised into blocks. Nodes within a block were updated synchronously, but blocks were updated asynchronously. They experimented with three schemes: (1) at each time step, a block is chosen at random with replacement; (2) at each time step, a block is chosen at random without replacement; (3) at each time step, a block is chosen according to a fixed update order.
There are different types of asynchronous updating, and different authors have described these in different ways. The schemes shown in the images below are as follows (Cornforth et al. 2005):
The time-state diagrams below show the differences that are caused by changing the update scheme of the cellular automata model without changing any other parameters. The rule used, rule 30
, is the same for each diagram.
like cellular automata are used to help understanding of processes that work in real life. By building simplified models, new insights can be learned. There is always a question of how simple these models should be in order to adequately describe what is being modelled. The use of asynchronous models can allow an extra level of realism in the model. All of the schemes described above have their part in real life. The random independent scheme could be appropriate for modelling social network
s or communication in computer network
s. The clocked scheme could be appropriate for modelling insect colonies
, while the self-synchronous scheme could be applied to neural tissue.
Multi-agent system
A multi-agent system is a system composed of multiple interacting intelligent agents. Multi-agent systems can be used to solve problems that are difficult or impossible for an individual agent or a monolithic system to solve...
models, usually treat time as discrete
Discrete time
Discrete time is the discontinuity of a function's time domain that results from sampling a variable at a finite interval. For example, consider a newspaper that reports the price of crude oil once every day at 6:00AM. The newspaper is described as sampling the cost at a frequency of once per 24...
and state
Finite state machine
A finite-state machine or finite-state automaton , or simply a state machine, is a mathematical model used to design computer programs and digital logic circuits. It is conceived as an abstract machine that can be in one of a finite number of states...
updates as occurring synchronously. The state of every cell in the model is updated together, before any of the new states influence other cells. In contrast, an asynchronous cellular automaton is able to update individual cells independently, in such a way that the new state of a cell affects the calculation of states in neighbouring cells.
Implementations of synchronous updating can be analysed in two phases. The first, interaction, calculates the new state of each cell based on the neighbourhood and the update rule. State values are held in a temporary store. The second phase updates state values by copying the new states to the cells.
In contrast, asynchronous updating does not necessarily separate these two phases: in the simplest case (fully asynchronous updating), changes in state are implemented immediately. We can summarise this difference as follows
| Synchronous phase 1 (interaction): |  |
| Synchronous phase 2 (update): |  |
| Fully Asynchronous updating: |  |
where
is the vector of states of the elements at time , is a temporary copy used in the updating, is the index to an individual element, is the total number of elements in the model, and is a function that calculates the new state of an element based on the current state of the elements in set , where .The synchonous approach assumes the presence of a global clock
Clock signal
In electronics and especially synchronous digital circuits, a clock signal is a particular type of signal that oscillates between a high and a low state and is utilized like a metronome to coordinate actions of circuits...
to ensure all cells are updated together. While convenient for preparing computer systems
Hardware description language
In electronics, a hardware description language or HDL is any language from a class of computer languages, specification languages, or modeling languages for formal description and design of electronic circuits, and most-commonly, digital logic...
, this is an unrealistic assumption if the model is intended to represent, for example, a living system where there is no evidence of the presence of such a device.
A general method repeatedly discovered independently (by K. Nakamura in the 1970s, by T. Toffoli in the 1980s, and by C. L. Nehaniv in 1998) allows one to emulate exactly the behaviour of a synchronous cellular automaton via an asynchronous one constructed as a simple modification of the synchronous cellular automaton (Nehaniv 2002). Correctness of this method however has only more recently been rigorously proved (Nehaniv, 2004). As a consequence, it follows immediately from results on synchronous cellular automata that asynchronous cellular automata are capable of emulating, e.g., Conway's Game of Life
Conway's Game of Life
The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970....
, of universal computation, and of self-replication
Self-replication
Self-replication is any behavior of a dynamical system that yields construction of an identical copy of that dynamical system. Biological cells, given suitable environments, reproduce by cell division. During cell division, DNA is replicated and can be transmitted to offspring during reproduction...
(e.g., as in a Von Neumann universal constructor
Von Neumann universal constructor
John von Neumann's Universal Constructor is a self-replicating machine in a cellular automata environment. It was designed in the 1940s, without the use of a computer. The fundamental details of the machine were published in von Neumann's book Theory of Self-Reproducing Automata, completed in...
).
Moreover, the general construction and the proof also applies to the more general class of synchronous automata networks (inhomogeneous networks of automata over directed graphs, allowing external inputs – which includes cellular automata as a special case), showing constructively how their behaviour may be asynchronously realized by a corresponding asynchronous automata network.
Update Schemes
Several studies have implemented asynchronous models and found that their behaviour differs from the synchronous ones. Bersini and Detours (1994) have shown how sensitive Conway's Game of LifeConway's Game of Life
The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970....
is to the updating scheme. Any interesting behaviour disappears in the asynchronous case. Harvey and Bossomaier (1997) pointed out that stochastic updating in random boolean networks results in the expression of point attractor
Attractor
An attractor is a set towards which a dynamical system evolves over time. That is, points that get close enough to the attractor remain close even if slightly disturbed...
s only: there is no repeatable cyclic behaviour, although they introduced the concept of loose cyclic attractors. Kanada (1994) has shown that some one-dimensional CA models that generate non-chaotic patterns when updated synchronously generate edge of chaos
Chaos theory
Chaos theory is a field of study in mathematics, with applications in several disciplines including physics, economics, biology, and philosophy. Chaos theory studies the behavior of dynamical systems that are highly sensitive to initial conditions, an effect which is popularly referred to as the...
patterns when randomised. Orponen (1997) has demonstrated that any synchronously updated network of threshold logic units (see Artificial neuron
Artificial neuron
An artificial neuron is a mathematical function conceived as a crude model, or abstraction of biological neurons. Artificial neurons are the constitutive units in an artificial neural network...
) can be simulated by a network that has no constraints on the order of updates. Sipper et al. (1997) investigated the evolution of non-uniform CAs that perform specific computing tasks. These models relax the normal requirement of all nodes having the same update rule. In their models, nodes were organised into blocks. Nodes within a block were updated synchronously, but blocks were updated asynchronously. They experimented with three schemes: (1) at each time step, a block is chosen at random with replacement; (2) at each time step, a block is chosen at random without replacement; (3) at each time step, a block is chosen according to a fixed update order.
There are different types of asynchronous updating, and different authors have described these in different ways. The schemes shown in the images below are as follows (Cornforth et al. 2005):
- The synchronous scheme - all cells are updated in parallel at each time step. This is the conventional model, stated here for comparison.
- The random independent scheme - at each time step, a cell is chosen at random with replacement, and updated.
- The random order scheme - at each time step, all nodes are updated, but in random order.
- The cyclic scheme - at each time step a node is chosen according to a fixed update order, which was decided at random during initialisation of the model.
- The self-clockedClock signalIn electronics and especially synchronous digital circuits, a clock signal is a particular type of signal that oscillates between a high and a low state and is utilized like a metronome to coordinate actions of circuits...
scheme - each cell has an independent timer, initialised to a random period and phase. When the period has expired, the cell is updated and the timer reset. Updating is autonomous and proceeds at different rates for different cells. - The self-sync scheme - the same as the clocked scheme, but the phase of the timers are affected by local coupling to neighbours, and so are able to achieve local synchrony.
The time-state diagrams below show the differences that are caused by changing the update scheme of the cellular automata model without changing any other parameters. The rule used, rule 30
Rule 30
Rule 30 is a one-dimensional binary cellular automaton rule introduced by Stephen Wolfram in 1983. Wolfram describes it as being his "all-time favourite rule" and details it in his book, A New Kind of Science...
, is the same for each diagram.
 |
 |
| Original rule 30 | Rule 30 updated randomly |
 |
 |
| Rule 30 updated in random order | Rule 30 updated in cyclic order |
 |
 |
| Self-clocked rule 30 | Self-synchronous rule 30 |
Implications
Often, modelsSimulation
Simulation is the imitation of some real thing available, state of affairs, or process. The act of simulating something generally entails representing certain key characteristics or behaviours of a selected physical or abstract system....
like cellular automata are used to help understanding of processes that work in real life. By building simplified models, new insights can be learned. There is always a question of how simple these models should be in order to adequately describe what is being modelled. The use of asynchronous models can allow an extra level of realism in the model. All of the schemes described above have their part in real life. The random independent scheme could be appropriate for modelling social network
Social network
A social network is a social structure made up of individuals called "nodes", which are tied by one or more specific types of interdependency, such as friendship, kinship, common interest, financial exchange, dislike, sexual relationships, or relationships of beliefs, knowledge or prestige.Social...
s or communication in computer network
Computer network
A computer network, often simply referred to as a network, is a collection of hardware components and computers interconnected by communication channels that allow sharing of resources and information....
s. The clocked scheme could be appropriate for modelling insect colonies
Colony (biology)
In biology, a colony reference to several individual organisms of the same species living closely together, usually for mutual benefit, such as stronger defense or the ability to attack bigger prey. Some insects live only in colonies...
, while the self-synchronous scheme could be applied to neural tissue.