## Synchronous and asynchronous updating in cellular automata

Jump to navigation Jump to search 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: The synchronous approach assumes the presence of a global clock to ensure all cells are updated together. While convenient for preparing computer systems , this might be 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 s, by T. Toffoli in the s, and by C. Nehaniv in 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 Correctness of this method however has only more recently been rigorously proved Nehaniv, As a consequence, it follows immediately from results on synchronous cellular automata that asynchronous cellular automata are capable of emulating, e.

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[ edit ] Several studies have implemented asynchronous models and found that their behaviour differs from the synchronous ones. Bersini and Detours have shown how sensitive Conway's Game of Life is to the updating scheme.

Any interesting behaviour disappears in the asynchronous case. Harvey and Bossomaier pointed out that stochastic updating in random boolean networks results in the expression of point attractors only: Kanada has shown that some one-dimensional CA models that generate non-chaotic patterns when updated synchronously generate edge of chaos patterns when randomised.

Orponen 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.

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: 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.

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. Original rule 30 Rule 30 updated in random order Rule 30 updated in cyclic order Self-clocked rule 30 Implications[ edit ] 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 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 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. References[ edit ] H. Thierry, , Fully asynchronous behavior of double-quiescent elementary cellular automata, Theoretical Computer Science: Time Out of Joint: Attractors in Asynchronous Boolean Networks. In Husbands and Harvey eds.

Theoretical Computer Science Sipper M, Tomassini M.