Chapter 5. Event-Based Simulation without Objects

ES Models

An ES model is a triple ⟨ SV, ET, R ⟩ where

1. SV is a set of state variable declarations defining the structure of possible system states,
2. ET is a set of event type definitions,
3. R is a set of event rules expressed in terms of SV and ET.

We show how to express the example model of a simple service desk system as an ES model. The set of state variables is a singleton:

SV = { queueLength: NonNegativeInteger}

There are two event types, both having an empty signature:

ET = { Arrival(), Departure()}

And there are two event rules:

R = { r_Arr, r_Dep}

which are defined as in Table 1 above.

Such a model, together with an initial state (specifying initial values for state variables and initial events), defines an ES system, which is a transition system where

1. system states are defined by value assignments for the state variables,
2. transitions are provided by event occurrences triggering event rules that change the simulation state through changing the system state (by changing the values of affected state variables) and the FEL (by adding follow-up events).

Whenever the transitions of an ES system involve computations based on random numbers (if the simulation model contains random variables), the transition system defined is non-deterministic.

For instance, assuming that the initial system state is S₀ = {queueLength: 0}, and there is an initial event {Arrival@1}, then, as a consequence of applying r_Arr, there is a system state change {queueLength := 1} and, assuming a random service time of 2 time units (as a sample from the underlying probability distribution function), a follow-up event Departure@3, which has to be scheduled along with the next Arrival event, say Arrival@3 (with a random inter-arrival time of 2), because Arrival is an exogenous event type (with a random recurrence). Consequently, the next system state is S₁ = {queueLength: 1}.

We need to distinguish between the system state, like S₀ = {queueLength: 0}, which is the state of the simulated system, and the simulation state, which adds the FEL to the system state, like

S₀ = ⟨ {queueLength: 0}, {Arrival@1} ⟩

S₁ = ⟨ {queueLength: 1}, {Arrival@2, Departure@3} ⟩

Doing one more step, the next transition is given by the next event Arrival@2 again triggering r_Arr, which leads to

S₂ = ⟨ {queueLength: 2}, {Departure@3, Arrival@4} ⟩

In this way, we get a succession of states S₀ → S₁ → S₂ → … as a history of the transition system defined by the ES model.

Event Rules as Functions

An event rule r = ON E(x)@t DO F( t, x) can be considered as a 2-step function that, in the first step, maps an event e = E(v)@i to a parameter-free state change function r_e = F( i, v), which maps a system state to a pair ⟨ Δ, E' ⟩ of system state changes Δ and follow-up events E'. When the parameters t and x of F( t, x) are replaced by the values i and v provided by a ground event expression E(v)@i, we also simply write F_i,v instead of F( i, v) for the resulting parameter-free state change function.

We say that an event rule r is triggered by an event e when the event’s type is the same as the rule’s triggering event type. When r is triggered by e, we can form the state change function r_e = F_i,v and apply it to a system state S by mapping it to a set of system state changes Δ and a set of follow-up events E':

r_e(S) = F_i,v(S) = ⟨ Δ, E' ⟩

We can illustrate this with the help of our running example. Consider the rule r_Arr defined in Table 1 above triggered by the event Arrival@1 in state S₀ = {queueLength: 0}. The resulting state change function F₁ defined by the corresponding event routine from Table 1 maps S₀ to the set of state changes Δ = { INCREMENT queueLength} and the set of follow-up events E' = {Departure@3}. We show how the pair ⟨ Δ, E' ⟩ amounts to a transition of the simulation state in the next section.

In ES, a system state change is an update of one or more state variables. Such an update is specified in the form of an assignment where the right-hand side is an expression that may involve state variables. For instance, the state change INCREMENT queueLength is equivalent to the assignment queueLength := queueLength + 1.

In general, there may be situations, where we have several concurrent events, that is, there may be two or more events occurring at the same (next-event) time. Therefore, we need to explain how to apply a set of rules R_E triggered by a set of events E, even if both sets are singletons in many cases.

The rule set R of an ES model can also be considered as a 2-step function that, in the first step, maps a set of events E to a state change function R_E, which maps a system state to a pair ⟨ Δ, E' ⟩ of state changes Δ and follow-up events E'.

For a given set of events E and a rule set R, we can form the set of state change functions obtained from rules triggered by events from E:

R_E = { r_e : r ∈ R & e ∈ E & e triggers r}

Notice that the elements C of R_E are parameter-free state change functions, which can be applied as a block, in parallel, to a system state S:

R_E(S) = ⟨ Δ, E' ⟩

with

