The Discrete Event System Specification Formalism

From IFORS Education Resources
Jump to: navigation, search

By: Hans Vangheluwe


The DEVS formalism was conceived by Zeigler [Zei84a, Zei84b] to provide a rigourous common basis for discrete-event modelling and simulation. For the class of formalisms denoted as discrete-event [Nan81], system models are described at an abstraction level where the time base is continuous (􀀀 ), but during a bounded time-span, only a finite number of relevant events occur. These events can cause the state of the system to change. In between events, the state of the system does not change. This is unlike continuous models in which the state of the system may change continuously over time. As an extension of Finite State Automata, the DEVS (Discrete Event Systems) formalism captures concepts from Discrete Event simulation. As such it is a sound basis for meaningful model exchange in the Discrete Event realm.

The DEVS Formalism

The DEVS formalism fits the general structure of deterministic, causal systems in classical systems theory. DEVS allows for the description of system behaviour at two levels. At the lowest level, an atomic DEVS describes the autonomous behaviour of a discrete-event system as a sequence of deterministic transitions between sequential states as well as how it reacts to external input (events) and how it generates output (events). At the higher level, a coupled DEVS describes a system as a network of coupled components. The components can be atomic DEVS models or coupled DEVS in their own right. The connections denote how components influence each other. In particular, output events of one component can become, via a network connection, input events of another component. It is shown in [Zei84a] how the DEVS formalism is closed under coupling: for each coupled DEVS, a resultant atomic DEVS can be constructed. As such, any DEVS model, be it atomic or coupled, can be replaced by an equivalent atomic DEVS. The construction procedure of a resultant atomic DEVS is also the basis for the implementation of an abstract simulator or solver capable of simulating any DEVS model. As a coupled DEVS may have coupled DEVS components, hierarchical modelling is supported.


Link to material: http://www.cs.mcgill.ca/~hv/classes/MS/DEVS.pdf


Personal tools