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,\mathrm{\infty }]$

and elapsed time

$t_e\in [0,\mathrm{\infty })$

by introducing two other time variables, last event time,

$t_l\in [0,\mathrm{\infty })$

, and next event time

$t_n\in [0,\mathrm{\infty }]$

with the following relations:

$t_e=t-t_l$

and

$t_s=t_n-t_l$

where $t\in [0,\mathrm{\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,\mathrm{\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
     $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 \varphi$ 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.