Δ = ⋃ { Δ_C : C ∈ R_E & C(S) = ⟨ Δ_C, E'_C ⟩ }
E' = ⋃ { E'_C : C ∈ R_E & C(S) = ⟨ Δ_C, E'_C ⟩ }

Notice that when forming the union of all state changes brought about by applying rules from R_E, and likewise when forming the union of all follow-up events created by applying rules from R_E, the order of rule applications does not matter because they do not affect the applicability of each other, so any selection function for choosing rules from R_E and applying them sequentially will do, and they could also be applied simultaneously if such a parallel computation is supported.

However, computing a set of state changes Δ raises the question if this set is, in some sense, consistent. A simple, but too restrictive, notion of consistent state changes would require that if Δ contains two or more updates of the same state variable, all of them must be equivalent (effectively assigning the same value). A more liberal notion just requires that if Δ contains two or more updates of the same state variable, their collective application must result in the same value for it, no matter in which order they are applied.

If Δ contains inconsistent updates for a state variable, this may be a bug or a feature of the simulation model. If it is not a bug, a conflict resolution policy is needed. The simplest policy is ignoring, or discarding, all inconsistent updates. Another common conflict resolution policy is based on assigning priorities to event rules.

Consider again our running example with a system state S = {queueLength: 1} and the set of next events N = {Arrival@4, Departure@4}. Then, R_N consists of the two parameter-free change functions:

1. F₁: function () {Δ := { INCREMENT queueLength}; IF queueLength = 0 THEN
   E' := { Departure @ (4 + serviceDuration())}; RETURN ⟨ Δ, E' ⟩ }
2. F₂: function () {Δ := { DECREMENT queueLength}; IF queueLength > 1 THEN
   E' := { Departure @ (4 + serviceDuration())}; RETURN ⟨ Δ, E' ⟩}

No matter in which order we apply F₁ and F₂, forming the union of their state changes always results in Δ = {}, because the incrementation and decrementation of the variable queueLength neutralize each other, and forming the union of their follow-up events always results in E' = { Departure@(4+d)} where d is the random value returned by the serviceDuration function.

An Event Rule Set as a Simulation State Transition Function

We show that the event rule set R of an ES model ⟨ SV, ET, R ⟩ defines a transition function that maps a simulation state ⟨ S, FEL ⟩ to a successor state ⟨ S', FEL' ⟩ in 3 steps:

1. R maps the set of next events N extracted from the FEL to a set R_N of state change functions of rules triggered by one of the next events from N.
2. R_N maps the current system state S to a set of state changes Δ and a set of follow-up events E'.
3. The pair ⟨ Δ, E' ⟩ amounts to a transition of the current simulation state ⟨ S, FEL ⟩ by applying the updates from Δ to S yielding S’ and by removing N from FEL and adding E'.

We have already explained how to obtain R_N from R and how to apply R_N to S for getting ⟨ Δ, E' ⟩ in the previous subsection, so we only need to provide more explanation for the last step: processing ⟨ Δ, E' ⟩ for obtaining the next simulation state ⟨ S', FEL' ⟩.

Let Upd denote an update operation that takes a system state S and a set of state changes Δ, and returns an updated system state Upd( S, Δ). When the system state consists of state variables, the update operation simply performs variable value assignments. Using this operation, we can define the third step of the simulation state transition function with two sub-steps in the following way:

1. S' = Upd( S, Δ)
2. FEL' = FEL − N ⋃ E'

This completes our definition of how the event rule set R of an ES model works as a transition function that computes the successor state of a simulation state:

R(⟨ S, FEL ⟩) = ⟨ S', FEL' ⟩

such that for a given initial simulation state S₀ = ⟨ S₀, FEL₀ ⟩, we obtain a succession of states

S₀ → S₁ → S₂ → …

by iteratively applying R:

S_i+1 = R( S_i)

Consider again our running example. In simple cases we do not have more than one next event, so R_N is a singleton and we do not have to apply more than one rule at a time. For instance, when

S₁ = ⟨{ queueLength: 1}, {Arrival@2, Departure@3}⟩

There is only one next event: Arrival@2, so we do not have to form a set of applicable rules, but can immediately apply the rule triggered by Arrival@2 for obtaining a set of system state changes and a set of follow-up events:

r_Arr ( S₁) = ⟨{ queueLength := 2}, {Arrival@4}⟩

Now consider a simulation state where we have more than one next event, like the following one:

S₃ = ⟨{ queueLength: 1}, {Arrival@4, Departure@4}⟩

We obtain

R( S₃) = ⟨{ queueLength: 1}, {Arrival@5, Departure@6}⟩

assuming a random inter-arrival time sample of 1 and a random service duration sample of 2.