Skip to content

PDEVS

Jump to bottom
Romain Franceschini edited this page Apr 30, 2020 · 7 revisions

Atomic discrete event models are defined in Quartz by subclassing the Quartz::AtomicModel base class. They allow to model timed, reactive and autonomous systems. Their behaviour is described through state transitions and other functions, triggered by the simulator as events occur.

Which state transition is triggered depends on the type of event that occurs, which can be either:

  • an internal event, which is planned autonomously by the model to occur at a certain point in time;
  • or an external event, which may occur at any point in time. It is unplanned by the model and is used to carry one or multiple input values received through input ports so the model can react to it accordingly.

As there are many subtleties to define such system, the remainder of this page is better read entirely. However, you can jump to a subsection if you're familiar with Quartz or with the PDEVS formalism:

Running example

Let's take a running example to incrementally describe the behaviour of a simple system. We will model a cashier, a commonly used abstraction in Queuing theory that features a timed, autonomous and reactive behaviour.

In our abstraction, the cashier is either available waiting to process clients, busy serving a client or unavailable because he leaves. When available, the cashier have to serve clients (one at a time) as they arrive by processing a given amount of articles. He becomes busy for a while, the processing time being proportional to the number of articles to process. Once finished, the cashier outputs the processed articles and signals he is now available unless he leaves, in which case he will signal its availability later.

Autonomous behaviour

Before starting to define our state transitions, let's declare the state and I/O interface of our cashier model:

class Cashier < Quartz::AtomicModel
  input :articles
  output :available, :articles

  state do
    enum Phase
      Available
      Busy
      Unavailable
    end

    parameter throughput = 0.4    # articles per time unit
    var phase = Phase::Available
    var number_of_articles = 0
  end
end

Articles are received through the input port :article and passed back through the output port having the same name. The available signal is sent through the output port :available.

As for the state, a phase variable is used to indicate in which phase the cashier currently is: processing articles, doing something else or waiting for clients. The variable number_of_articles indicates how many articles are to be processed. The throughput parameter indicates the mean processing time per article of the cashier. Disclaimer: the default throughput is arbitrarily chosen and may not be realistic. Choosing the right parameters is usually the task of domain experts.

Note: we didn't specified a time precision for the model since it defaults to the base time unit, which is fine for our abstraction. A time unit will represent a second in our case.

When available, our cashier waits clients for a maximum amout of 5 minutes, otherwise he leaves for doing other stuff but always comes back every 15 minutes. When he is busy, he stays that way the amount of time necessary to process the articles.

We will define the time spent in each state thanks to the #time_advance method.

Planning the duration of a state

The time advance method is used by the simulator to determine when the next internal event will be scheduled. In other words, it allows you to specify how much time you want to spend in the current state.

It is called after each state transition to give a chance the model to evolve autonomously. It is also called when the simulation is initialized, to know which models will first be scheduled. The expected return type is a Duration (see time representation).

An implementation for our requirements can be something like:

class Cashier < Quartz::AtomicModel
  # ...

  def time_advance : Quartz::Duration
    case state.phase
    when .available?
      5 * 60.time_units
    when .unavailable?
      15 * 60.time_units
    else
      Quartz.duration(state.number_of_articles / throughput)
    end
  end
end

Note: An important thing to remember is that you are not supposed to mutate the state from the time advance method, doing so may lead to an unexpected behaviour.

Congratulations! You completed an important step in the definition of a discrete event model, which is planning your future events.

So what now?

When a planned event expires, it is said to be due. The simulator will trigger an internal state transition to update the model state via the #internal_transition. Right before calling this transition, a chance is given to your model to send outputs for the expiring state through the #output method.

The simulator will always call the methods in this order, unless an external event comes perturbate the sequence (more on that later):

  1. #time_advance
  2. #output
  3. #internal_transition

Sending outputs

