DEVS
DEVS is a formalism for modeling and analysis of discrete event systems (DESs).
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 Archived 2012-06-21 at the Wayback Machine, in 1976, while Zeigler was an associate professor at University of Michigan.
DEVS can be seen as an extension of the Moore machine formalism,[1] which is a finite state automaton where the outputs are determined by the current state alone (and do not depend directly on the input).
The extension was done by Since the lifespan of each state is a real number (more precisely, non-negative real) 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.
The state transition and output functions of DEVS can also be stochastic.
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 (such as hardware design, hardware/software codesign, communications systems, manufacturing systems) and science (such as biology, and sociology) 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.
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.
that is the set of non-negative real numbers; the extended time base,
that is the set of non-negative real numbers plus infinity.
Simply speaking, there are two cases that an atomic DEVS model
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 where The ping-pong game of Fig.
changes its components' states (1) when an external event
executes its internal state transition and generates its output
In both cases (1) and (2), a triggering event is transmitted to all influencees which are defined by coupling sets
The simulation algorithm of DEVS models considers two issues: time synchronization and message propagation.
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.
As a result, based on the reachability 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.
