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 [math]\displaystyle{ t_s \in [0,\infty] }[/math] and elapsed time [math]\displaystyle{ t_e\in [0,\infty) }[/math] by introducing two other time variables, last event time, [math]\displaystyle{ t_l\in [0,\infty) }[/math], and next event time [math]\displaystyle{ t_n\in [0,\infty] }[/math] with the following relations:

[math]\displaystyle{ \, t_e = t - t_l }[/math]

and

[math]\displaystyle{ \, t_s = t_n - t_l }[/math]

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

[math]\displaystyle{ \,t_r=t_s-t_e }[/math]

is equivalently computed as

[math]\displaystyle{ \, t_r = t_n - t, }[/math]

apparently [math]\displaystyle{ t_r \in [0,\infty] }[/math].

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

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.