Petri Nets 101
Petri Nets 101
In the article about finite automata, we said they are "stupid". It is very difficult to make them understand certain systems. One example was the "ABC bomb".
But there are better abstract machines out there. For example, the Petri net is more powerful than a finite automaton, and still retains a nice graphical simplicity.
The figure below shows a (very simple) finite automaton and the equivalent Petri net. In a Petri net, the places (sometimes called "states", mistakenly) are represented by circles. The transitions are rectangles or traces. The arrows are the arcs that connect transitions to places.
The distinguishing feature of the Petri net is the token, the chubby point inside the starting place. Each transition "eats" a number of input tokens (typically one) and "spits" a number of output tokens (typically one, but may be several, or none). One token per arc is the default, other quantities should be made explicit.
If a transition has input arcs (as all transitions have in the example above) it is only enabled to trigger when there are tokens to "eat".
The placement of tokens throughout the net is the marking. It represents the current state of the machine. If there is only one token, each possible marking is tied to a single place, so it is tempting to call markings and places as "states". Things are different when there are two or more tokens, so it is best to avoid the "state" jargon when dealing with Petri nets.
Still about the example above, there is a hollow rectangle, and a thin solid rectangle. This is already an extension of the original Petri net, that I introduce early because I find it very useful. The hollow rectangle is a transition that depends on some external event (and also on the availability of a token). The solid rectangle, sometimes drawn as a straight line, is a transition that triggers as soon as there are input tokens.
The net of the first example "dies" in just two movements. Once the single token falls into the final place, it can't leave. The next net is also elementary but it is a "Highlander":
Note the two hollow rectangles, meaning both transitions depend on external events to trigger.
The net below is an infinite loop that triggers all the time (busy-loop) since the transitions are (very thin) solid rectangles and therefore don't depend on any external events:
The following example shows the marking of a Petri net before and after the event is triggered. (I have copied this one from Wikipedia, in case you see a suspiciously similar net there.) Note the transition's weights. It takes an input of 3 tokens, but the output is just 2.
Until now, we haven't explored the main advantage of a Petri net, which is the power to represent concurrency. Concurrency exists when there are two or more tokens in the net, as shown in the examples below:
In both nets above, the final transition can only trigger when there are two tokens at the intermediate place(s). But each token can move there independently. To achieve the same with a finite automaton, we would need five states and a spaghetti of transitions.
The Petri net below implements an OR logical condition:
A transition does not have to "eat" or generate tokens. A transition may be a pure generator or pure consumer of tokens, as in the example below.
Ok, enough of theoretical theory. Let's play with some "practical theory". Let's reintroduce the self-service kiosk developed in the article about finite automata. The kiosk has a numeric keyboard, a "Print" button, a small screen and a printer. It prints a numbered token when the button is pressed, and the user can also query the status of the token by typing its number.
As explained in the original article, this automaton has a "bug". Either a query timeout or the printer can trigger a transition to IDLE, but the printer should do this only if it was PRINTING, and the timeout should only trigger if state is QUERY. We don't want the printer aborting a query, or a query timeout aborting a print job.
A finite automaton does not care "who" triggered a transition. So, if the printer says "go to IDLE", and the current state can transition to IDLE (as PRINTING or QUERY can), the transition will happen. Of course, we could fix this problem on code, but then we negate the advantages of using automata. We want our kiosk to stay sane efortlessly!
This particular problem is easy to solve with addition of pseudo-states. They are "fake" states in the sense that they don't map to real-world events, they are there just to block undesired transitions:
This automaton avoids undesired transitions because the printer can only transition from PRINTING to PRINTED, and this can only happen when the state is PRINTING. The same applies for the sequence QUERY-QUERIED. When the state reaches PRINTED or QUERIED, it auto-transitions to IDLE without waiting on any external event.
Now, let's model the same kiosk as a Petri net:
At first sight, this net looks like the problematic automaton. But it is problem-free because the transition needs a token input. This is equivalent to bind a transition with a previous state. For example, the "printer signal" event can only move a token to the IDLE place when the (only) token is at PRINTING place. If the token is not there, the printer event is ignored, as it should be.
This example is made up to illustrate this article, but I have a real-world example, from a real project. In my lightmeter app for photographers, I need to ask permission to use the phone camera. In Android phones, an app may be paused when the authorization dialog is shown (but it may be not paused, as well). Moreover, the authorization callback may fire before the app is resumed. The result is a relatively complicated finite automaton:
The complication stems from the concurrency of two things: the authorization response callback, and the (possible) pausing/resuming of the app. There are many possible event sequences, and the finite automaton must know them all.
The same mechanism is better modeled as a Petri net:
The camera request event generates two tokens. One token depends on the callback to move ahead. The other token goes further down, but it is "hidden" away if the app is paused. The final transition needs two tokens, that is, it triggers when two conditions are met: app not paused and request answered (in any order).
Finally, we have the Petri net representation of an "ABC bomb", whose finite automaton was a complete spaghetti. The bomb sets off when three buttons (A, B, C) are pressed in any order, but only once.
Note we have a single bidirectional transition per button. This works in a Petri net because the token enables only one direction at a time.
We can also employ a "colored Petri net", a flavor that accepts tokens of many types, or "colors". The final, set-off transition now asks one red token, one green token and one blue token, instead of 3 tokens of whatever color.
The ABC bomb is too simple to justify usage the of colored tokens. Still, the graph could be downsized from 7 places to 3.
Another useful extension, common in finite automata implementations, is the "data contraband": an optional piece of data attached with the transition. It fits well with Petri nets because it has tokens, and it feels more natural to attach data to the token. Colored tokens might represent different data types, etc.
Last but not least, using abstract machines like Petri nets allows the usage of readily-available automatic consistency checkers and code generators.