Petri net

From Wikipedia, the free encyclopedia

A Petri net (also known as a place/transition net or P/T net) is one of several mathematical modeling languages for the description of discrete distributed systems. A Petri net is a directed bipartite graph, in which the nodes represent transitions (i.e. discrete events that may occur), places (i.e. conditions), and directed arcs (that describe which places are pre- and/or postconditions for which transitions). Petri nets were invented in August 1939 by Carl Adam Petri – at the age of 13 – for the purpose of describing chemical processes.^[1]

Like industry standards such as UML activity diagrams, BPMN and EPCs, Petri nets offer a graphical notation for stepwise processes that include choice, iteration, and concurrent execution. Unlike these standards, Petri nets have an exact mathematical definition of their execution semantics, with a well-developed mathematical theory for process analysis.

(a) Petri net trajectory example

1 Petri nets basics
2 Formal definition and basic terminology
- 2.1 Syntax
- 2.2 Execution semantics
3 Variations on the definition
4 Formulation in terms of vectors and matrices
5 Mathematical properties of Petri nets
6 Extensions
7 Main Petri net types
8 Other models of concurrency
9 Application areas
10 See also
11 References
12 Further reading
13 External links

[edit] Petri nets basics

A Petri net consists of places, transitions, and directed arcs. Arcs run between places and transitions, never between places or between transitions. The places from which an arc runs to a transition are called the input places of the transition; the places to which arcs run from a transition are called the output places of the transition.

Places may contain any non-negative number of tokens. A distribution of tokens over the places of a net is called a marking. A transition of a Petri net may fire whenever there is a token at the end of all input arcs; when it fires, it consumes these tokens, and places tokens at the end of all output arcs. A firing is atomic, i.e., a single non-interruptible step.

Execution of Petri nets is nondeterministic: when multiple transitions are enabled at the same time, any one of them may fire. If a transition is enabled, it may fire, but it doesn't have to.

Since firing is nondeterministic, and multiple tokens may be present anywhere in the net (even in the same place), Petri nets are well suited for modeling the concurrent behavior of distributed systems.

[edit] Formal definition and basic terminology

The following formal definition is loosely based on (Peterson 1981). Many alternative definitions exist.

[edit] Syntax

A Petri net graph (called Petri net by some, but see below) is a 3-tuple $(S,T,W)\!$ , where

$S$ is a finite set of places
$T$ is a finite set of transitions
$S$ and $T$ are disjoint, i.e. no object can be both a place and a transition
$W: (S \times T) \cup (T \times S) \to \mathbb{N}$ is a multiset of arcs, i.e. it defines arcs and assigns to each arc a non-negative integer arc multiplicity; note that no arc may connect two places or two transitions.

The flow relation is the set of arcs: $F = \{ (x,y) \mid W(x,y) > 0 \}$ . In many textbooks, arcs can only have multiplicity 1, and they often define Petri nets using $F$ instead of $W$ .

A Petri net graph is a bipartite multidigraph $(S \cup T, F)$ with node partitions $S$ and $T$ .

The preset of a transition t is the set of its input places: ${}^{\bullet}t = \{ s \in S \mid W(s,t) > 0 \}$ ; its postset is the set of its output places: $t^{\bullet} = \{ s \in S \mid W(t,s) > 0 \}$

A marking of a Petri net (graph) is a multiset of its places, i.e., a mapping $M: S \to \mathbb{N}$ . We say the marking assigns to each place a number of tokens.

A Petri net (called marked Petri net by some, see above) is a 4-tuple $(S,T,W,M_0)\!$ , where

$(S, T, W)$ is a Petri net graph;
$M 0$ is the initial marking, a marking of the Petri net graph.

[edit] Execution semantics

The behavior of a Petri net is defined as a relation on its markings, as follows.

Note that markings can be added like any multiset: $M + M' \ \stackrel{D}{=}\ \{ s \to M(s) + M'(s) \mid s \in S \}$

The execution of a Petri net graph $G = (S,T,W)\!$ can be defined as the transition relation $\to_{G}$ on its markings, as follows:

