6. The Cell–DEVS Formalism

The Cell-DEVS formalism proposes a simple and generic way of defining discrete-event cellular models with advanced timing behavior. Each cell is a continuous-time model in which state transitions are defined by a local computation function. It also provides different delay functions that simplify complex timing definitions. This approach allows us to define Cellular Automata (CA) models with advanced timing behavior while using the formal specifications of DEVS.

Usually, cellular models consist of a grid of uniform cells that transition from one state to another depending on its previous state and the previous state of neighboring cells. However, Cadmium 2 implements the Asymmetric Cell-DEVS formalism, a more abstract and versatile cellular formalism that not only allows us to define classic, grid-like systems but also scenarios with more complex topologies and relationships (e.g., countries that are interconnected via economic transactions). In the asymmetric Cell-DEVS formalism, each cell may have different behavior, and they are not necessarily arranged in a regular lattice. Thus, unlike traditional cellular models, neighborhoods can be diverse for every cell. Next, we describe all the elements that comprise the Cell-DEVS formalism.

Let us assume we want to study the movement of individuals between the five Regions of Denmark presented in the next figure:

These regions are identified as C1–C5. We also want to assess the influence of the connections with bordering countries (namely, Germany and Sweden). The next figure shows the structure of an asymmetric Cell-DEVS coupled model representing the system under study:

Asymmetric Cell-DEVS Scenarios

Asymmetric Cell-DEVS scenarios are regular coupled DEVS models that are formally described as follows:

$$ CM=\langle X, Y, C, EIC, EOC, IC\rangle, $$

where:

• $X$ is the input set. Each element $x\in X$ corresponds to a possible input event of the Cell-DEVS model.
• $Y$ is the output set. Each element $y\in Y$ corresponds to a possible output that may leave the Cell-DEVS model.
• $C$ is the set of components. Each element $c\in C$ corresponds to a cell of the Cell-DEVS model.
• $EIC$ is the external input coupling relation. It defines how external inputs of $CM$ are linked to component inputs of each cell $c_i\in C$ in the model.
• $IC$ is the internal coupling relation. It defines the interconnections between cells in the model. We say that cell $c_i\in C$ is influenced by cell $c_j\in C$ if the $IC$ maps outputs of cell $c_j$ to inputs of cell $c_i$. Alternatively, we say that cell $c_i$ is a neighbor of cell $c_j$ if the $IC$ set maps outputs of $c_i$ to inputs of $c_j$.
• $EOC$ is the external output coupling relation. It maps outputs of cells to the $Y$ set. It allows us to forward information about the scenario to other DEVS models.

In the example, there is one cell per Region of Denmark (i.e. $C = \{ c_1,c_2,c_3,c_4,c_5 \}$ ). The figure represents the $EIC$ set by the dashed edges that link inputs from Sweden and Germany to the cells $c_5$ and $c_3$; and the $EOC$ set is depicted with dashed edges that link cells $c_3$ and $c_5$ to Germany and Sweden. Finally, we represent the $IC$ set with solid edges that link the cells. For instance, cell $c_2$ is influenced by $c_1$, $c_2$, $c_3$, and $c_4$. On the other hand, $c_3$, $c_4$, and $c_5$ are neighbor cells of $c_4$.

Asymmetric Cell-DEVS Cells

Each cell $c_i \in C$ of the scenario is formally defined as follows:

$$ c_i = \langle X_i^N, X_i^E, Y_i, S_i, N_i, \tau_i, d_i, \mathit{delay}_i\rangle, $$

where:

• $X_i^N$ is the neighborhood input set. It defines the possible inputs that the cell may receive from neighboring cells in the Cell-DEVS model.
• $X_i^E$ is the external input set. It enumerates inputs that the cell may receive not from neighboring cells (e.g., inputs from a different DEVS or Cell-DEVS model). We use the cell input set $X_i = X_i^N \cup X_i^E$ to refer to the neighborhood and external input sets together. It represents all the potential inputs that the cell may receive.
• $Y_i$ is the cell output set. It describes all the possible output events of the cell.
• $S_i$ is the cell state set. It enumerates the possible states of the cell.
• $N_i$ is the cell neighborhood set. It enumerates all the neighboring cells of the cell.
• $\tau_i : S_i \times N_i \times X_i \rightarrow S_i$ is the local computation function of the cell. When triggered, it computes the new state of cell $c_i$ from its previous state, the neighborhood set, and inputs.
• $d_i : S_i → \mathbb{R}_{\geq0}$ is the cell delay function. When the cell transitions to a new state $s_i \in S_i$, it waits for $d_i(s_i)$ time units before sharing its state transition with other cells this change.
• $\mathit{delay}_i$ is the cell delay type function. These functions allow us to define complex timing behavior effortlessly. We provide more details about these functions later.