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 as way that the new state of a cell affects the calculation of states in neighbouring cells. A cellular automaton (plural: cellular automata) is a discrete model studied in computability theory and mathematics. ... In computer science, a multi-agent system (MAS) is a system composed of several agents, collectively capable of reaching goals that are difficult to achieve by an individual agent or monolithic system. ... Discrete time is non-continuous time. ... Fig. ... A synchronous circuit is a digital circuit in which the parts are synchronized by a clock signal. ... In a synchronous system, operations are coordinated under the centralized control of a fixed-rate clock signal or several clocks. ...

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 separate these two phases: changes in state are implemented immediately. We can summarise this difference as follows

where σ^(t) is the vector of states of the elements at time t, and is a temporary copy used in the updating, i is the index to an individual element, N is the total number of elements in the model, and f() is a function that calculates the new state of an element based on the current state of the elements in set K_i, where .

The synchonous approach assumes the prescence 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. In synchronous digital electronics, such as most computers, a clock signal is a signal used to coordinate the actions of two or more circuits. ... In electronics, a hardware description language or HDL is any language from a class of computer languages for formal description of electronic circuits. ...

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 is the game of life to the updating scheme. Any interesting behaviour disapears in the asynchronous case. Harvey and Bossomaier (1997) pointed out that stochastic updating in random boolean networks results in the expression of point attractors 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. In dynamical systems, an attractor is a set to which the system evolves after a long enough time. ... To meet Wikipedias quality standards, this article may require cleanup. ... An artificial neuron (also called a node or Nv neuron or Binary neuron or McCulloch-Pitts neuron) is an abstraction of biological neurons and the basic unit in an artificial neural network. ...

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-clocked 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, is the same for each diagram. In synchronous digital electronics, such as most computers, a clock signal is a signal used to coordinate the actions of two or more circuits. ... Rule 30 is an elementary Cellular Automaton Rule. ...

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

Image File history File links No higher resolution available. ... Image File history File links No higher resolution available. ... Image File history File links No higher resolution available. ... Image File history File links No higher resolution available. ... Image File history File links No higher resolution available. ... Image File history File links No higher resolution available. ...

Implications

Often, models like cellular automata are used to help understanding of processes that work in real life. By building simplified models, new insights can be gleaned. 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 networks or communication in computer networks. The clocked scheme could be appropriate for modelling insect colonies, while the self-synchronous scheme could be applied to neural tissue. Wooden mechanical horse simulator during WWI. A simulation is an imitation of some real thing, state of affairs, or process. ... Look up realism, realist, realistic in Wiktionary, the free dictionary. ... // An example of a social network diagram Social network analysis views social relationships in terms of nodes and ties. ... This article or section is in need of attention from an expert on the subject. ... The nervous system of an animal coordinates the activity of the muscles, monitors the organs, constructs and processes input from the senses, and initiates actions. ...

References

• H. Bersini and V. Detours, 1994. Asynchrony induces stability in cellular automata based models, Proceedings of the IVth Conference on Artificial Life , pages 382-387, Cambridge, MA, July 1994, vol 204, no. 1-2, pp. 70-82.
• Cornforth, D, Green, D, & Newth, D 2005, Ordered Asynchronous Processes in Multi-Agent Systems, Physica D, vol 204, no. 1-2, pp. 70-82.
• Cornforth, D, Green, DG, Newth D & Kirley M 2002, Do Artificial Ants March in Step? Ordered Asynchronous Processes and Modularity in Biological Systems. In Standish, Bedau, Abbass, Proceedings of the Eighth International Conference on Artificial Life, Sydney, pp. 28-32
• Harvey I., and Bossomaier T.R.J, (1997). Time Out of Joint: Attractors in Asynchronous Boolean Networks. In Husbands and Harvey (eds.), Proceedings of the Fourth European Conference on Artificial Life, 67-75, MIT Press.
• Kanada Y. (1994). The Effects of Randomness in Asynchronous 1D Cellular Automata. Artificial Life IV.
• Orponen, P. (1997). Computing with Truly Asynchronous Threshold Logic Networks. Theoretical Computer Science 174(1-2):123-136.
• Sipper M, Tomassini M. and Capcarrere M.S. (1997). Evolving Asynchronous and Scalable Non-Uniform Cellular Automata. Proc. of Intl. Conf. on Artificial Neural Networks and Genetic Algorithms (ICANNGA97), Springer-Verlag.
• Virtual laboratory at Monash University