for any $t$ in $T$ : $M \to_{G,t} M' \ \stackrel{D}{\Leftrightarrow}\ \exists M'': S \to \mathbb{N}: M = M'' + \textstyle\sum_{s \in S} W(s,t) \ \wedge\ M' = M'' + \textstyle\sum_{s \in S} W(t,s)$
$M \to_{G} M' \ \stackrel{D}{\Leftrightarrow}\ \exists t \in T: M \to_{G,t} M'$

In words:

firing a transition $t$ in a marking $M$ consumes $W (s, t)$ tokens from each of its input places $s$ , and produces $W (t, s)$ tokens in each of its output places $s$
a transition is enabled (it may fire) in $M$ if there are enough tokens in its input places for the consumptions to be possible, i.e. iff $\forall s: M(s) \geq W(s,t)$ .

We are generally interested in what may happen when transitions may continually fire in arbitrary order.

We say that a marking $M'$ is reachable from a marking $M$ in one step if $M \to_G M'$ ; we say that it is reachable from $M$ if $M {\to_G}^* M'$ , where ${\to_G}^*$ is the transitive closure of $\to_G$ ; that is, if it is reachable in 0 or more steps.

For a (marked) Petri net $(S,T,W,M_0)\!$ , we are interested in the firings that can be performed starting with the initial marking $M 0$ . Its set of reachable markings is the set $R(N) \ \stackrel{D}{=}\ \{ M' \mid M_0 {\to_{(S,T,W)}}^* M' \}$

The reachability graph of $N$ is the transition relation $\to_G$ restricted to its reachable markings $R (N)$ . It is the state space of the net.

A firing sequence for a Petri net with graph $G$ and initial marking $M 0$ is a sequence of transitions $\vec \sigma = \langle t_{i_1} \ldots t_{i_n} \rangle$ such that $M_0 \to_{G,t_{i_1}} M_1 \wedge \ldots \wedge M_{n-1} \to_{G,t_{i_n}} M_n$ . The set of firing sequences is denoted as $L (N)$ .

[edit] Variations on the definition

As already remarked, a common variation is to disallow arc multiplicities and replace the bag of arcs W with a simple set, called the flow relation, $F \subseteq (S \times T) \cup (T \times S)$ . This limits expressive power, but not significantly: multi-arcs are rarely used in practice, while in theoretical considerations, allowing them rarely makes a significant difference.

Another common variation, e.g. in , e.g. Desel and Juhás (2001)^[2], is to allow capacities to be defined on places. This is discussed under extensions below.

[edit] Formulation in terms of vectors and matrices

The markings of a Petri net $(S,T,W,M_0)\!$ can be regarded as vectors of nonnegative integers of length $| S |$ .

Its transition relation can be described as a pair of $| S |$ by $| T |$ matrices:

$W -$ , defined by $\forall s,t: W^-[s,t] = W(s,t)$
$W +$ , defined by $\forall s,t: W^+[s,t] = W(t,s).$

Then their difference

$W T = W + - W -$

can be used to describe the reachable markings in terms of matrix multiplication, as follows. For any sequence of transitions $w$ , write $o (w)$ for the vector that maps every transition to its number of occurrences in $w$ . Then, we have

$R(N) = \{ M \mid \exists w: M = M_0 + W^T \cdot o(w) \wedge w \!$ is a firing sequence of $N \}\!$ .

Note that it must be required that $w$ is a firing sequence; allowing arbitrary sequences of transitions will generally produce a larger set.

(b) Petri net Example

$W^{+}=\begin{bmatrix} * & t1 & t2 \\ p1 & 0 & 1 \\ p2 & 1 & 0 \\ p3 & 1& 0 \\ p4 & 0 & 1 \end{bmatrix}$

$W^{-}=\begin{bmatrix} * & t1 & t2 \\ p1 & 1 & 0 \\ p2 & 0 & 1 \\ p3 & 0 & 1 \\ p4 & 0 & 0 \end{bmatrix}$

$W^T=\begin{bmatrix} * & t1 & t2 \\ p1 & -1 & 1 \\ p2 & 1 & -1 \\ p3 & 1 & -1 \\ p4 & 0 & 1 \end{bmatrix}$

$M_{0}=\begin{bmatrix} 1 & 0 & 2 & 1 \end{bmatrix}$

[edit] Mathematical properties of Petri nets

