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.

Algorithm

algorithm DEVS-coordinator   Variables:      parent // parent coordinator      ${\displaystyle t_{l}}$: // time of last event      ${\displaystyle 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${\displaystyle i\in D}$do             send init-message(t) to child ${\displaystyle 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 ${\displaystyle 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(${\displaystyle 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(${\displaystyle x_{i}}$,t) to child ${\displaystyle 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(${\displaystyle x_{i}}$,t) to child ${\displaystyle 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.