-----------------------------------------------------------
Generalized Stochastic Petri nets:
-----------------------------------------------------------

-----------------------------------------------------------
 Introduction to Petri Net Models :
-----------------------------------------------------------

A Petri net consists of places, transitions, arcs and tokens.  Tokens reside in places and move from 
one place to another along the arcs through the transitions. A marking is the number of tokens in each 
place. The transitions in a (pure) Petri net are untimed; the interest is in studying sequences of 
transition firings. A very common Petri net extension is the stochastic Petri net (SPN), in which the 
transitions are timed.
 
In fact, a commonly used method for analyzing an SPN is to transform it into a stochastic process based 
on its reachability graph and analyze the stochastic process. The stochastic process is M(t), the 
marking of the SPN at time t.  In this case, M(t) is an irreducible continuous-time Markov chain, 
(CTMC) which can be analyzed using the methods.

The steady-state or transient analysis of the Markov chain can be used to get steady-state or transient 
SPN measures.
 
Graphical notation for SPNs is not completely standardized. 

	- Immediate transitions are usually drawn as lines. 

	- Timed transitions are sometimes drawn as thick bars, sometimes as thin rectangles, and 
	  sometimes as lines if there are no immediate transitions in the net.  

	- Tokens are sometimes drawn as dots, sometimes as small circles. Sometimes when there are 
	  multiple tokens in a place, instead of drawing multiple dots there is just a number inside or 
	  just outside the circle.
 

-----------------------------------------------------------
 Petri Net Model Definitions:
-----------------------------------------------------------
 
We now give a more formal definition of a Petri net and discuss some issues related to timed Petri 
nets.  Before presenting the definition, we need the notion of a bag, also called a multiset.  A bag 
is a set where members are allowed to appear multiple times. A Petri net marking is a bag whose elements
are place names; the bag contains a place name for each token.  

A Petri net (PN) is a 5-tuple (P,T,I(.),O(.),m_{0}), where
	 . P is a set of places,
	 . T is a set of transitions,
	 . I(.), the input function, maps transitions to bags of places,
	 . O(.), the output function, maps transitions to bags of places, and
	 . m_{0} is the initial marking of the net.

A transition t is enabled by a marking m if and only if I(t) is a subbag of m. 
Any transition t enabled by marking m can fire.

When it does, I(t) is subtracted from the marking m and O(t) is added to m, resulting in a new marking.
 
In a graphical picture of a Petri net, the arcs from places to transitions represent the input functions
and the arcs from transitions to places represent the output function. If a marking enables more than one
transition, any of the enabled transitions might fire first. This firing may disable transitions which 
were previously enabled.
 
As originally defined, Petri nets did not have a time element. Petri net analysis was concerned with 
what markings were possible and whether there were markings with special characteristics, like absorbing
markings. If we want to introduce time into the Petri net model, there are several issues that must be 
decided.  Should time be associated with places or transitions?  How is time handled when there are
conflicting transitions?  
 
To associate time with places, we can say that when a token arrives in a place, it does not enable a 
transition right away, but only after a random amount of time has passed.  As soon as a transition is 
enabled, it fires. To associate time with transitions, we consider that a transition is enabled as soon
as all required tokens are present in the required places, but the transition does not fire right away.
A transition's firing time, which is specified by a distribution function, is measured from the instant 
the transition is enabled to the instant it actually fires.

A stochastic Petri net (SPN) is a Petri net with timed transitions; where the firing time distributions 
are assumed to be exponential. Thus, each transition in an SPN has a firing rate associated with it;
if the firing rate of transition t_i is lambda_i, its firing time distribution is exponential with 
mean 1/lambda_i.
 
Having decided to associate time with the transitions, we must then decide how time is to be specified 
for conflicting timed transitions; this is the execution policy. The SPN model uses the race policy. 
Under this policy, conflicting timed transitions are viewed as competing processes. The transition whose 
firing time elapses first is the one that fires.  If we have two transitions whose firing times are 
given by the random variables X_1 and X_2, then the random variable for the time until a transition 
fires is min(X_1,X_2).