One thing that makes Petri nets interesting is that they provide an interesting balance between modeling power and analyzability: many things one would like to know about concurrent systems can be automatically determined for Petri nets, although some of those things are very expensive to determine in the general case. Several subclasses of Petri nets have been studied that can still model interesting classes of concurrent systems, while these problems become easier.

An overview of such decision problems, with decidability and complexity results for Petri nets and some subclasses, can be found in Esparza and Nielsen (1995)^[3].

[edit] Reachability

The reachability problem for Petri nets is to decide, given a Petri net $N$ and a marking $M$ , whether $M \in R(N)$ .

Clearly, this is a matter of walking the reachability graph defined above, until either we reach the requested marking or we know it can no longer be found. This is harder than it may seem at first: the reachability graph is generally infinite, and it is not easy to determine when it is safe to stop.

In fact, this problem was shown to be EXPSPACE-hard^[4] years before it was shown to be decidable at all (Mayr, 1981). Papers continue to be published on how to do it efficiently^[5]

While reachability seems to a be a good tool to find erroneous states, for practical problems the constructed graph usually has far too many states to calculate. To alleviate this problem, linear temporal logic is usually used in conjunction with the tableau method to prove that such states cannot be reached. LTL uses the semi-decision technique to find if indeed a state can be reached, by finding a set of necessary conditions for the state to be reached then proving that those conditions cannot be satisfied.

[edit] Liveness

Petri nets can be described as having different levels of liveness $L 0 - L 4$ . While the levels of liveness are defined on transitions within the Petri net, the Petri net itself is considered $L k$ live if and only if every transition within it is $L k$ live.

A Petri net $(N, M 0)$ 's transition $t$ is

$L 0$ live, or dead, if and only if it can not be fired, i.e. it is not in any firing sequence $\vec \sigma$ where $\vec \sigma \in L(N,M_0)$
$L 1$ live if and only if it can possibly be fired, i.e. it is in a firing sequence $\vec \sigma$ where $\vec \sigma \in L(N,M_0)$
$L 2$ live if and only if for any k positive whole number, t can be fired at least k times in a firing sequence $\vec \sigma$ where $\vec \sigma \in L(N,M_0)$
$L 3$ live if and only if there exists a firing sequence $\vec \sigma \in L(N,M_0)$ where $t$ is fired infinitely
$L 4$ live or simply live if and only if in any reachable state M (i.e. $\forall M \in R(N,M_0)$ ), $t$ is $L 1$ live

Note that these are increasingly stringent requirements such that if a transition is $L 3$ live for example, it is automatically $L 1$ and $L 2$ live as well. As an example, (b) Example Petri net is live with the given initial state, but with a different (e.g. totally empty) initial state, all of its transitions are dead.

In computer programming and other applications, the property of liveness of a Petri net is used to model that the system can never lock up.

[edit] Boundedness

Reachability graph of (a) Petri net Example if the net is 2-bounded. In this case, it can only have a maximum of 9 (or

32

) states.

A Petri net is inherently $k$ -bounded if in no reachable state can at any place contain more than $k$ tokens. A Petri net is safe if it is 1-bounded. Naturally, the initial $M 0$ marking is also restricted by the boundedness. Note that a Petri net is inherently bounded if and only if all its reachability graphs (i.e reachability graphs with all possible starting states) all have a finite number of states.

Formally, $K : S \to \mathbb{N^+}$ is a set of capacity restrictions, which assigns to each place $s \in S$ some positive number $n \in \mathbb{N^+}$ denoting the maximum number of tokens that can occupy that place. A net in which each of its places has some capacity $k$ , is known as an 'inherently $k$ -bounded' Petri net.

Boundedness is decidable by looking at covering, by constructing the Karp-Miller Tree. In computer programming and other applications, the property of boundedness of a Petri net is used to model limits on available system resources such as CPUs and I/O buses.

Example place-transformation. The grey place that was originally inherently 2-bounded has been transformed into two places: a grey original, and a counter place

Boundedness of a certain place in an inherently bounded net can be mimicked in a non-inherently bounded net by doing a place-transformation, where a new place (called counter-place) is created, and all transitions that put x tokens to the original place take x tokens from the counter-place, and all transitions that take away x tokens from the original place put x tokens to the counter-place. The number of tokens in $M 0$ must now satisfy the equation place+counter-place=boundedness. Thus, doing a place-transformation for all places in a bounded net, and restricting the starting state $M 0$ to conform to the above noted equality, a bounded net can easily be transformed to a non-bounded net. Therefore any analysis that is used on inherently non-bounded nets can be used on bounded nets (but not the other way around).

