Introduction to Petri Nets
P.J. Drongowski

Sources.

  James L. Peterson, Petri Nets, Computing Surveys, ACM,
  Vol. 9, No. 3, September 1977, pg. 223-252. Introduces
  Petri nets and discusses computer science applications.

  James L. Peterson, Petri net theory and the modeling of systems,
  Prentice-Hall Inc., 1981. Presents a theoretical view of
  Petri Nets with some applications.

History.

  Carl Adam Petri in 1962. Doctoral dissertation on a formal
  theory of communication between asynchronous components of
  a computer system.

  Anatol Holt, et al. in 1968. Applied nets to information
  system theory.

  MIT Project MAC. Jack Dennis and students. Modeling of
  digital systems. Later, nets inspired dataflow computer
  concept.

  Nets are particularly popular in Germany and else where in
  the European computer science community.

Petri nets.

  Petri nets can be treated as either a pure theory or as a
  model for some physical phenomenon.

  Composition (4-tuple.)
    Set of places P.
    Set of transitions T.
    Input function I.
    Output function O.

  The functions I and O relate transitions and places. I is a
  mapping from a single transition to a bag of places called
  the "input places." O is a mapping from a single transition to
  to a bag of places called the "output places" of the transition."
  (Remember, a bag is a generalization of a set which allows
  multiple occurrences of an element in a bag.) The set of places
  and set of transitions are disjoint.

  A place p is an "input place" of a transition t, if p is a
  member of the bag I(t). The notion of output place is defined
  in a similar fashion using O.

Graphs.

  Clearly, a 4-tuple defines a particular graph which is the
  pictorial representation of the corresponding Petri net. The
  following conventions are used.

    Place: Represented by a circle.

    Transition: Represented by a bar.

    I & O functions: Represented by a directed arc from a place      
    to a transition (as defined by the input places of the
    transition) or a directed are from a transition to a place
    (as defined by the output places.)

An example.

  P = { p1, p2, p3, p4, p5 }
  T = { t1, t2, t3, t4 }

  I(T) = { {p1}, {p2,p3,p5}, {p3}, {p4} }
  O(T) = { {p2,p3,p5}, {p5}, {p4}, {p2,p3} }

  See graph on pg. 11 of Peterson.

Marking.

  A marking is an assignment of tokens to the places of a Petri
  net. Tokens reside in the places. The number and position of the
  tokens will change during the execution of a net. A token is
  represented by a small dot in one of the place circles.

  A marking can be defined in one of two ways.
    * As a function from the set of places P to the non-negative
      integers, N.
    * As a vector with n elements, where n is equal to the number
      of places in the net.

  A marked Petri net is a 5-tuple consisting of the usual P,T,I,O
  tuple, plus a marking, mu.

Example (con't.)

  Mu = [ 1, 2, 0, 0, 1 ]

  Mark the example net appropriately. (See Peterson pg. 17.)

Execution.

  The behavior of a Petri net depends upon the number and position
  of the tokens in the net. A net executes by a "firing" transitions.

  When a transition fires, tokens are removed from the input places
  and new tokens are created and distributed to the output places.

  A transition is "enabled" or "fireable" if each of the input places
  has at least as many tokens in it as arcs from the place to the
  transition. (Since more than arc may lead from a place to a transition,
  multiple tokens will be needed for multiple arcs.)

    Illustrate firing with the example net.
    Give an example with multiple arcs.

  When a transition fires, all old tokens are destroyed, and one new
  token will be created for each output arc. Multiple tokens will be
  created for multiple arcs. Firing will change the marking Mu to
  a new marking, Mu'.

  Transitions will continue to fire as long as at least one enabled
  transition exists in the net. When there are not enabled transitions,
  execution "halts."

Next state function.

  To model the effect of a firing, one can define a "next state
  function" which maps a marking and a transition into a new marking.
  The new marking is the effect of firing the transition.
     Delta ( Mu, t ) -> Mu'

  Two sequences result from the execution of a Petri net.
    * Sequence of markings.
    * Sequence of transitions (which were fired.)

  If Mu' can be attained by firing t from state Mu, than Mu' is
  said to be "immediately reachable" from Mu.

  The "reachability set" of a Petri net with marking Mu is the set
  of all markings which are reachable from Mu.

Events and conditions.

  "Events" are actions that take place in a system. The occurrence
  of these events is controlled by the state of the system.

  The state of the system can be described as a set of "conditions"
  which are either "true" or "false."

  An event occurs when a certain condition holds -- the "precondition"
  for the event. The event may invalidate the precondition. Those
  conditions which hold after the event are called "postconditions."

  The presence of a token at a place can be used to assert the
  existence of a condition. Actions are associated with the transitions.

  Example: Job shop scheduling.

Concurrency and conflict.

  Petri nets easily model concurrent (parallel) behavior. Two enabled
  transitions that do not interact may fire concurrently. (See Figure
  3.7 in Peterson pg. 39 for an example.)

  Petri nets are asynchronous. Further, there is no notion of absolute
  time. A Petri net execution is a sequence of discrete events. If
  parallelism is permitted, than more than one distinct sequence of
  events may result. The partial ordering in which events occur is
  unique.

  "Non-primitive events" are those which take a finite amount of time
  to execute. A non-primitive event can be model by two transitions --
  when the event starts and finishes. (In the job shop model, machining
  operations are non-primitive because in reality, they take some amount
  of time to be performed.)

  See pg. 40 in Peterson for an example of a "conflict." If a conflict
  exists between two events, the order of execution of the events is
  indeterminate. Indeterminacy can be either benign or disastrous.
  Whether a conflict is acceptable or unacceptable depends upon some
  global property of the graph. Desirability cannot be decided
  locally.

Modeling.

  Petri nets can be used to model the control component of hardware
  units. (Peterson pg. 51 has an example of a pipelined processor.)

  An annotated Petri net can be used to model the behavior of a
  program. The annotations add:
    * Logical conditions,
    * Assignments and other imperatives
  to the basic Petri net model. The logical conditions enhance the
  semantics of the basic model to describe decisions within a program.

  Mutual exclusion and the implementation of critical sections.
  (Controlling access to a shared resource.)
  (See Peterson pg. 63.)

  Producer/consumer problem. (Produce a result; place it into a
  buffer; send "go ahead" signal; consumer reads the result.)
  Class exercise: The P/C graph in Peterson is not "safe." It
  assumes that more than one buffer is available to exchange
  information, i.e., more than one token may occupy the "buffer"
  place in the graph. Redraw the graph such that the resulting
  graph is safe. The redraw the graph to maximize concurrency.

  Question: Can we model the execution of the P/C graph on a
  sequential von-Neumann style processor? This is accomplished
  by creating a place representing the central system clock and
  sending an arc from the place to all transitions in the net.
  Note that this creates conflicts everywhere! To demonstrate
  that these conflicts do not matter, a global proof will be
  required. Hence, when translating inherently concurrent behavior
  to a synchronous, central control environment complicates any
  kind of program proof. The concurrent P/C graph was inherently
  correct, since the local topologies of the graph were all
  conflict free.

Properties.

  Safeness. A "safe net" is one in which there is a bound on the
  number of tokens in any one place, and that bound is one.

  Liveness. A transition is "potentially fireable" if there exists
  some sequence that enables it. A transition of a Petri net is
  "live" if it is potentially fireable in all reachable markings.
  (Liveness is used to prove the absence of deadlocks.)

Copyright (c) 1986 Paul J. Drongowski