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.