Asynchronous Updating

Authors: Alex Tee Neng Heng, David G. Green

These demonstrations show that the manner in which cells are updated can have just as great an effect as the underlying rules in a model.

Traditionally, the cells in a CA model are synchronized. They are all updated in parallel, at the same time. However, in many real-life systems, events do not happen in such a coordinated way. For instance, modern integrated computer chips are so complex that manufacturers have to allow for different parts of the chip getting updated at different times.

In recent years, researchers have begun to look more closely at the impact that different processing patterns can have. Some of these patterns are illustrated in the figure. It shows a simple systems of four cells wit time running from left to right. Each spike indicates the time at which a particular cell gets updated.

The updating schemes

Asynchronous patterns are of two kinds: random and ordered. In random asynchronous updating, cells are updated in no particular order. In ordered asynchronous updating, there is some pattern to the order of updating.

  • In a random independent scheme, any cell can be updated at any time.
  • In a random order scheme the order is random, but all cells get updated before any one cell gets updated again.
  • In a clocked scheme, each cell gets updated at fixed time intervals, but the intervals vary from cell to cell.
  • In a cyclic scheme, all cells get updated one at a time in a fixed order.
  • In a self-synchronising scheme, cells initially update at random, but by interacting with their neighbours gradually become locally syncrhonized.

Although the demonstrations shown here show asynchrony in cellular automata, they can occur in any system with multiple components. All of the above schemes occur in real systems. In socio-economic systems, for instance, events are often random independent. Many biological systems seem to run according to a clocked scheme. The rate of plant growth, for instance, is locally limited by the supply of nutrients.

Finally, self-synchronization seems to occur in many systems and may be an important mechanism for generating local order.

References

Demo screenshot