This is stochastic processes model 5, Continuous-time Markov Chain. In the lecture 1, we have discussed
the definition, Kolmogorov differential equation, infinitesimal generator matrix with examples.
In the lecture 2, we have discussed birth death processes. In the lecture 3, we have
discussed Poisson processes. Lecture 4, we have discussed M/M/1 queuing model.
Simple Markovian queueing models with examples is discussed in lecture 5. Queueing networks
is discussed is discussed in lecture 6. Applications in communication networks, simulation of simple
Markovian queueing models with examples, I have discussed in lecture 7. This is lecture
8, stochastic petri nets.
In this lecture, I am going to cover the definition, simple examples followed by that stochastic
petri nets, then generalised stochastic petri nets, then finally stochastic reward nets.
Petri nets is a formal and graphical appealing language
which is appropriate for modelling systems with concurrency, Carl Adam Petri defined
the language in 1962. Petri nets have proven useful for modelling, analyzing and verifying
protocols typically used in networks. It has been under development since the beginning
of the 60’ies. You can find the introduction to petri nets in this website.
Now we are going into the definition of petri net. Petri net is a bipartite directed graph
consisting of two kinds of nodes. The first one is the places, the second one is transitions.
Transitions that are connected by directed edges or directed arcs. Arcs exist only between
places and transitions that is there is no arc between two places or two transitions.
Places typically represent conditions within the system being modelled; places typically
represent conditions within the system being modelled; they are denoted graphically as
circles. Transitions represent events occurring in the system that cause change in the conditions
of the system; they are denoted graphically as bars.
See this diagram, here are the basic components of a petri net. This is called input place
and this arc is called input arc because the arc is connecting from the place to transition
and this is called, the line is called, this bar is called a transition. The transition
to the place that arc is called a output arc and the corresponding place is called output
place. The number of dots inside the place is called tokens. Here input place has one
token whereas this place has no token.
The definition continues, input arcs, directed arcs drawn from places to transitions; they
represent the conditions that need to be satisfied for the event to be activated. Output arcs
are directed arcs drawn from transition to places; they represent the conditions resulting
from the occurrence of an event. The previous diagram, this is the input arc because it
connects place to the transition and this is called output arc because it connects transition
to place.
Input places of a transition are the set of places that are connected to the transition
through input arcs. Output places of a transition are the set of places to which output arcs
exist from the transition. In this diagram we have only one input place because the transition
has only one input arc. With respect to the same transition we have only one output place
because we have one output arc.
The definition continues, the tokens are dots or integers associated with places; a place
connecting tokens indicates that the corresponding condition is active. That means, in the previous
diagram, the one token deposited in the input place means this transition can be activated.
The place containing a tokens indicates that the corresponding condition is active. Marking
of a petri net is a vector listing the number of tokens in each place of the net. That is
called marking.
When input places of a transition has a required number of tokens then the transition is enabled.
An enabled transition may fire, event happens removing a specified number of tokens from
each input place and depositing a specified number of tokens in each of its output places.
In the same example, before the transition fires, one token in the input place, no token
in the output place. Whenever there is a token in the input place, then the condition is
active. Then the transition first enabled, after the transition enabled, it fires. After
the transition fires the token will be removed from the input place and the token will be
deposited to the output places.
So here we have only one input place and only one output place therefore, after the transition
fires, one token is removed from the input place and one token is deposited in the output
place.
Now we will see another example, enabling and firing of transitions. In this example,
we have two places; here we have two places one is called the place P on, the other place
is called P off. Initially, two tokens deposited in the place P on, no token in the place P
off. We have two transitions one is the T failure and the other one is T repair. Whenever
the conditions are satisfied, then the transitions will enable first and then it fires.
Since two tokens are in the place P on, the transition T failure enables whereas no token
is in the place P off therefore the transition T repair will not enable. If a T failure enables,
then the required number of tokens will be removed from the place P on and the required
number of tokens will be deposited in the place P off. So once the T failure enables
and fires enabling and firing of transition.
So when the T failure transition enables and fires, one token will be removed from the
place P on, one token will be deposited in the place P off. Now the situation is this
petri net. Since one token is in the place P on as well as one token in the place P off,
both the transitions T repair and T failure enables. If T failure fires, then one token
will be removed from the place P on and one token will be deposited in the place P off.
Already one token is in the place P off therefore two tokens in the place P off and one token
is removed from the place P on. Hence, zero token in the place P on and two tokens in
the place P off. Suppose at this stage, both the T repair as well as the T failure enables
but T repair fires, that means at this stage if T repair fires then one token will be removed
from the place P off and one token will be deposited in the place P on.
Therefore, when T repair fires then zero token in the place P off, two tokens in the place
P on. Similarly, in this situation no token in the place P on, two tokens in the place
P off, therefore, the T failure cannot enable, the only enabling transition is a T repair
therefore if this fires, T repair fires one token will be removed from the place P off,
one token will be deposited in the place P on hence, one token in the place P off, one
token in the place P on by T repair fires.
So these are all the dynamics in the petri net by enabling and firing of transitions.
So this is a very simple example. We are going to consider some more examples in this lecture.
Now we are going to introduce another concept called reachability analysis. Consider a petri
net containing M places and N transitions. A marking M(t) of a petri net is a M tuple
with m1 of t, m2 of t, m3 of t and so on till m suffix M of t because we have m places of
non-negative integers where mi of t denotes number of tokens in the place i at any time
at any given instant of time t.
We have m places therefore, if we make a m table and number of tokens in each place at
any given instant of time then that is called a marking. For a given reference time t 0,
M of t 0 is called an initial marking of the petri net. M of t 0 is called as an initial
marking of a petri net. A marking is reachable from another marking if there exist a sequence
of transition firings starting from the original marking that result in the new marking.
We will have some more concepts then we will go for the examples.
The reachability set of a petri net is a set of all markings that are reachable from its
initial marking through any possible firing sequences of transitions. A reachability graph
is a directed graph whose nodes are the markings in the reachability set with directed arcs
between the markings representing the marking to marking transitions. The directed arcs
are labelled with the corresponding transition whose firing results in a change of the marking
from the original marking to the new marking.