[edit] Extensions

There are many extensions to Petri nets. Some of them are completely backwards-compatible (e.g. coloured Petri nets) with the original Petri net, some add properties that cannot be modelled in the original Petri net (e.g. timed Petri nets). If they can be modelled in the original Petri net, they are not real extensions, instead, they are convenient ways of showing the same thing, and can be transformed with mathematical formulas back to the original Petri net, without losing any meaning. Extensions that cannot be transformed are sometimes very powerful, but usually lack the full range of mathematical tools available to analyse normal Petri nets.

The term high-level Petri net is used for many Petri net formalisms that extend the basic P/T net formalism; this includes coloured Petri nets, hierarchical Petri nets, and all other extensions sketched in this section. The term is also used specifically for the type of coloured nets supported by CPN Tools.

A short list of possible extensions:

In a standard Petri net, tokens are indistinguishable. In a Coloured Petri Net, every token has a value.^[6] In popular tools for coloured Petri nets such as CPN Tools, the values of tokens are typed, and can be tested (using guard expressions) and manipulated with a functional programming language. A subsidiary of coloured Petri nets are the well-formed Petri nets, where the arc and guard expressions are restricted to make it easier to analyse the net.

Another popular extension of Petri nets is hierarchy: Hierarchy in the form of different views supporting levels of refinement and abstraction were studied by Fehling. Another form of hierarchy is found in so-called object Petri nets or object systems where a Petri net can contain Petri nets as its tokens inducing a hierarchy of nested Petri nets that communicate by synchronisation of transitions on different levels. See [3] for an informal introduction to object Petri nets.

A Vector Addition System with States (VASS) can be seen as a generalisation of a Petri net. Consider a finite state automaton where each transition is labelled by a transition from the Petri net. The Petri net is then synchronised with the finite state automaton, i.e., a transition in the automaton is taken at the same time as the corresponding transition in the Petri net. It is only possible to take a transition in the automaton if the corresponding transition in the Petri net is enabled, and it is only possible to fire a transition in the Petri net if there is a transition from the current state in the automaton labelled by it. (The definition of VASS is usually formulated slightly differently.)

Prioritised Petri nets add priorities to transitions, whereby a transition cannot fire, if a higher-priority transition is enabled (i.e. can fire). Thus, transitions are in priority groups, and e.g. priority group 3 can only fire if all transitions are disabled in groups 1 and 2. Within a priority group, firing is still non-deterministic.

The non-deterministic property has been a very valuable one, as it lets the user abstract a large number of properties (depending on what the net is used for). In certain cases, however, the need arises to also model the timing, not only the structure of a model. For these cases, timed Petri nets have evolved, where there are transitions that are timed, and possibly transitions which are not timed (if there are, transitions that are not timed have a higher priority than timed ones). A subsidiary of timed Petri nets are the stochastic Petri nets that add nondeterministic time through adjustable randomness of the transitions. The exponential random distribution is usually used to 'time' these nets. In this case, the nets' reachability graph can be used as a Markov chain.

Dualistic Petri Nets (dP-Nets) is a Petri Net extension developed by E. Dawis, et al. ^[7] to better represent real-world process. dP-Nets balance the duality of change/no-change, action/passivity, (transformation) time/space, etc., between the bipartite Petri Net constructs of transformation and place resulting in the unique characteristic of transformation marking, i.e., when the transformation is "working" it is marked. This allows for the transformation to fire (or be marked) multiple times representing the real-world behavior of process throughput. Marking of the transformation assumes that transformation time must be greater than zero. A zero transformation time used in many typical Petri Nets may be mathematically appealing but impractical in representing real-world processes. dP-Nets also exploit the power of Petri Nets' hierarchical abstraction to depict Process architecture. Complex process systems are modeled as a series of simpler nets interconnected through various levels of hierarchical abstraction. The process architecture of a packet switch is demonstrated in ^[8], where development requirements are organized around the structure of the designed system. dP-Nets allow any real-world process, such as computer systems, business processes, traffic flow, etc., to be modeled, studied, and improved.

