A Petri net is basically a both graphical and mathematical modeling tool for concurrent, distributed, parallel, nondeterministic and/or stochastic systems. It was developed by Carl Adam Petri in the early 1960's.

Generally, it consists of passive components (places) and active components (transitions) which are connected by directional weighted arcs. An arc can only connect a place with a transition or vice versa, but never two transitions or two places. The places can contain an amount tokens, defined by the capacity of the respective place. The state of the whole system is defined by the locations and amount of tokens in the places. System activity is modeled by the active components, the transitions which are able to fire, however only if they are enabled. A transition is enabled, if the places which have arcs leading to the transition are filled with the amount of tokens corresponding to the respective arcs weight. If a transition fires, an amount of tokens, as large as the weight of the respective arc leading from the place to the transition is drawn from each place. At the same time, an amount of tokens corresponding to the weights of the arcs leading to the following places is added to them. This of course implies that there can be a different number of tokens flowing to the transition than from it.

There are various special forms of Petri nets, for example a timebased Petri net, which has a certain delay specified before an enabled transition can actually fire. If the delay is randomly distributed, the net is called stochastic. If the delay distributed exponentially, the Petri net has Markov character.

A crude little ascii how a Petri net is usually drawn:

place:
___
/ \
| |
\___/
(this is supposed to be a circle. yes i know. it doesn't quite look
like one. if anybody with mad ascii powers is able to show me how to draw
convincing ascii circles, please do tell me =)
___ ___
empty, capacity 2: / 2 \ 2 tokens: / 2 \
| | |o o|
\___/ \___/
transition:
+-+
| |
| |
+-+
tiny sample Petri net
t1
+-+
-->| |--- ...............arcs
2/ | | \2
| +-+ v
___ ___
p1/ 2 \ / 2 \p2
|o o| | |
\___/ \___/
^ |
\ +-+ /
2----| |<-- 2 ..............weight
| |
+-+
t2

In the Petri net shown above, there are 2 places (p_{1}, p_{2}), 2 transitions (t_{1}, t_{2}) and 4 arcs connecting them.

t_{1} is able to fire, because the only place which has an arc leading to it (p_{1}) has as many tokens (2) as the weight of the arc. So the transition fires, and p_{1} has both tokens substracted, and p_{2} is given 2 tokens. Now t_{2} is able to fire, and so on.

The reachability graph is the base of Petri net analysis, it describes, starting with the initial marking (distribution of tokens) M_{0}. It illustrates which states a Petri net is able to reach, the set of all reachable markings is called reachability set. By examining the reachability graph it can be seen if a Petri net has deadlocks, which is a state where no transition in the whole Petri net is able to fire. In contrast, a Petri net is called safe if there are no deadlocks in the reachability graph.

Sources:

- http://pdv.cs.tu-berlin.de/~azi/petri.html
- http://www.daimi.au.dk/PetriNets/faq/
- various university lecture handouts

Further literature
- J.L. Peterson, PetriNet Theory and the Modeling of Systems, Prentice Hall, N.J., 1981
- lots of literature: http://www.daimi.au.dk/PetriNets/introductions/

Node your homework