Given our requirements, the model should send outputs in all 3 states. The number of articles processed at the end of Busy state should be sent to the :articles output port, and a flag indicating whether the cashier may process clients for each state should be sent through the :available port.

Sending values to ports is done using the #post method:

class Cashier < Quartz::AtomicModel
  # ...

  def output
    if state.phase.busy?
      post state.number_of_articles, on: :articles
    end

    going_available = state.phase.busy? || state.phase.unavailable?
    post going_available, on: :available
  end
end

Note: Like the #time_advance method, you are not supposed to mutate the state from the #output method, doing so may lead to an unexpected behaviour. Also, #post is only meant to be used in the context of the #output method.

An important thing to notice is that when the cashier is in the Available state, we send the opposite on the :available port. This is because the output method is called when the state expires. Thus, it is about to become unavailable.

This can be counterintuitive in some cases, but this is how the underlying formalism on which Quartz is based is defined. But this also makes a lot of sense for other cases, such as sending the number of processed articles at the end of the Busy state.

Internal state transition

Once our outputs are sent, we may change our expiring state via the #internal_transition function. The new state will depend on whether the cashier is currently available. If so, it will become unavailable because it means the cashier spent 5 minutes waiting for clients and decide to leave. If not it will become available, because it either means the cashier comes back or that he just finished processing the previous client.

class Cashier < Quartz::AtomicModel
  # ...

  def internal_transition
    state.number_of_articles = 0
    state.phase = if state.phase.available?
                    State::Phase::Unavailable
                  else
                    State::Phase::Available
                  end
  end
end

Note: you can also assign a new state using the #state= method.

Wrap-up

Congratulations! you defined your first autonomous discrete event model with Quartz, with outputs.

Let's review what will happen if we simulate our cashier model as-is:

  1. In the initial state, the cashier is in the Active state phase.
  2. The simulator calls the #time_advance function, which returns a duration of 300s in our case (5min).
  3. The Active state expires (no inputs comes perturbate the model). The #output function is called, which outputs false to the :available output port. #internal_transition is called and the model goes to the Unavailable state.
  4. The #time_advance function is called again. The current state will expire after 900s (15min), and so on.

Such a simulation can go on forever unless a termination condition is set. Note that the simulation may stop on its own if the model returns an infinite duration from #time_advance.

Reactive behaviour

Let's now focus on another state transition expected to be defined by an atomic model: the external transition, which may be triggered at any point in time. No matter the current state planned duration, the external transition will perturbate the model. This is exactly what we should expect from a reactive system.

For example, when our cashier is available, he plans to become unavailable after 5min if no client shows up to avoid sitting indefinitely. If our cashier were a robot, waiting indefinitely would be modelled by planning an infinite duration for the available state. No matter the duration, what is important here is that we expect a client to interrupt this available state at some point.

External transition

In Quartz, you should define the #external_transition(messages) method to react to external inputs. The messages parameter is a Hash mapping input ports to a list of input values (Hash(InputPort, Array(Any))). This means multiple inputs can arrive at the same time, even on the same input port.

When input events occurs, the following methods are called:

  1. #external_transition(messages) to change the state according to the inputs.
  2. #time_advance to plan the new future internal event.

Here's a first attempt in writing our cashier external transition:

class Cashier < Quartz::AtomicModel
  # ...
  def external_transition(messages)
    if state.phase.available?
      n = messages[input_port(:articles)].map(&.as_i).sum
      state.number_of_articles = n
      state.phase = State::Phase::Busy
    else
      raise "No inputs should arrive when #{self} is unavailable"
    end
  end
end

As you can see, we only consider inputs when our cashier is available. In our case, we only have one input port, so we know for sure that messages contains the input_port(:articles) key with associated input(s).

As already said, it is possible that multiple inputs arrive simultaneously even on the same input port. For our cashier, it would mean that several clients arrive at the same time, each with their own shopping cart full of articles. What is going to be our policy then? We can either decide to process the sum of all articles as if it were only one client, or we can decide to select one of them, again according to some policy (randomly, based on a property, ...).

