3. The DEVS Formalism

The Discrete EVent System Specification (DEVS) formalism provides a rigorous definition for discrete-event modeling and simulation. DEVS allows the user to define a mathematical object that represents an abstraction of real systems. Parallel DEVS (PDEVS) is a popular variant of the original formalism, which addresses some deficiencies of the original DEVS. In fact, multiple state-of-the-art works usually refer to PDEVS as simply DEVS. In the following, unless it is explicitly noted, the use of DEVS implies PDEVS. In DEVS, the behavior of a system can be described at two levels: atomic models, which describe the autonomous behavior of a system as a series of transitions between states and its reactions to external events, and coupled models, which describe a system as the interconnection of coupled components.

Atomic DEVS Models

The formal definition of an atomic model is described as the following:

$$ AM=\langle X, Y, S, \delta_{int}, \delta_{ext}, \delta_{con}, \lambda, ta \rangle, $$

where:

• $X$ is the input set. Each element $x\in X$ corresponds to a possible input event that may trigger the atomic model’s external transition function.

• $Y$ is the output set. Each element $y\in Y$ corresponds to a possible output event that may be triggered by the atomic model’s output function.

• $S$ is the state set. At any given time, the atomic model is in the state $s\in S$.

• $ta:S\rightarrow\mathbb{R}_{\geq0}\cup\infty$ is the time advance function. When the atomic model enters the state $s$, it will remain in this state for $ta(s)$ time units or until the model receives one or more inputs.

• $\delta_{int}:S\rightarrow S$ is the internal transition function. After spending $ta(s)$ time units in the state $s$ without receiving any input, the atomic model transitions to the state $s\prime=\delta_{int}(s)$.

• $\lambda:S\rightarrow Y$ is the output function. When the atomic is about to change its state due to an internal transition, the atomic model generates $\lambda(s)=Y^b\subseteq Y$ outputs. This function is triggered right before calling the internal transition function.

• $\delta_{ext}:S\times\mathbb{R}\times X\rightarrow S$ is the external transition function. It is triggered when the atomic model receives a bag of inputs $X^b\subseteq X$ after $e$ time units since the atomic model transitioned to its current state $s$. When triggered, the atomic model transitions to a new state $s\prime=\delta_{ext}(s,e,X^b)$.

• $\delta_{con}:S\times\mathbb{R}\times X\rightarrow S$ is the confluent transition function. This transition function decides the next state in cases of collision between external and internal events. Typically, $\delta_{con}(s,ta(s),X^b)=\delta_{ext}(\delta_{int}(s),0,X^b)$. The classic DEVS formalism does not provide any mechanism to properly handle state transition collisions. Therefore, this function is the main difference between classic DEVS and PDEVS.

The picture below is an schematic of an atomic DEVS model:

Coupled DEVS Models

The formal definition of a coupled model is described as follows:

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

• $X$ is the input set. Each element $x\in X$ corresponds to a possible input event of the coupled model.
• $Y$ is the output set. Each element $y\in Y$ corresponds to a possible output that may leave the coupled model.
• $C$ is the set of components. Each element $c\in C$ corresponds to a DEVS submodel (atomic or coupled) of the coupled model.
• $EIC$ is the external input coupling relation. It defines how external inputs of $M$ are linked to component inputs of $C$.
• $EOC$ is the external output coupling relation. It defines how component outputs of $C$ are linked to external outputs of $M$.
• $IC$ is the internal coupling relation, from component outputs of $c_i\in C$ to component inputs of $c_j\in C$.

The picture below is an schematic of a coupled DEVS model:

DEVS with Ports

Cadmium 2 implements a variant of the DEVS formalism that uses ports to define the input/output interface of the DEVS components. DEVS with ports is a very convenient way of interpreting how DEVS models communicate with each other. In DEVS with ports, each DEVS model (either atomic or coupled) receive input messages via one of its input ports, and sends output messages to other models via its output ports. Additionally, couplings between models are defined in an origin port-destination port basis. In this way, messages in the origin port are propagated to the destination port, allowing DEVS models to communicate with each other. In this wiki, we represent model ports with the portID<messageType> convention. When defining the port interface of our DEVS models, we must be aware of the following constraints:

• Port IDs must be unique in each model. In this way, we can univocally refer to one model port by its name. Note that two different components can have ports with the same name.
• Each port can only contain messages of its corresponding data type. For example, the if the data type of a port is int, we can only add integer numbers. Adding a message of type double (i.e., double-precision floating-point number) to this port would lead to an error and simulation would terminate abruptly. Note that a model can have multiple ports of different data types.
• We can only define couplings between ports of the same data type. Thus, a port which data type is int can only be coupled to another port which data type is int. In this way, we ensure that the message interface of our models is robust and predictable, as we know the data type of the messages that a port can send/receive.

The next figure shows a representation of a model implemented in Cadmium 2:

In this example, there are three atomic DEVS models: Generator, Processor, and Transducer. The Transducer model has two input ports: inGenerated<Job> and inProcessed<Job>. Both ports can only contain messages of type Job. Alternatively, the outStop<bool> port is an output port that contains boolean messages. The GPT coupled models defines different couplings between these atomic models. For example the outGenerated<Job> output port of the Generator model is coupled to the inGenerated<Job> input port of the Processor model and the inGenerated<Job> port of the Transducer model. On the other hand, the outStop<bool> output port of the Transducer model is coupled to the inStop<bool> port of the Generator model. Note that all the couplings link ports of the same message data type.