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 ${\displaystyle t_{s}\in [0,\infty ]}$ and elapsed time ${\displaystyle t_{e}\in [0,\infty )}$ by introducing two other time variables, last event time, ${\displaystyle t_{l}\in [0,\infty )}$, and next event time ${\displaystyle t_{n}\in [0,\infty ]}$ with the following relations:

${\displaystyle \,t_{e}=t-t_{l}}$

and

${\displaystyle \,t_{s}=t_{n}-t_{l}}$

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

${\displaystyle \,t_{r}=t_{s}-t_{e}}$

is equivalently computed as

${\displaystyle \,t_{r}=t_{n}-t}$

, apparently ${\displaystyle 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
     ${\displaystyle 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$
     ${\displaystyle t_{l}\leftarrow \max\{t_{li}:i\in D\}}$;
     ${\displaystyle t_{n}\leftarrow \min\{t_{ni}:i\in D\}}$;
  when receive star-message(Time t)
     if ${\displaystyle t\neq t_{n}}$ then
        error: bad synchronization;
     ${\displaystyle i^{*}\leftarrow Select(\{i\in D:t_{ni}=t_{n}\});}$
     send star-message(t)to $i^*$
     ${\displaystyle t_{l}\leftarrow \max\{t_{li}:i\in D\}}$;
     ${\displaystyle t_{n}\leftarrow \min\{t_{ni}:i\in D\}}$;
  when receive x-message($x\in X$, Time t)
     if ${\displaystyle (t_{l}\leq t}$ and ${\displaystyle t\leq t_{n})}$ == false then
        error: bad synchronization;
     for each ${\displaystyle (x,x_{i})\in C_{xx}}$ do
        send x-message($x_{i}$,t) to child $i$
     ${\displaystyle t_{l}\leftarrow \max\{t_{li}:i\in D\}}$;
     ${\displaystyle t_{n}\leftarrow \min\{t_{ni}:i\in D\}}$;
  when receive y-message(${\displaystyle y_{i}\in Y_{i}}$, Time t)
     for each ${\displaystyle (y_{i},x_{i})\in C_{yx}}$ do
        send x-message($x_{i}$,t) to child $i$
     if ${\displaystyle C_{yy}(y_{i})\neq \phi }$ then
        send y-message(${\displaystyle C_{yy}(y_{i})}$, t) to parent;
     ${\displaystyle t_{l}\leftarrow \max\{t_{li}:i\in D\}}$;
     ${\displaystyle 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.