siiky
2024/11/06
2024/11/06
2024/11/06
whitepaper,petri_nets,computation,computer_science,distributed,formal_methods
The thesis where it all started! A translation of it, actually. This is where Carl Adam Petri describes how to throw away all the "classical automata theory" into the bin and replace it with Petri nets.
In ยง2 "A Critique of the Theory of Automata" (pp. 3-5) he explains everything that's wrong with automata. For the rest of the chapter he proves why.
The main points are:
the fiction that it is at all times meaningful to speak of the total state Z of a system S at a time t
p. 3
The mishmash of the state of each and every component of a system into a single "uniform" state. In other words, the composition of several automata results in a single automaton, each state of which is a state of each of the composed automata.
A process in S can then be described by means of a function f such that Z = f(t)
p. 3
The state of an automaton is tied to "real time". This understanding of an automaton's state is not compatible with perspective, i.e., the order of transitions in history may result in different states, no matter whether those transitions are independent or not.
Because of these, automata are not appropriate to represent physical computers; trying it necessarily breaks one of the points (p. 5, (5), see points (1)-(4)).
In the most important interpretations each domain of operation can take in only an uniform limited number of objects. It suffices then, as will be seen, to allow only locations that contain exactly one object at all times. The trasition to 'locations' that at all times contain exactly n objects, which we can call quasimetri locations, is always possible by connecting ordinary locations with suitable switching elements.
p. 38
1-safe Petri nets (i.e., nets where places have at most one token at all times) are sufficient, that is, they're Turing complete (this is my interpretation, though Turing completeness only comes into play a little later in the thesis).
(The concept of time span is meaningful only in non-conflict-free nets.)
p. 79
Conflict-free nets are nets whose transitions do not share input places with other transitions, i.e., they don't "compete" for tokens with other transitions. This definition must be extended to high-level nets, because place-transitions edges may have conditions to force otherwise competing transitions to fire at mutually exclusive times.
Another way of saying it is that the order in which transitions of a conflict-free net are fired is completely irrelevant semantically: the end result will always be the same.
This is especially relevant for distributed systems (open Petri nets), however, where the previous statement is not true.
There are scenarios where we want divirging behaviors depending on history, usually with time-related operations (e.g., timeouts), but also when changing states (e.g., a user is allowed to get a coin iff they've inserted a coin but haven't used it).
More to the point of the quote above, nets of a distributed system are allowed to evolve independently of the outside world and, if a net is turned conflict-free by excluding its interface places, then once again the firing order of its transitions is semantically irrelevant.