Petri net

As a consequence, the states are to be regarded as individual conditions. The (global) state of a Petri net is described by the set of conditions that hold; a transition can occur iff all enabling conditions hold, and its occurrence causes all of them to no longer hold.

This models a notion of synchronization.

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₁, p₂), 2 transitions (t₁, t₂) and 4 arcs connecting them.
t₁ is able to fire, because the only place which has an arc leading to it (p₁) has as many tokens (2) as the weight of the arc. So the transition fires, and p₁ has both tokens substracted, and p₂ is given 2 tokens. Now t₂ 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₀. 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