(This pattern is described in Watson, J., Hawkins, J., Bradley, D., Dassanayake, D., Wiles, J. & Hanan, J. (2005). Towards a network pattern language for complex systems. To be presented at The Second Australian Conference on Artificial Life (ACAL 2005), and published by World Scientific in the Advances in Natural Computation series. See Publications for more information.)

Submitted by: Jim Hanan, James Watson, Daniel Bradley, John Hawkins, Dharma Dassanayake, Scott Heckbert, Andrew Hockey.

1a. Pattern name: Synchronous System State Update

1b. Classification: Model (Behavioural)

2. Intent. In many complex systems simulations, all objects that interact in the model should be updated synchronously, reflecting the parallel nature of the abstracted system. This pattern describes a method of implementing synchronous updating by creating a new set of states from current states.

3. Also known as: Synchronous update.

4. Motivation. Given the Boolean network model shown in Figure 1, you want to analyze system behaviour when all node interactions are taken into account before states are changed.

Figure 1: Simple Boolean network with node A activated.

\includegraphics[width=3.2cm]{figures/fig1.eps.gz}

Using the Synchronous State Update pattern, you would create and assign values to a new set of states (one for each node) according to all the interactions between nodes in the current state (see Figure 2). The new set of states then becomes the current set.

Figure 2: For node A, no activation is received from its inputs, so it becomes inactive. Node B is activated by node A, so it becomes active. This process of swapping states can occur indefinitely.

\includegraphics[width=7.2cm]{figures/fig2.eps.gz}

By determining the new set of states for each node in the network according to all interactions among the old states, synchronous updating is achieved.

This is different to asynchronous updating, where all nodes and their interactions are not considered before updating. From the initial conditions of Figure 1, asynchronous updating could

  • first update A according to B's state without considering A's input to B, so A and B become inactive forever
  • first update B according to A's state without considering B's input to A, so A and B become active forever

5. Applicability. The Synchronous System State Update is useful whenever all components of a complex system are concurrently interacting on the same timescale. For example, this is often the case when you are interested in the influence of interactions between entities, and thus abstract away the time differences between these interactions and consider them all at the same point in time. Examples include some Boolean models of gene regulation, social networks, and L-systems plant development. It is best suited to processes with discrete time-steps, though continuous systems can be approximated with small time-steps.

6. Structure. (Intentionally left blank).

7. Participants. Entities, Relationships, Current states, Next states

8. Collaborations. Each entity has a corresponding current state. Next states are created according to the current states of the entities and the relationships between them. The next states become the current states at the end of updating.

9. Consequences.

  • Since interactions are only considered at each time-step, this pattern abstracts away the actual time events occur.
    • For non-stochastic simulations, this causes the system to exhibit deterministic behaviour, which is often desirable for system-wide analysis.
    • If the system being modeled has asynchrony, this information is lost, unless modeled explicitly by incorporating delays and fine scale time steps.
    • May lose variability potentially created by asynchronous updating.
  • Updating slows as the number of entities increases.
  • Approximating continuous processes requires small time-steps, which requires longer processing times.

10. Implementation.

  • Small time-step sizes can be used to approximate continuous time.
  • Pointers to the new/current states lists can be manipulated to improve performance, e.g.:
        free(current)
        current = next
        next = new (un-initialized) set of states
    
  • Depending on the model's architecture, each entity (such as an agent) can handle its own updating and state, or a separate global process can maintain state lists and iterate through all entities. For very large numbers of entities, the global algorithm approach can be more efficient if simple representations are used for entities (e.g., a bit array for Boolean networks) instead of object instantiations.

11. Sample code.

C = current states of entities, indexed by node number
N = next states of entities, indexed by node number
t = current time-step

t = 1
while (t <= time-steps of interest)
    for i = 1 to number of nodes in the system
        N[i] = state based on inputs to C[i]
	
    C = N
    t = t + 1

12. Known uses. Network update [2], Game loop, L-system derivation process [1]

13. Related patterns. Asynchronous System State Update should be used when asynchronous updating is important to the model. Sequential State Update should be used when the ordering of the updates is inherent in the system being modeled (e.g., Chomsky grammars).

Bibliography

1
A. Lindenmayer.
Mathematical models for cellular interactions in development, parts I and II.
Journal of Theoretical Biology, 18:280-315, 1968.

 

2
T. Reil.
Dynamics of gene expression in an artificial genome - implications for biological and artificial ontogeny.
In D. Floreano, F. Mondada, and J.D. Nicoud, editors, Proceedings of the 5th European Conference on Artificial Life, pages 457-466. Springer Verlag, 1999.

About this document ...

Towards a Network Pattern Language for Complex Systems

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.