In the proposed external transition, we took the first option. We update the cashier state with the number of articles to process and change its phase to Busy.

Note: If we chose to select only one client, the others will be silently ignored and their articles will never be processed unless the cashier has a way to put them back on the system, e.g. via a dedicated output port.

When our cashier is not available, an exception is raised. While this may be useful to detect the mis-use of a model, there are more graceful ways to handle such cases. Read on to know how.

Output values after receiving inputs

An important thing to notice is that the output function is not called before the external transition, unlike it is for the internal transition. In this sense, atomic models are closer to Moore machines than to Mealy machines because the outputs are only based on the current state, and not on the inputs.

This means that sending an output immediately after receiving an input requires the use of a transient state, which is completely fictional and only introduced for modelling purposes. The planned duration associated to such state is a duration of 0 (which is allowed) and triggers the output method.

In our cashier example, we don't need this to output the number of articles, which already has a dedicated state (busy). However, we do need introduce a transient state to signal the cashier is not available anymore.

We need to revise our model a bit for such purpose:

class Cashier < Quartz::AtomicModel
  # ...
  state do
    enum Phase
      Available
      GoingBusy # transient state
      Busy
      Unavailable
    end
  end

  def external_transition(messages)
    if state.phase.available?
      n = messages[input_port(:articles)].map(&.as_i).sum
      state.number_of_articles = n
      state.phase = State::Phase::GoingBusy # going to transient state
    else
      raise "No inputs should arrive when #{self} is unavailable"
    end
  end

  def output
    if state.phase.busy?
      post state.number_of_articles, on: :articles
    end
    going_available = state.phase.busy? || state.phase.unavailable? # updated
    post going_available, on: :available
  end

  def internal_transition
    state.number_of_articles = 0
    state.phase = if state.phase.available?
                    State::Phase::Unavailable
                  elsif state.phase.going_busy? # updated
                    State::Phase::Busy
                  else
                    State::Phase::Available
                  end
  end
end

Elapsed time

To keep track of how much time passed since the last state change, the elapsed time variable can be used. It is available through the #elapsed method and its value is updated along with the simulation before each state transition.

This variable is crucial for the following use cases.

Reschedule an internal event

Let's decide to change our external transition to ignore clients coming in while the cashier is busy or unavailable, instead of raising an exception.

Pretty straightforward! Our revised transition would look like this:

def external_transition(messages)
  if state.phase.available?
    n = messages[input_port(:articles)].map(&.as_i).sum
    state.number_of_articles = n
    state.phase = State::Phase::GoingBusy
  end
end

Spoiler alert: it's wrong.

While this seems straightforward, we have to keep in mind that right after #external_transition is called, the #time_advance method is also called so that the simulator knows how much time the cashier wants to stay in the same state.

So if our cashier is in the Busy state for 25s (the time necessary to process 10 articles) and a client interrupts the cashier 15 seconds after he started processing articles, the time advance function is going to return again 25s (Quartz.duration(state.number_of_articles / throughput)). The cashier will spend in total 35s in the busy state instead of 25.

To avoid such issue, we have take the elapsed time into account. A common way to handle this is to introduce a state variable that represents the planned duration associated with a state, e.g. var planned_duration = 0.time_units.

Here's a new version of our model with such technique:

