Simulation algorithms for coupled DEVS

Given a coupled DEVS model, simulation algorithms are methods to generate the model's legal behaviors, which are a set of trajectories not to reach illegal states. (see behavior of a Coupled DEVS model.) [Zeigler84] originally introduced the algorithms that handle time variables related to lifespan $t_s \in [0,\infty]$ and elapsed time $t_e\in [0,\infty)$ by introducing two other time variables, last event time, $t_l\in [0,\infty)$, and next event time $t_n\in [0,\infty]$ with the following relations:

$\, t_e = t - t_l$

and

$\, t_s = t_n - t_l$

where $t\in [0,\infty)$ denotes the current time. And the remaining time,

$\,t_r=t_s-t_e$

is equivalently computed as

$\, t_r = t_n - t$

, apparently $t_r \in [0,\infty]$.

Based on these relationships, the algorithms to simulate the behavior of a given Coupled DEVS are written as follows.

Algorithms

DEVS-coordinator
  Variables:
     parent // parent coordinator
     $t_l$: // time of last event
     $t_n$: // time of next event
     $N=(X, Y, D, \{M_i\}, C_{xx}, C_{yx}, C_{yy},Select)$// the associated Coupled DEVS model
  when receive init-message(Time t)
     for each $i \in D$ do
        send init-message(t) to child $i$
     $t_l \leftarrow \max\{t_{li}: i \in D\}$;
     $t_n \leftarrow \min\{t_{ni}: i \in D\}$;
  when receive star-message(Time t)
     if $t \ne t_n$ then
        error: bad synchronization;
     $i^* \leftarrow Select(\{i \in D: t_{ni} = t_n\});$
     send star-message(t)to $i^*$
     $t_l \leftarrow \max\{t_{li}: i \in D\}$;
     $t_n \leftarrow \min\{t_{ni}: i \in D\}$;
  when receive x-message($x \in X$, Time t)
     if $( t_l \le t$ and $t \le t_n )$ == false then
        error: bad synchronization;
     for each $(x,x_i) \in C_{xx}$ do
        send x-message($x_i$,t) to child $i$
     $t_l \leftarrow \max\{t_{li}: i \in D\}$;
     $t_n \leftarrow \min\{t_{ni}: i \in D\}$;
  when receive y-message($y_i \in Y_i$, Time t)
     for each $(y_i,x_i) \in C_{yx}$ do
        send x-message($x_i$,t) to child $i$
     if $C_{yy}(y_i)\ne \phi$ then
        send y-message($C_{yy}(y_i)$, t) to parent;
     $t_l \leftarrow \max\{t_{li}: i \in D\}$;
     $t_n \leftarrow \min\{t_{ni}: i \in D\}$;

See also

• Coupled DEVS
• Behavior of Coupled DEVS
• Simulation Algorithms for Atomic DEVS

References

• [Zeigler84] Bernard Zeigler (1984). Multifacetted Modeling and Discrete Event Simulation. Academic Press, London; Orlando. ISBN 978-0-12-778450-2.
• [ZKP00] Bernard Zeigler, Tag Gon Kim, Herbert Praehofer (2000). Theory of Modeling and Simulation (second ed.). Academic Press, New York. ISBN 978-0-12-778455-7.