There are many more extensions to Petri nets, however, it is important to keep in mind, that as the complexity of the net increases in terms of extended properties, the harder it is to use standard tools to evaluate certain properties of the net. For this reason, it is a good idea to use the most simple net type possible for a given modelling task.

[edit] Main Petri net types

Petri net types graphically

There are six main types of petri net:

State Machine (SM) - here, every transition has one incoming arc, and one outgoing arc. This means, that there can not be concurrency, but there can be conflict (i.e. Where should the token from the place go? To one transition or the other?). Mathematically: $\forall t\in T: |t\bullet|=|\bullet t|=1$
Marked Graph (MG) - here, every place has one incoming arc, and one outgoing arc. This means, that there can not be conflict, but there can be concurrency. Mathematically: $\forall s\in S: |s\bullet|=|\bullet s|=1$
Free choice (FC) - here, an arc is either the only arc going from the place, or it is the only arc going to a transition. I.e. there can be both concurrency and conflict, but not at the same time. Mathematically: $\forall s\in S: (|s\bullet|\leq 1) \vee (\bullet (s\bullet)=\{s\})$
Extended free choice (EFC) - a Petri net that can be transformed into an FC.
Asymmetric choice (AC) - concurrency and conflict (in sum, confusion), but not asymmetrically. Mathematically: $\forall s_1,s_2\in S: (s_1\bullet \cap s_2\bullet\neq 0) \to [(s_1\bullet\subseteq s_2\bullet) \vee (s_2\bullet\subseteq s_1\bullet)]$
Multiple Asymmetric choice (MAC) - multiple concurrency and conflict (in sum, multiple confusion). Mathematically: for a set |P|=k, $\forall t\in T$ exist a subset $\bullet t,$ and $\bullet T$ contains all subset and is the Power Set 2^k without the empty subset
Petri Net (PN) - confusion is allowed (i.e. everything is allowed)

[edit] Other models of concurrency

Other ways of modelling concurrent computation have been proposed, including process algebra, the actor model, and the theory of traces^[9]. Different models provide tradeoffs of concepts such as compositionality, modularity, and locality.

An approach to relating some of these models of concurrency is proposed in the chapter by Winskel and Nielsen^[10].

[edit] Application areas

[edit] See also

[edit] References

^ Carl Adam Petri and Wolfgang Reisig (2008) Petri net. Scholarpedia, 3(4):6477 [1]
^ Desel, Jörg and Juhás, Gabriel "What Is a Petri Net? Informal Answers for the Informed Reader", Hartmut Ehrig et al. (Eds.): Unifying Petri Nets, LNCS 2128, pp. 1-25, 2001. [2]
^ Decidability issues for Petri nets - a survey, by Javier Esparza and Mogens Nielsen, in: Bulletin of the EATCS, 1994. Revised, 1995.
^ Lipton, R. "The Reachability Problem Requires Exponential Space", Technical Report 62, Yale University, 1976]
^ P. Küngas. Petri Net Reachability Checking Is Polynomial with Optimal Abstraction Hierarchies. In: Proceedings of the 6th International Symposium on Abstraction, Reformulation and Approximation, SARA 2005, Airth Castle, Scotland, UK, July 26-29, 2005]
^ "Very Brief Introduction to CP-nets", Department of Computer Science, University of Aarhus, Denmark
^ Dawis, E. P., J. F. Dawis, Wei-Pin Koo (2001). Architecture of Computer-based Systems using Dualistic Petri Nets. Systems, Man, and Cybernetics, 2001 IEEE International Conference on Volume 3, 2001 Page(s):1554 - 1558 vol.3
^ Dawis, E. P. (2001). Architecture of an SS7 Protocol Stack on a Broadband Switch Platform using Dualistic Petri Nets. Communications, Computers and signal Processing, 2001. PACRIM. 2001 IEEE Pacific Rim Conference on Volume 1, 2001 Page(s):323 - 326 vol.1
^ Antoni Mazurkiewicz, "Introduction to Trace Theory", in The Book of Traces V. Diekert, G. Rozenberg, eds. World Scientific, Singapore (1995) pp 3-67.
^ G. Winskel, M. Nielsen. "Models for Concurrency". Handbook of Logic and the Foundations of Computer Science, vol. 4, pages 1-148, OUP.