class Cashier < Quartz::AtomicModel
  input :articles
  output :available, :articles

  state do
    enum Phase
      Available
      GoingBusy
      Busy
      Unavailable
    end

    parameter throughput = 0.4 # articles per time unit
    var phase = Phase::Available
    var number_of_articles = 0
    var planned_duration : Quartz::Duration = 5 * 60.time_units
  end

  def time_advance : Quartz::Duration
    state.planned_duration
  end

  def output
    if state.phase.busy?
      post state.number_of_articles, on: :articles
    end
    going_available = state.phase.busy? || state.phase.unavailable?
    post going_available, on: :available
  end

  def external_transition(msg)
    if state.phase.available?
      n = msg[input_port(:articles)].map(&.as_i).sum
      state.planned_duration = Quartz.duration(n / throughput)
      state.number_of_articles = n
      state.phase = State::Phase::GoingBusy
    else
      # reschedules an internal event as before interruption
      state.planned_duration -= self.elapsed
    end
  end

  def internal_transition
    if state.phase.available?
      state.phase = State::Phase::Unavailable
      state.planned_duration = 15 * 60.time_units
    elsif state.phase.going_busy?
      state.phase = State::Phase::Busy
      state.planned_duration = 0.time_units
    else
      state.phase = State::Phase::Available
      state.planned_duration = 5 * 60.time_units
    end
  end
end

Initial state

The elapsed time can also be set during initialization. It will be taken into account by the simulator to calculate the next internal event, according to this formula :

next_internal_event = model.time_advance - model.elapsed

This can be useful to initialize or restore a simulation in a particular state.

For example, if we consider a model where multiple cashiers works in parallel, the initial elapsed value can be used to shift the time at which each of them goes unavailable, to avoid all cashiers leaving at the same time if no clients showed up for 5 minutes.

cashier1 = Cashier.new("cashier_1")
cashier2 = Cashier.new("cashier_2")

cashier2.elapsed = 150.time_units

If we simulate those two cashiers, their breaks will be staggered to increase the amount of time clients can actually be served. The time sequence would be as follows if no input occurs:

  1. After 2m30, cashier 2 takes a break for 15min
  2. At time 5m, cashier 1 takes a break for 15min
  3. At time 17m30, cashier 2 comes back
  4. At time 20m, cashier 1 comes back

When inputs and internal events occurs simultaneously

The last important thing to consider is the possibility that an internal event may expires at the same time an input event occurs.

This situation is known as an event collision and can be specicically adressed. A specific state transition, called confluent transition is used and literally represent the union of an internal event with an external event. It has a default behavior that can be overriden for the purpose of your model.

Its default definition is as follows:

def confluent_transition(messages)
  internal_transition
  external_transition(messages)
end

While this is an appropriate handling of the conflict in many cases, you may want to reverse the applied order of transitions, or define a specific behaviour altogether.

Note: In any case, that means that outputs are already sent (recall the sequence of transitions).

In our example, such conflict can occur if a client arrives when the cashier finishes with a first client.

Common patterns

While you learned how to effectively mix autonomous and reactive behaviour, this section provides examples to common patterns, such as generators and collectors. The former are purely autonomous while the latter are purely reactive.

Generators

As their names suggest, generators are used to send values over one or several outputs ports and don't expect any input.

They are typically used to generate a sequence of values, from a statistical distribution or from data points stored in a file or in a database.

Below is an example that generates random numbers between 0 and 1 from a uniform distribution every 1 time unit:

class RandomGenerator < Quartz::AtomicModel
  output :out

  state { parameter prng = Random.new }

  def time_advance : Quartz::Duration
    1.time_unit
  end

  def output
    post prng.rand, on: :out
  end

  def internal_transition
  end

  def external_transition(bag)
  end
end

Collectors

Collectors are the exact opposive of generators. They feature a passive behaviour, waiting indefinitely until inputs wakes them up to do a task.

Quartz provides the PassiveBehavior mix-in to help define such models. It defines an empty behaviour to the #output, #internal_transition and defines a #time_advance methods that returns an infinite duration.

Below is an example that counts the total number of inputs received:

class Counter < Quartz::AtomicModel
  include Quartz::PassiveBehavior

  state { var count = 0 }

  def external_transition(messages)
    self.each_input_port do |input_port|
      if messages.has_key?(input_port)
        state.count += messages[input_port].size
      end
    end
  end
end

In the next section you'll learn how to couple models together to form a network of components. Yay!

Next: Hierarchical models.

Clone this wiki locally