DEVS


DEVS, abbreviating discrete event system specification, is a modular and hierarchical formalism for modeling and analyzing general systems that can be discrete event systems which might be described by state transition tables, and continuous state systems which might be described by differential equations, and hybrid continuous state and discrete event systems. DEVS is a timed event system.

History

DEVS is a formalism for modeling and analysis of discrete event systems. The DEVS formalism was invented by Bernard P. Zeigler, who is emeritus professor at the University of Arizona. DEVS was introduced to the public in Zeigler's first book, Theory of Modeling and Simulation in 1976, while Zeigler was an associate professor at University of Michigan. DEVS can be seen as an extension of the Moore machine formalism, which is a finite state automaton where the outputs are determined by the current state alone. The extension was done by
  1. associating a lifespan with each state,
  2. providing a hierarchical concept with an operation, called coupling,
Since the lifespan of each state is a real number or infinity, it is distinguished from discrete time systems, sequential machines, and Moore machines, in which time is determined by a tick time multiplied by non-negative integers. Moreover, the lifespan can be a random variable; for example the lifespan of a given state can be distributed exponentially or uniformly. The state transition and output functions of DEVS can also be stochastic.
Zeigler proposed a hierarchical algorithm for DEVS model simulation in 1984 which was published in Simulation journal in 1987. Since then, many extended formalism from DEVS have been introduced with their own purposes: DESS/DEVS for combined continuous and discrete event systems, P-DEVS for parallel DESs, G-DEVS for piecewise continuous state trajectory modeling of DESs, RT-DEVS for realtime DESs, cell-DEVS for cellular DESs, fuzzy-DEVS for fuzzy DESs, dynamic structuring DEVS for DESs changing their coupling structures dynamically, and so on. In addition to its extensions, there are some subclasses such as SP-DEVS and FD-DEVS have been researched for achieving decidability of system properties.
Due to the modular and hierarchical modeling views, as well as its simulation-based analysis capability, the DEVS formalism and its variations have been used in many application of engineering and science

Formalism

Intuitive example

DEVS defines system behavior as well as system structure. System behavior in DEVS formalism is described using input and output events as well as states. For example, for the ping-pong player of Fig. 1, the input event is ?receive, and the output event is !send. Each player, A, B, has its states: Send and Wait. Send state takes 0.1 seconds to send back the ball that is the output event !send, while the Wait state lasts until the player receives the ball that is the input event ?receive.
The structure of ping-pong game is to connect two players: player A output event !send is transmitted to player B input event ?receive, and vice versa.
In the classic DEVS formalism, atomic DEVS captures the system behavior, while coupled DEVS describes the structure of system.
The following formal definition is for classic DEVS. In this article, we will use the time base, that is the set of non-negative real numbers; the extended time base, that is the set of non-negative real numbers plus infinity.

Atomic DEVS

An atomic DEVS model is defined as a 7-tuple where

  • is the set of input events;
  • is the set of output events;
  • is the set of sequential states ;
  • is the initial state;
  • is the time advance function which is used to determine the lifespan of a state;
  • is the external transition function which defines how an input event changes a state of the system, where is the set of total states, and is the elapsed time since the last event;
  • is the internal transition function which defines how a state of the system changes internally ;
  • is the output function where and is a silent event or an unobserved event. This function defines how a state of the system generates an output event ;

; The atomic DEVS model for ping-pong players
The atomic DEVS model for player A of Fig. 1 is given player= such that
Both player A and player B are atomic DEVS models.
Simply speaking, there are two cases that an atomic DEVS model can change its state : when an external input comes into the system ; when the elapsed time reaches the lifespan of which is defined by. At the same time of, generates an output which is defined by.
For formal behavior description of given an atomic DEVS model, refer to the section about behavior of atomic DEVS. Computer algorithms to implement the behavior of a given atomic DEVS model are available in the section about simulation algorithms for atomic DEVS.

Coupled 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-tuplewhere

  • is the set of input events;
  • is the set of output events;
  • is the name set of sub-components;
  • is the set of sub-components where for each can be either an atomic DEVS model or a coupled DEVS model.
  • is the set of external input couplings;
  • is the set of internal couplings;
  • is the external output coupling function;
  • 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 where ;;; is described as above; ; ; and.
Simply speaking, like the behavior of the atomic DEVS class, a coupled DEVS model changes its components' states when an external event comes into ; when one of components where executes its internal state transition and generates its output. In both cases and, a triggering event is transmitted to all influences which are defined by coupling sets and.
For formal definition of behavior of the coupled DEVS, you can refer to the section about behavior of coupled DEVS. Computer algorithms to implement the behavior of a given coupled DEVS mode are available at the section about simulation algorithms for coupled DEVS.

Analysis methods

Simulation for discrete event systems

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.

Simulation for continuous state systems

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. 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, and Prof. Kofman wrote a text book, Continuous System Simulation, in which chapters 11 and 12 cover how DEVS simulates continuous state systems. Dr. Nutaro's book, covers the discrete event simulation of continuous state systems too.

Verification for discrete event systems

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 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, finite & deterministic DEVS, and finite & real-time DEVS. As a result, based on the reachability graph, dead-lock and live-lock freeness as qualitative properties are decidable with SP-DEVS, FD-DEVS, and FRT-DEVS; and min/max processing time bounds as a quantitative property are decidable with SP-DEVS so far by 2012.

Timed event system

The general system has been described by Zeigler with the standpoints to define the time base, the admissible input segments, the system states, the state trajectory with an admissible input segment, the output for a given state. A timed event system defining the state trajectory associated with the current and event segments came from the class of general system to allows non-deterministic behaviors in it. Since the behaviors of DEVS can be described by timed event system, DEVS and RTDEVS is a sub-class or an equivalent class of timed event system.
A timed event system is a structure
where
  • is the set of events;
  • is the set of states;
  • is the set of initial states;
  • is the set of accepting states;
  • is the set of state trajectories in which indicates that a state can change into along with an event segment. If two state trajectories and are called contiguous if, and two event trajectories and are contiguous. Two contiguous state trajectories and implies.
Given a timed event system, the set of its behaviors is called its language depending on the observation time length. Let be the observation time length. If, -length observation language of is denoted by, and defined as
We call an event segment a -length behavior of, if.
By sending the observation time length to infinity, we define infinite length observation language of is denoted by, and defined as
We call an event segment an infinite-length behavior of, if .