Discrete Event Simulation and the DEVS formalism

Just to gather new tools to help me in my M. Sc. thesis, I'm taking a course on Discrete Event Simulation. This course in fact is not as general as its name may suggest. It focuses mainly on modelling with a formalism called DEVS (which stands for Discrete Event System Specification), created by Bernard Zeigler.

The choice of the DEVS formalism instead of other tools (like Petri nets or Finite State Automata, for example) was in part because the professors and teaching assistants have been doing research with it for years, but also because there are transformations from almost all the other formalisms' models to DEVS models. Moreover, there are no transformations from DEVS models to a number of those formalisms' models, which is a good indicator of the robustness of DEVS.

So, let's see what a DEVS atomic model looks like:

M = < S, X, Y, internal-delta, external-delta, lambda, ta >

• M: a DEVS atomic model
• S: sequential state set
• X: external input event set
• Y: external output event set
• internal-delta: internal transition function
• external-delta: external transition function
• lambda: output function
• ta: time advance function

We relate this functions and sets as follows (I'll mix some semantics explanations to give you a taste of the way we think about DEVS models):

• ta: S -> R+0
  Given a state in our model, ta relates it to a time value (positive real, zero or infinite). Whenever our model changes its current state, a kind of global variable (let's call it e, for elapsed time) is reset to 0 and is incremented as events occur. When et reaches ta(currentState) the internal-delta function is "invoked".
• Q = { (s, e) | s in S, 0 <= e <= ta(s) }
  We call Q the total state set. The variable e is the elapsed time. It's importante to note that if e surpasses ta(s), (s, e) is not an element of our total state set.
• internal-delta: S -> S
  Given a state in our model, internal-delta relates it to another state. When
  e = ta(s), internal-delta tells us which is the new "current state".
• external-delta: X * Q -> S
  This function depends on a state s, the elapsed time e and an external input event, and relates this triple to a state s'. Intuitively, it models the response of our model to external stimuli.
• lambda: S -> Y

Maps a state to an element of the output event set. It's the way we let our model raise events to the "outer world".

In the next post, I'll try to put all this together in a tiny model, to see it "alive".

Martín