## Probing robustness of cellular automata through variations of asynchronous updating

Received Aug 23; Accepted Jun Abstract Discrete dynamical systems are used to model various realistic systems in network science, from social unrest in human populations to regulation in biological networks.

A common approach is to model the agents of a system as vertices of a graph, and the pairwise interactions between agents as edges. Agents are in one of a finite set of states at each discrete time step and are assigned functions that describe how their states change based on neighborhood relations. Full characterization of state transitions of one system can give insights into fundamental behaviors of other dynamical systems.

In this paper, we describe a discrete graph dynamical systems GDSs application called GDSCalc for computing and characterizing system dynamics. It is an open access system that is used through a web interface. We provide an overview of GDS theory. This theory is the basis of the web application; i.

We present a set of illustrative examples to demonstrate its use in education and research. Finally, we compare GDSCalc with other discrete dynamical system software tools.

Our perspective is that no single software tool will perform all computations that may be required by all users; tools typically have particular features that are more suitable for some tasks.

We situate GDSCalc within this space of software tools. Introduction Background and Motivation Civil disobedience [ 1 ], addiction [ 2 ], emotional behavior [ 3 ], social media [ 4 ], biology [ 5 ], and finance [ 6 ] are some of the research topics that are studied using agent-based modeling. Many simulations in these fields represent their populations of proteins, neurons, institutions, humans as networks, with vertices and edges denoting agents and their interactions, respectively.

One goal of simulation is to understand how information, behaviors, and other contagions propagate through a networked population. There are fundamental aspects of network dynamics common to these and other domains, and other aspects that are domain-specific. Other names include finite dynamical systems and generalized cellular automata. Informally, a GDS consists of a network; a set of states, an element of which is assigned to each vertex; a function for each vertex that describes how the agent changes its state; and an update procedure that specifies the sequencing of vertex function execution.

A GDS computes dynamics by evaluating vertex functions that have dependencies encoded by the dependency network, at each time step. A GDS is defined formally below. The GDSC application can be used for both research and education. As evidence for the former point, we note that three works [ 8 — 10 ] used GDSC to identify experimentally dynamical system behaviors that were then rigorously proved as general characterizations of GDSs.

Thus, GDSC is a useful tool for experimental mathematics and computational mathematics, where computational studies are used to guide formulation of theorems and provide insights for their proofs.

Furthermore, computational results are also useful in their own right; e. GDSC works on small to moderate size networks. The reason for this is inherent in the problem of computing the complete dynamics of a GDS: For a vertex graph, this is state transitions. Nonetheless, specific reasoning can be done for a much larger class of networks. Furthermore, the theorems alluded to above are constructed for arbitrary numbers of vertices; i.

GDSs generalize concepts such as cellular automata, Boolean networks, graph automata, and synchronous and sequential discrete dynamical systems.

We will return to this topic when we discuss other software systems. GDSs are closely related to a host of other models, such as finite automata, discrete recurrent Hopfield networks, finite state machines, and systolic arrays see [ 12 ] for further references. GDS is a general model of computation which can simulate general and resource-bounded Turing machines [ 12 ].

Theoretical and software foundations of GDSCalc capabilities. We discuss the major elements of GDS theory which provide the basis for the web-application. In particular, the theory is designed to produce a mental model [ 13 ] as well as a formal model for the user, which is then reflected in the user interface UI , compute engine, and results of GDSC.

Illustrative examples using GDSCalc. We provide four examples that highlight the usefulness of GDSC for classroom use and research. Although our focus here is on research, our examples will also bring out the usefulness of GDSC for educational purposes. Terms used here are defined below. These examples also address features of the system. The first example describes how GDSC was used to find a class of GDS, based on trees acyclic graphs , that generate particular long-term dynamics: The second example addresses stability and evolution.

It illustrates how GDSC was used to find classes of GDS that produce arbitrarily large limit cycles, and limit cycles that form undirected binary hypercubes in attractor graphs. Both of these results significantly extend the state-of-the-art on system stability. A third illustrative use case departs from binary or Boolean vertex state systems to investigate dynamical systems which have any finite number of vertex states.

We established what to our knowledge are the first theoretical results of their kind on large state sets, identifying conditions that guarantee that the only long-term dynamics of a system are fixed points, and that these systems can produce bifurcations. These first three sets of results are our own. In a fourth example, we illustrate that GDSC can produce results in the literature [ 5 ] from other researchers, demonstrating that GDSC is applicable to research beyond ours.

We emphasize that in the first three examples, the experimental results were used to develop intuition and concrete data that enabled us to achieve a primary aim: This justifies our earlier claim that GDSC can be used for experimental and computational mathematics. Furthermore, these examples demonstrate the range of applications that can be investigated with GDSC.

Although each set of results can potentially be used in multiple applications, our first through fourth sets of results were motivated by general systems, evolution, social sciences, and biology, respectively. We note that these examples illustrate the human-computer interactive nature of problem solving possible with GDSC.

For the first three examples, the problems being addressed can only be defined at a high level e. Since there are no known algorithmic solutions to these problems, they require interactive systems [ 14 ] that enable a user to test many sets of inputs.

Comparisons of dynamical systems software tools. We compare GSDC with other dynamical systems tools. We also describe several other dynamical system models which serve as background for the comparisons. GDSC provides unique features not found in other tools.

For example, our tool is web-based, meaning that a user need not concern herself with compiling software, third-party libraries, software upgrades, commercial software purchase, system compatibility issues, and high performance resources needed for many of the computations. We also note that GDSC will not perform some analyses available with other software. Our position is that GDSC is a useful tool for some classes of problems, but that other tools are better suited for other problems.

An analyst is best served by having access to a collection of tools so that she may select one that is appropriate for a particular task. The GDSC online environment [ 15 ] contains supporting materials including: GDS is formally introduced in the next section, with an example to make the concepts concrete. Research-driven examples are used to demonstrate the utility of the GDSC system; these examples are taken from real research projects using published data.

Finally, we itemize features of our system and compare GDSC to other dynamical systems software. Analysis In this section, we formally present the GDS. Then, to make the ideas concrete, we present two vertex functions for vertex state update, followed by examples of GDSs. Variants of the GDS formalism can be found in [ 17 ]. We use the convention that directed edge u, v means that the state of vertex u is used to determine the next state of vertex v.

The 1-neighborhood of a vertex v is the set of vertices adjacent to v in X. We refer to x[v] as the restricted state. Here, n[v] i is the ith entry in the sequence. We denote the system state and restricted state at time t as x t and x t [v], respectively. The dynamics of changes in vertex states are governed by a sequence F.