DEVS

An atomic DEVS model is defined as a 7-tuple

${\displaystyle M=<X,Y,S,s_{0},ta,\delta _{ext},\delta _{int},\lambda >}$

where

• ${\displaystyle X}$ is the set of input events;
• ${\displaystyle Y}$ is the set of output events;
• ${\displaystyle S}$ is the set of sequential states (or also called the set of partial states);
• ${\displaystyle s_{0}\in S}$ is the initial state;
• ${\displaystyle ta:S\rightarrow \mathbb {T} ^{\infty }}$ is the time advance function which is used to determine the lifespan of a state;
• ${\displaystyle \delta _{ext}:Q\times X\rightarrow S}$ is the external transition function which defines how an input event changes a state of the system, where ${\displaystyle Q=\{(s,t_{e})|s\in S,t_{e}\in (\mathbb {T} \cap [0,ta(s)])\}}$ is the set of total states, and ${\displaystyle t_{e}}$ is the elapsed time since the last event;

[2]

• ${\displaystyle \delta _{int}:S\rightarrow S}$ is the internal transition function which defines how a state of the system changes internally (when the elapsed time reaches to the lifetime of the state);
• ${\displaystyle \lambda :S\rightarrow Y^{\phi }}$ is the output function where ${\displaystyle Y^{\phi }=Y\cup \{\phi \}}$ and ${\displaystyle \phi \not \in Y}$ is a silent event or an unobserved event. This function defines how a state of the system generates an output event (when the elapsed time reaches to the lifetime of the state);

The atomic DEVS Model for Ping-Pong Players

The atomic DEVS model for player A of Fig. 1 is given Player=${\displaystyle <X,Y,S,s_{0},ta,\delta _{ext},\delta _{int},\lambda >}$ such that

${\displaystyle {\begin{aligned}X&=\{?{\textit {receive}}\}\\Y&=\{!{\textit {send}}\}\\S&=\{(d,\sigma )|d\in \{{\textit {Wait}},{\textit {Send}}\},\sigma \in \mathbb {T} ^{\infty }\}\\s_{0}&=({\textit {Send}},0.1)\\ta(s)&=\sigma {\text{ for all }}s\in S\\\delta _{ext}((({\textit {Wait}},\sigma ),t_{e}),?{\textit {receive}})&=({\textit {Send}},0.1)\\\delta _{int}({\textit {Send}},\sigma )&=({\textit {Wait}},\infty )\\\delta _{int}({\textit {Wait}},\sigma )&=({\textit {Send}},0.1)\\\lambda ({\textit {Send}},\sigma )&=!{\textit {send}}\\\lambda ({\textit {Wait}},\sigma )&=\phi \end{aligned}}}$

Both Player A and Player B are atomic DEVS models.

Simply speaking, there are two cases that an atomic DEVS model ${\displaystyle M}$ can change its state ${\displaystyle s\in S}$: (1) when an external input ${\displaystyle x\in X}$ comes into the system ${\displaystyle M}$; (2) when the elapsed time ${\displaystyle t_{e}}$ reaches the lifespan of ${\displaystyle s}$ which is defined by ${\displaystyle ta(s)}$. (At the same time of (2), ${\displaystyle M}$ generates an output ${\displaystyle y\in Y}$ which is defined by ${\displaystyle \lambda (s)}$.) .

For formal behavior description of given an Atomic DEVS model, refer to the page Behavior of DEVS. Computer algorithms to implement the behavior of a given Atomic DEVS model are available at Simulation Algorithms for Atomic DEVS.

The coupled DEVS defines which sub-components belong to it and how they are connected with each other. A coupled DEVS model is defined as an 8-tuple

${\displaystyle N=<X,Y,D,\{M_{i}\},C_{xx},C_{yx},C_{yy},Select>}$

where

• ${\displaystyle X}$ is the set of input events;
• ${\displaystyle Y}$ is the set of output events;
• ${\displaystyle D}$ is the name set of sub-components;
• ${\displaystyle \{M_{i}\}}$ is the set of sub-components where for each ${\displaystyle i\in D,M_{i}}$ can be either an atomic DEVS model or a coupled DEVS model.
• ${\displaystyle C_{xx}\subseteq X\times \bigcup _{i\in D}X_{i}}$ is the set of external input couplings;
• ${\displaystyle C_{yx}\subseteq \bigcup _{i\in D}Y_{i}\times \bigcup _{i\in D}X_{i}}$ is the set of internal couplings;
• ${\displaystyle C_{yy}:\bigcup _{i\in D}Y_{i}\rightarrow Y^{\phi }}$ is the external output coupling function;
• ${\displaystyle Select:2^{D}\rightarrow D}$ is the tie-breaking function which defines how to select the event from the set of simultaneous events;

The coupled DEVS model for Ping-Pong Game

