Timed Nets

This page provides a brief introduction to timed CPNs and related concepts.

Nature of simulated time

In order to understand how time is represented in a CPN, we must first distinguish clearly between real time and simulated time. Real time is just that: time in the real physical world in which the simulator executes a model and we can watch what happens. Simulated time is just a symbolic representation of time that we may optionally build into a model. It has no reality outside the symbolic world of the model that contains it.

Real time and simulated time have no intrinsic relationship whatsoever. We may or may not build a symbolic representation of time into a model. If we do not, the sequence of states that an executing model passes through has no temporal interpretation: it is just a sequence of states.

Representing time in a CPN

In order to take time into account we need a way to represent and manipulate time within a model. A surprisingly simple methodology provides everything we need in order to represent time in a CPN:

• A token may have an associated number, called a time stamp. Such a token is called a timed token, and its color set is a timed color set. In the example below, the place D contains one timed token with value (q,0) and time stamp 145.
  

  A timed token

• The simulator contains a counter called the clock. The clock is a number whose current value is the current simulation time. The current value of the clock is shown as part of the overview of a net which is one of the index entries. In the example below, the current simulation time is 136.
  

  Current simulation time

• A timed token is not available for any purpose whatever unless the clock time is greater than or equal to the token’s time stamp.
• When there are no enabled transitions, but there would be if the clock had a greater value, the simulator increments the clock by the minimum amount necessary to enable at least one transition.

How simulated time works

Simulated time has nothing to do with the external time during which the simulator steps through net execution and observers possibly watch the execution process, or with the numbered sequence of steps by which the simulator executes a net. Simulated time is just an incrementable number that is globally available within an executing model. The value of this number can be thought of as the time indicated by a simulated clock. When the number is incremented, the clock moves forward to a later time.

The units of simulated time do not inherently represent any particular absolute time unit. We may interpret simulated time units as microseconds or millennia, depending on what we are modeling, but syntactically time is just a number. For brevity, simulated time is sometimes referred to as model time.

Simulated time and transition enabledness

The state of a net changes only when enabled transitions fire. In order for simulated time to affect net execution, it must affect transition enabledness and firing.

This effect is produced by the rule that a timed token is unavailable for any purpose unless the clock is greater than or equal to the token’s time stamp. Such a token is ignored when transitions are checked for enablement: the token might as well not be there at all.

In effect, a timed token does not exist until the clock reaches a creation time, given by the token’s time stamp. When the clock reaches that time, the token suddenly springs into existence, so to speak, becomes a factor in determining enablement, and can be removed from a place when transitions occur.

The simulated clock

Simulated time could tick forward continually, as real time does, but that would be a very inefficient way to do things: the clock would frequently waste real time counting off intervals of simulated time during which the model remains unchanged. Such counting would accomplish nothing. It is more efficient in such a case to jump the simulated clock immediately to the next time when some change is possible, and proceed with executing the net.

Therefore the simulated clock does not move at a steady rate. Instead it remains at its current value as long as there are any enabled transitions. When there are no enabled transitions left, the clock jumps forward by the smallest amount necessary for at least one transition to become enabled. This implies that time will never move forward in a net that always has enabled transitions independently of time.

Simulated time passes when and only when the clock is incremented. Everything that happens while the clock remains at a particular setting is both simultaneous and instantaneous in simulated time.

This is convenient when a system contains an event that happens at a particular moment, but that is sufficiently complex that modeling it by firing a sequence of simple transitions, rather than one complex transition, is most convenient. Leaving the clock unincremented during such a sequence lets us model the event as a manageable series of small changes, while preserving the instantaneity of the event’s effect on the state of the model.

Help topics for timed CPNs

• Create a Timed CP-net
• Time attributes in tokens
• Timed color set functions
• Timed color sets
• Timed multisets

 Example nets

The example nets for the Timed Resource Allocation system and the Timed Protocol are examples of timed CPNs.