Solutions to Parallel and Distributed Computing Problems: Lessons from Biological Sciences

1.3 EXECUTION MODELS FOR CELLULAR AUTOMATA

1.3.1 Synchronous Cellular Automata versus Asynchronous Cellular Automata

The CA model is a conceptually simple and effective solver for dynamic complex systems (DCS). From a modeler's perspective, a CA model allows the formulation of a DCS application in simple rules. From a computer simulation perspective, a CA model provides an execution mechanism that evaluates the temporal dynamic behavior of a DCS, given these simple rules. An important characteristic of the CA execution mechanism is the particular update scheme that applies the rules iteratively to the individual cells of the CA. The different update schemes impose a distinct temporal behavior on the model. Thus we must select the proper update mechanism that aligns with the dynamics of the model.

In the previous discussion, the update mechanism of CAs is described as being synchronously in parallel. However, for certain classes of DCS, the temporal dynamic behavior is asynchronous. In particular, systems with heterogeneous spatial and temporal behavior are, in general, most exactly mapped to asynchronous models [3, 41]. In case asynchronous models are solved by CA, the asynchronous temporal behavior must be captured by the update mechanism. This class of CA is called asynchronous cellular automata (ACA) [23, 39, 51, 53]. The ACA model incorporates asynchronous cell updates, which are independent of the other cells, and allows for a more general approach to CA. With these qualifications, ...