The ping-pong game of Fig. 1 can be modeled as a coupled DEVS model ${\displaystyle N=<X,Y,D,\{M_{i}\},C_{xx},C_{yx},C_{yy},Select>}$ where ${\displaystyle X=\{\}}$;${\displaystyle Y=\{\}}$;${\displaystyle D=\{A,B\}}$; ${\displaystyle M_{A}{\text{ and }}M_{B}}$ is described as above; ${\displaystyle C_{xx}=\{\}}$; ${\displaystyle C_{yx}=\{(A.!send,B.?receive),(B.!send,A.?receive)\}}$; and ${\displaystyle C_{yy}(A.!send)=\phi ,C_{yy}(B.!send)=\phi }$.

Simply speaking, like the behavior of the atomic DEVS class, a coupled DEVS model ${\displaystyle N}$ changes its components' states (1) when an external event ${\displaystyle x\in X}$ comes into ${\displaystyle N}$; (2) when one of components ${\displaystyle M_{i}}$ where ${\displaystyle i\in D}$ executes its internal state transition and generates its output ${\displaystyle y_{i}\in Y_{i}}$. In both cases (1) and (2), a triggering event is transmitted to all influencees which are defined by coupling sets ${\displaystyle C_{xx},C_{yx},}$ and ${\displaystyle C_{yy}}$.

For formal definition of behavior of the coupled DEVS, you can refer to Behavior of Coupled DEVS. Computer algorithms to implement the behavior of a given coupled DEVS mode are available at Simulation Algorithms for Coupled DEVS.

The simulation algorithm of DEVS models considers two issues: time synchronization and message propagation. Time synchronization of DEVS is to control all models to have the identical current time. However, for an efficient execution, the algorithm makes the current time jump to the most urgent time when an event is scheduled to execute its internal state transition as well as its output generation. Message propagation is to transmit a triggering message which can be either an input or output event along the associated couplings which are defined in a coupled DEVS model. For more detailed information, the reader can refer to Simulation Algorithms for Atomic DEVS and Simulation Algorithms for Coupled DEVS.

By introducing a quantization method which abstracts a continuous segment as a piecewise const segment, DEVS can simulate behaviors of continuous state systems which are described by networks of differential algebraic equations. This research has been initiated by Zeigler in 1990s[3] and many properties have been clarified by Prof. Kofman in 2000s and Dr. Nutaro. In 2006, Prof. Cellier who is the author of Continuous System Modeling[Cellier91], and Prof. Kofman wrote a text book, Continuous System Simulation[CK06] in which Chapters 11 and 12 cover how DEVS simulates continuous state systems. Dr. Nutaro's book [Nutaro10], covers the discrete event simulation of continuous state systems too.

As an alternative analysis method against the sampling-based simulation method, an exhaustive generating behavior approach, generally called verification has been applied for analysis of DEVS models. It is proven that infinite states of a given DEVS model (especially a coupled DEVS model ) can be abstracted by behaviorally isomorphic finite structure, called a reachability graph when the given DEVS model is a sub-class of DEVS such as Schedule-Preserving DEVS (SP-DEVS), Finite & Deterministic DEVS (FD-DEVS) [HZ09], and Finite & Real-time DEVS (FRT-DEVS) [Hwang12]. As a result, based on the rechability graph, (1) dead-lock and live-lock freeness as qualitative properties are decidable with SP-DEVS [Hwang05], FD-DEVS [HZ06], and FRT-DEVS [Hwang12]; and (2) min/max processing time bounds as a quantitative property are decidable with SP-DEVS so far by 2012.

Numerous extensions of the classic DEVS formalism have been developed in the last decades. Among them formalisms which allow to have changing model structures while the simulation time evolves.

G-DEVS [Giambiasi01][Zacharewicz08], Parallel DEVS, Dynamic Structuring DEVS, Cell-DEVS [Wainer09], dynDEVS, Fuzzy-DEVS, GK-DEVS, ml-DEVS, Symbolic DEVS, Real-Time DEVS, rho-DEVS

There are some sub-classes known as Schedule-Preserving DEVS (SP-DEVS) and Finite and Deterministic DEVS (FD-DEVS) which were designated to support verification analysis. SP-DEVS and FD-DEVS whose expressiveness are E(SP-DEVS) ${\displaystyle \subset }$ E(FD-DEVS)${\displaystyle \subset }$ E(DEVS) where E(formalism) denotes the expressiveness of formalism.

• Event Segment
• Timed Event System
• Verifiable sub-classes of DEVS: SP-DEVS, FD-DEVS
• Behavior of Atomic DEVS
• Behavior of Coupled DEVS
• Simulation Algorithms for Atomic DEVS
• Simulation Algorithms for Coupled DEVS

• Automata Theory: a formal method for state transition systems
• Finite State Machine: a state transition machine with finite sets of events and states
• Petri Nets: a graphical representation of state and transition relations
• Markov Chain: a stochastic process in which the future will be determined by the current state
• Specification and Description Language: SDL, a formal complete and unambiguous language to graphically represent simulation models.