Petri nets are designed for modelling randomization, concurrency, and conflict.
A Petri net is a bipartite graph, giving formalism an easier intuitive interpretation.
Basic Definitions
Components
Places: used to represent conditions or local system states.
Transitions: used to describe events that occur in the system. It will result in a modification to the system state.
Tokens: identity-less markers that reside in places.
Arcs: specify the relationships between PLACES and TRANSITIONS.
- An arc from a place to a transition is a input arc.
- An arc from a transition to a place is a output arc.
Operations
Firing: When a transition fires tokens from input places are absorbed and tokens are created on each of the output places.
Arcs with multiplicities: If a multiplicity is associated with an arc, the firing rule is adjusted to reflect the multiplicity by altering number of tokens required or produced.
Marking: \(m:P\to\mathbb N_0\), where \(m(p)=n\) means that there are \(n\) tokens on place \(p\).
A transition \(t\) is said to be enabled in marking \(m\), aka \(m[t\rangle\), if all the pre-places of \(t\) have marking that is greater than or equal to the multiplicity of that input arc. Otherwise \(t\) is said to be disabled.
A transition which is enabled in \(m\) may fire.
When \(t\) in \(m\) fires, a new marking \(m'\) is achieved, aka \(m[t\rangle m'\).
Reachability
Starting from initial marking, by firing rules we can progress through the states of the model. This is called playing the token game.
In this way we obtain the reachability set, i.e., all possible states of the model.
We can also construct reachability graph.
Stochastic Petri Nets
In stochastic Petri net we associate an exponentially distributed delay with the firing of each transition.
The delay occurs between when the transition becomes enabled and when it fires.
Generalized Stochastic Petri Nets
Limits of SPN: model construction can be easily very large. Because actions would not be explicitly represented.
Generalized Stochastic Petri Nets (GSPN) is an extension of SPN formalism.
Immediate Transitions
When they are enabled in a model, they fire immediately with no latency.
It is always prior to delayed transition.
If two or more immediate transition can be enabled at the same time, the probability must be declared.
Inhibitor Arcs
From a place to a transition. The transition can not fire if there is a token in the place. It can fire when there is no token in the place connected to its input arc.
We can use GSPN to model concurrency, conflict, synchronization, mutual exclusion...
PN v.s. SPN v.s. GSPN
PN only includes immediate transitions
SPN only includes (exponentially distributed) delayed transition.
GSPN includes both transitions and inhibitor arcs. More easy to make representation of some systems.