💾 Archived View for siiky.srht.site › wiki › book.wolfgang_reisig.understanding_petri_nets.gmi captured on 2023-12-28 at 15:50:44. Gemini links have been rewritten to link to archived content
⬅️ Previous capture (2023-11-04)
-=-=-=-=-=-=-
siiky
2023/09/14
2023/12/13
2023/12/13
book,programming,petri_nets
https://link.springer.com/book/10.1007/978-3-642-33278-4
https://dx.doi.org/10.1007/978-3-642-33278-4
# Further Reading
Someone who models a system does not always immediately think about components that behave like places and transitions of a Petri net. Usually, a system is first theoretically broken down into abstract components, which are later on systematically refined. All modeling techniques based on Petri nets make use of refinement and composition. In connection with colored nets [38], hierarchical concepts are introduced. Girault and Valk [29] also recommend a refining approach in their extensive book on system design with Petri nets. Introductory texts of various kinds can be found in the anthologies of the latest two Advanced Courses on Petri Nets [18], [70].
# How It Began
In the late 1950s, Carl Adam Petri, at the time a research associate at the Department for Instrumental Mathematics at the University of Bonn, Germany, thought very pragmatically about the implementation of recursive functions. After all, for such functions, it is generally not possible to predict how much space their calculations will consume. If the available resources are insufficient for a calculation, the data processing system should be expandable, to continue the calculation. This is more efficient than starting over with a larger system.
So Petri sought a system architecture that can be expanded indefinitely. Such an architecture does not have any central components, most of all no central, synchronizing clock, because every expansion enlarges the system in space. Connections to the clock would become longer, and longer cycles would demand lower clocking frequencies. At some point, the limitations of the laws of physics would have to be broken in order to further expand the system. Therefore, such an architecture inevitably has to make do without any synchronizing clocks.
In his famous dissertation “Kommunikation mit Automaten” (Communication with Automata) [56], Petri shows that it is actually possible to construct such an indefinitely expandable, asynchronous system architecture. It incorporates locally confined components communicating with each other via local interfaces.
Actions with locally confined causes and effects are the central idea of the nets proposed by Petri in [56]. Termed “Petri nets”, they became one of the most popular concepts of computer science. Only later did Petri start to use a graphical representation. Thus, the first text on Petri nets does not contain a single Petri net!
pp. 11-12
[56] Carl Adam Petri, Kommunikation mit Automaten
[29] Claude Girault, Rüdiger Valk, Petri Nets for Systems Engineering
[29] Claude Girault, Rüdiger Valk, Petri Nets for Systems Engineering
Unfortunately I still don't know german to be able to read [56].
# A Universal, Expandable Architecture
In his dissertation, Petri designed a universal computer architecture that can be expanded an arbitrary number of times. We will explain this idea using the example of a finite, but infinitely expandable stack.
About elementary system nets, i.e., the "plain tokens" nets.
[61] Lutz Priese, Harro Wimmel, "Theoretische Informatik: Petri-Netze"
[70] Wolfgang Reisig, Grzegorz Rozenberg, "Lectures on Petri Nets"
What the fuck happened here?
§ 4.7 Causal Order: distributed runs are able to represent causal order.
In Nr, the place E can be seen as a model of a resource that is used, but not used up. This forces the two actions of a and b into one of two possible orders.
If an action α generates tokens that are used by another action β, then α causally precedes β. This "causally precedes" relation is, of course, transitive: if α precedes β and β precedes γ, then α also precedes γ. Furthermore, causally precedes is irreflexive: no action causally precedes itself. Thus, causally precedes is a strict partial order.
(...) Simultaneity is transitive; independence is not.
p. 46
Two aspects of distributed runs are particularly important (...): (...) the control of the state space explosion during verification through model checking [49], [77].
[10] E. Best, César Fernández, "Non-Sequential Processes"
[23] Javier Esparza, Keijo Heljanko, "Unfoldings: A Partial-Order Approach to Model Checking"
[54] Mogens Nielsen, Gordon Plotkin, Glynn Winskel, "Petri nets, event structures and domains"
[77] Antti Valmari, "The state explosion problem"
p. 48
# Read and Write vs. Give and Take
(...)
This prompts us to try to translate programs into Petri nets and vice versa: each variable z in a program corresponds to a place pz in a system net N, and the current value w in z corresponds to a token in pz. The reading of z is simulated with a transition t and a loop between pz and t:
[Petri net drawing]
In a concurrent program with two processes, a second process in N would generate a second loop between pz and a second trasition t'.
[Petri net drawing]
In each run of N, the transitions t and t' can occur arbitrarily often, but always one after another and never independently. For example, t' may occur infinitely often and block t. This contradicts the the assumption that processes can read a variable independently without interfering with each other. If the updating of the variable z is also modeled as a loop between a transition t'' and the place pz, the updating transition t'' can be blocked by the reading transition t, in contradiction to the common assumption of concurrent programming in which the updating of a variable is never blocked by the reading of the variable. This ovservation has far-eaching consequences, some of which will become apparent in the case study of the mutual exclusion system in Chap. 20.
The translation of a system net N into a program P synchronizes the transitions of N into one or more control flows. The structure
[Petri net drawing]
of N generates (among others) a distributed run in which r and t occur independently from each other. A corresponding program would have to organize the nondeterminism between r and s and between t and s and thus force r and s under a central control.
Finally, programming languages and many other operational modeling techniques allow for multiple control flows. They are, if necessary, dynamically created or terminated, but rarely each the necessary flexibility to model, for example, the solution to the kindergarten game in Fig. 4.13.
pp. 48-49
Scenarios are sort of like common or repeatable sequences of actions ("firings", more or less). For example, in the cookie machine net, selling a cookie box may be a scenario.
(...) To form a complete scenario, the token sin the counter, the cash box and the storage would have to match in the outset and at the end. To also cover such cases, we will weaken the definition of a scenario of a system net N:
[Fig 5.4]
[Fig 5.5]
A scenario for a marking M of N is a finite partial distributed run K of N in which a part of °K and a part of K° represent the marking M. (...)
pp. 54-55
Thinking in scenarios can significantly simplify and deepen our understanding of a complex system.
[16] Jörg Desel, Gabriel Juhás, "“What Is a Petri Net?” Informal Answers for the Informed Reader"
p. 55
Harel greatly extends this idea for Live Sequence Charts [35] and integrates it into a tool.
p. 56
§ 6.3 Real Extensions
Montanari and Rossi [52] propose context places. A context place can be accessed by multiple transitions simultaneously without hindrance. They can, for instance, be used to solve the problem described in the postscript to Chapter 4: Read and Write vs. Give and Take.
[18] Jörg Desel, Wolfgang Reisig, Grzegorz Rozenberg, "Lectures on Concurrency and Petri Nets"
[52] Ugo Montanari, Francesca Rossi, "Contextual nets"
[70] Wolfgang Reisig, Grzegorz Rozenberg, "Lectures on Petri Nets"
[75] Rüdiger Valk, "Self-modifying nets, a natural extension of Petri nets"
[76] Rüdiger Valk, "Object Petri Nets"
p. 63