Ready.


Review: "Petri Nets" (1977)

On this page, we will review/discuss the tutorial paper:

"Petri Nets"
by James L. Peterson
in ACM Computing Surveys, vol:9, No:3, Sept. 1977, pp.223-252.

Pe77 is a literature-survey about Petri nets. It is an easy-to-read tutorial, with fine pointers. This page features several quotes from the Peterson paper. The copyright notice is:

Copyright (c) 1977, Association for Computing Machinery, Inc. General permission to republish, but not for profit, all or part of this material is granted provided that ACM's copyright notice is given and that the reference is given and that reference is made to the publication, to its date of issue, and to the fact that reprinting privileges were granted by permission of the Association for Computing Machinery.






Petri Nets, for Modeling and Verifying


For systems with asynchronous and concurrent activities.

A Petri net is an abstract, formal model of information flow. The properties, concepts, and techniques of Petri nets are being developed in a search for natural, simple, and powerful methods for describing and analyzing the flow of information and control in systems, particularly systems that may exhibit asynchronous and concurrent activities.
(Pe77, p.223, emphasis added)


Modeling concurrency and constraints

The major use of Petri nets has been the modeling of systems of events in which it is possible for some events to occur concurrently but there are constraints on the concurrence, precedence, or frequency of these occurrences.
(Pe77, p.223)


Like A Flowchart, for Modeling Systems.

A Petri net, has places and transitions, as its static elements.

"The Petri net graph models the static properties of a system, much as a flowchart represents the static properties of a computer program."
(Pe77, p.223)

The token flow, on a Petri net, is the dynamical aspect.


Petri nets as a modeling tool

Petri nets are also a modeling tool. They were devised for use in the modeling of a specific class of problems, the class of discrete-event systems with concurrent or parallel events. Petri nets model systems, and particularly two aspects of systems, events and conditions, and the relationships among them.[44]
(Pe77, p.228. The reference "[44]" is by Peterson to Holt and Commoner(1970))


Properties of Petri nets useful in modeling

Petri net modeling best suits those systems, that have concurrency, and a need for mutual-exclusion, for ensuring correct operation. Peterson lists a few properties that make Petri nets useful in modeling (Pe77, pp.229-231):


Hierarchical Modeling

Pe77 had written it:

"An entire net may be replaced by a single place or transition for modeling at a more abstract level (abstraction) or places and transitions may be replaced by subnets to provide more detailed modeling (refinement)."
(Pe77, pp.230-231, emphasis added.)

Pe77 also has the figure 11 (p.231), demonstrating the capability. It is a very simple tool for modeling.


Modeling Software

Pe77 has a subsection with the name "Modeling of Software" (pp.233-234). Fig.15 shows a program fragment translated into Petri nets. The critical-section in the program is enclosed with semaphore request/release operations (P(mutex), and V(mutex), respectively).

Peterson represents the program-fragment as a Petri net place. This tells us that the code is a process (a condition) that may take some unknown amount of time, which is the time the place holds a token (the observable condition, within the Petri net abstraction).

The place that corresponds to the critical section is enclosed between two transitions, corresponding to the P(mutex) and V(mutex). This fits very well to an understanding of the Petri net transitions as being instantaneous. That is, a transition takes no time, and as a result, no two transitions may overlap in time.

In Pe77, there is a subsection with the name "Modeling of Software" (pp.233-234). On p.234, there is the figure 15 that shows a program fragment translated into Petri net representation. The critical-section in the software is enclosed with semaphore request P(mutex), and the semaphore release V(mutex) operations. Peterson approach is to represent a program-fragment as a Petri net place enclosed between two transitions. This tells us that the code may take some unknown amount of time, which is the time the place holds a token. When the transition after the place fires, that means the execution-completion event has occurred. This is one side of it. And the other side is symmetrical. As a result, the figure is representing two figures which get into their own critical sections, when the other process is not in its critical section.

When the transition after the place fires, that means the execution-completion event has occurred. This is one side of it. The other side is symmetrical, and the two sides are mutually-excluded throough an intermediate place, which has a single token. A P(mutex) operation draws the token, and makes the other side wait until its place finishes its process, and deposits the token at the end, with a V(mutex) operation, that corresponds to the transition following the place. All in all, that Fig.15 is a very clean modeling of a system of two processes, each getting into their own critical sections, when the other process is not in its critical section.


reachability-test, with independent-subnets

Petri nets are verifiable with a reachability test. Pe77 refers to a point, as concerns the modeler. i.e: The locality, the modularity of the noticeable changes:

... local changes in state, as modeled by transitions. In a complex system composed of independent asynchronously operating subparts, each part can be modeled by a Petri net. The enabling and firing of transitions are then affected by, and in turn affect only, local changes in the marking of the Petri net. Separate parts of the total system may operate independently and concurrently.
(Pe77, p.237)

VD78 is an example of a methodology with modular Petri nets - with explicit restrictions for well-formed subnets.






Further Reading

Pe77 does not list what-to-do for preserving equivalence, for a reduced subnet to stand as a (non-primitive) transition, or as a place. We may do it, either with a list of restrictions, as VD78 well-formed subnets, or reduce with known equivalences (patterns), as SARA CFA does with the SARA/UCLA strong-reduction algorithm.

Avoid an ignorant commitment to a not verifiable vagueness with ill-structured subnets.

NN73 was a paper listed by Pe77. It is about macro-nets (Macro E-nets). E-nets are an extension of Petri nets - interpreted with data, and time. It is rather trivial to read NN73, for a Petri net case.




Forum: . . (Fair Menu . . . . . Fault Report? . . . . . Remedy for your case . . . . . Noticed Plagiarism?)

Referring#: 0.0.1
Last-Revised (text) on Nov. 7, 2004 . . . published as http://www.geocities.com/ferzenr/review_1977_Peterson.htm
Written by: Ahmed Ferzan/Ferzen R Midyat-Zila (or, Earth)
Copyright (c) [2002,] 2004, 2009 Ferzan Midyat. All rights reserved.
mirror