[edit] Further reading

Cardoso, Janette; Heloisa Camargo. Fuzziness in Petri Nets. Physica-Verlag. ISBN 3-7908-1158-0.
Jensen, Kurt. Coloured Petri Nets. Springer Verlag. ISBN 3-540-62867-3.
Котов, Вадим (1984). Сети Петри (Petri Nets, in Russian). Наука, Москва.
Pataricza, András (2004). Formális moódszerek az informatikában (Formal methods in informatics). TYPOTEX Kiadó. ISBN 963-9548-08-1.
Peterson, James L. (1977). "Petri Nets". ACM Computing Surveys 9 (3): 223–252.
Peterson, James Lyle (1981), Petri Net Theory and the Modeling of Systems, Prentice Hall, ISBN 0-13-661983-5
Petri, Carl A. (1962). Kommunikation mit Automaten. Ph. D. Thesis. University of Bonn.
Petri, Carl Adam; Reisig, Wolfgang. "Petri net". Scholarpedia 3(4):6477. http://www.scholarpedia.org/article/Petri_net. Retrieved on 2008-07-13.
Reisig, Wolfgang. A Primer in Petri Net Design. Springer-Verlag. ISBN 3-540-52044-9.
Riemann, Robert-Christoph. Modelling of Concurrent Systems: Structural and Semantical Methods in the High Level Petri Net Calculus. Herbert Utz Verlag. ISBN 3-89675-629-X.
Störrle, Harald. Models of Software Architecture - Design and Analysis with UML and Petri-Nets. Books on Demand. ISBN 3-8311-1330-0. With courtesy of the author, freely available online.
Zhou, Mengchu; Frank Dicesare. Petri Net Synthesis for Discrete Event Control of Manufacturing Systems. Kluwer Academic Publishers. ISBN 0-7923-9289-2.
Zhou, Mengchu; Kurapati Venkatesh. Modeling, Simulation, & Control of Flexible Manufacturing Systems: A Petri Net Approach. World Scientific Publishing. ISBN 981-02-3029-X.

[edit] External links

Wikimedia Commons has media related to: Petri nets

[0] Carl Adam Petri and Wolfgang Reisig (2008) Petri net. Scholarpedia, 3(4):6477 [1]

[1] Desel, Jörg and Juhás, Gabriel "What Is a Petri Net? Informal Answers for the Informed Reader", Hartmut Ehrig et al. (Eds.): Unifying Petri Nets, LNCS 2128, pp. 1-25, 2001. [2]

[2] Decidability issues for Petri nets - a survey, by Javier Esparza and Mogens Nielsen, in: Bulletin of the EATCS, 1994. Revised, 1995.

[3] Lipton, R. "The Reachability Problem Requires Exponential Space", Technical Report 62, Yale University, 1976]

[4] P. Küngas. Petri Net Reachability Checking Is Polynomial with Optimal Abstraction Hierarchies. In: Proceedings of the 6th International Symposium on Abstraction, Reformulation and Approximation, SARA 2005, Airth Castle, Scotland, UK, July 26-29, 2005]

[5] "Very Brief Introduction to CP-nets", Department of Computer Science, University of Aarhus, Denmark

[6] Dawis, E. P., J. F. Dawis, Wei-Pin Koo (2001). Architecture of Computer-based Systems using Dualistic Petri Nets. Systems, Man, and Cybernetics, 2001 IEEE International Conference on Volume 3, 2001 Page(s):1554 - 1558 vol.3

[7] Dawis, E. P. (2001). Architecture of an SS7 Protocol Stack on a Broadband Switch Platform using Dualistic Petri Nets. Communications, Computers and signal Processing, 2001. PACRIM. 2001 IEEE Pacific Rim Conference on Volume 1, 2001 Page(s):323 - 326 vol.1

[8] Antoni Mazurkiewicz, "Introduction to Trace Theory", in The Book of Traces V. Diekert, G. Rozenberg, eds. World Scientific, Singapore (1995) pp 3-67.

[9] G. Winskel, M. Nielsen. "Models for Concurrency". Handbook of Logic and the Foundations of Computer Science, vol. 4, pages 1-148, OUP.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]