An alternative execution policy is the preselection policy. Under this policy, transitions are assigned
firing probabilities independent of their firing times.  When transitions are in conflict, one is chosen
to fire based on the probabilities, and it fires once its firing time has elapsed.

A generalized stochastic Petri net (GSPN), first proposed by Ajmone Marsan et al., is a PN where both 
immediate and timed transitions are allowed. A graphical representation of a GSPN generally shows
immediate transitions as lines and timed transitions as thick bars or rectangular boxes. 
When both immediate and timed transitions are enabled in a marking, only the immediate transitions can 
fire; the timed transitions behave as if they were not enabled. If there are markings that enable more 
than one immediate transition, the conflict is resolved using a preselection policy. Thus, conflicting
immediate transitions are assigned relative firing probability values; 

These probabilities may not always add upto 1 in a marking; in such a case, they are normalized to yield 
probabilities. It is for this reason that we call them relative firing probabilities.
Note that conflict among timed transitions is resolved using the race policy.
 

-----------------------------------------------------------
Petri Net Extensions 
-----------------------------------------------------------

The basic Petri net model, while very useful, can be difficult or inconvenient to use for modeling 
certain kinds of real world situations.  Over the years, many extensions to the basic model have been 
proposed.  Some are a matter of convenience, especially regarding graphical representation, and some 
are true extensions that add modeling power. Of course, for any particular extension we must weigh the 
benefit of easier model construction and more modeling power against an increase in the difficulty of 
model analysis. 
 
In this section, we discuss some extensions that have proven useful and effective enough that they are 
generally considered to be part of the standard PN definition. They are arc multiplicity, inhibitor arcs,
transition priorities, guards and marking-dependent arc multiplicity.

**********************
Arc Multiplicity:
********************** 

Arc multiplicity is a convenient extension for representing the case when more than one token is to be 
moved to or from a place. We note that this extension does not increase the modeling power of Petri nets
but is meant to make their use easier.

If the multiplicity of the input arc connecting place p to transition t is n, it means that transition 
t is enabled if and only if there are at least n tokens in place p. When transition t fires, n tokens are
removed from place p. If the multiplicity of the output arc from the transition t to the place p is n, 
then when t fires, n tokens are deposited in place p.
 
The standard notation is to denote multiple arcs as a single arc with a number next to it giving its 
multiplicity.  Optionally, a line can be drawn through the arc to indicate that the multiplicity is great
er than 1. It is assumed that an arc without any annotation has multiplicity 1.
 
**********************
Inhibitor Arcs
**********************
 
An inhibitor arc from place p to transition t disables t in any marking where p is not empty.
Graphically, an inhibitor arc connects a place to a transition and is drawn with a small circle instead 
of an arrowhead. It is possible to use the arc multiplicity extension in addition to inhibitor arcs.

In this case a transition t is disabled whenever place p contains at least as many tokens as the 
multiplicity of the inhibitor arc. Inhibitor arcs do increase the power of Petri nets and hence are a 
true extension of Petri nets.
 
	1/ One use of inhibitor arcs is to model limited resources.

	2/ A second use for inhibitor arcs is to represent a situation where some users of a limited 
	   resource are given access to the resource with a higher priority than other users.  


**********************
Priorities
**********************
 
A way to represent priorities is to assign to each transition an integer priority level. A transition 
is enabled only if no higher priority transition is enabled. Clearly, transition priorities also extend 
the power of Petri nets.


**********************
Marking-Dependent Firing Rates
**********************
 
A common extension to SPNs and GSPNs is to allow the transition firing rates to depend on the marking 
of the Petri net.  In its full generality, the firing rate of any transition can depend on the number 
of tokens in any of the places.  Sometimes a more limited form is used, where the firing rate of a 
transition is allowed to be dependent on the number of tokens in one of the places with an outgoing arc
leading to the transition.  In particular, it is often useful to allow the firing rate to be a multiple 
of the number of tokens.

 In a similar fashion, relative firing probabilities of immediate transitions may be allowed to be 
marking dependent. Another very important extension of SPNs is the ability to specify reward rates at 
the net level. 