3
$\begingroup$

In learning about Timed Automata, Coloured Petri Nets, and Process Calculi, I am wondering what the benefit is of having the Petri Net transition be a separate type of node in Petri Nets.

It seems that you can model the same stuff (eventually) using Timed Automata or Process Calculi, which both only have states and transitions (as edges, not objects). Instead of transition nodes, you could just have two types of "state", one be the Petri net place, the other be the Petri net transition. Then this second node does all it's queuing/guarding/checking of the tokens and whatnot. So I'm not sure the benefit is of having transition be a separate object in Petri Nets, when it could just be a second kind of "place" or "state".

That makes me wonder if there is a generalization of Petri nets to arbitrary number of node types (where instead of just place/transition, you have x, y, z, ...). In this sense it seems that process calculi are a generalization of Petri Nets.

$\endgroup$

2 Answers 2

2
$\begingroup$

In my experience, the duality of Petri nets is a great strength.

It forces us to specify the potential events or actions in a system (the transitions), as they may happen to individual items (the tokens), together with their preconditions and postconditions (the places). This forces us to think through what a step really means as we're denoting it, because we're denoting its effects as well.

When done right, it also matches a natural language specification. In a natural model, transitions represent predicates involving verbs of change, places represent predicates involving verbs of state, and tokens represent their subjects. For instance:

  • a transition can be a customer arrives, or switch the light off, or the light breaks, or the sun goes down;
  • a place can be a customer is waiting, or a customer is ready to pay, or the light is off, or the sun is down;
  • a token is a customer, the light, the sun.

(Further expanded in this answer.)

It greatly helps to adopt this as a naming convention for your Petri nets. You can then read the model out loud as a bunch of natural statements in natural language.

Let's compare this to models without this duality.

On one hand, we have state machine based models.

These list the system's states and connect them with arrows representing state transitions. Such a model can only be in one state at once; it does not allow the specification of individual conditions that together specify the global state, like places in a Petri net do. Of course we can draw several state machines for several subsystems and say they somehow operate together, and we can add that into the modeling technique by adding ways of specifying how submodels combine and coordinate; in Petri nets, we don't need to do that, the ability is already there. Moreover, if we want to start describing a system we don't already know, or design a system that doesn't already exist, writing down a bunch of predicates describing the relevant conditions and potential changes, like we can when specifying Petri nets, feels more natural to me, and leaves more freedom, than having to write down a specification in terms of state machines.

(That being said, when state-machine based techniques and Petri nets are extended to support modelling arbitrary processes in detail, the results may be very similar. Abstract State Machines look quite similar to algebraic Petri nets.)

On the other hand, we have process models in which the objects are steps to be taken, connected with arrows to describe the order in which they (may) happen. In my opinion, these are awful and a hindrance to good process design.

The simplest kind I've seen is just a bunch of boxes and arrows, like this:

a bunch of boxes and arrows

What does this say? After we go home, do we both feed the cat and get a glass of water? Do we choose between them? Does it vary? We have no idea. This is not a specification, it's a sketch.

Then, of course, we have flowcharts. Flowcharts, like state machines, describe completely sequential processes. Starting in the initial state, each box in the flowchart takes us to the next state, until we reach the final state. The two examples in Wikipedia:

a flowchart with a loop a flowchart with two tests

The boxes are actions; the diamonds are tests, which pick the next step based on the test result. An imperative computer works this way, and so do many completely sequential algorithms executed by something other than a computer. Flowcharts can describe them, but they are of little help in reasoning about them: in designing them, redesigning them, or proving their correctness.

A flowchart models the actions that change certain conditions, and tests that inspect certain conditions, but it doesn't model the conditions themselves. To prove correctness, we must explicitly model all of the relevant conditions, state which conditions must hold at the start, state which conditions must hold at the end, and by bookkeeping the conditions along the way, prove whether or not the algorithm is guaranteed to achieve that.

This is exactly what proof techniques for correctness of algorithms do (e.g. Hoare logic) and it will happen when turning a flowchart into a Petri net. The places will specify the relevant conditions.

So one limitation of flowcharts is that, by omitting bookkeeping on the relevant conditions, they don't support reasoning about the algorithms being specified. But at least they can specify such algorithms. Things get much worse when the algorithm in question isn't already given.

How do you design an algorithm for a given problem from scratch? You specify the initial and final conditions and you figure out a bunch of intermediate conditions and steps to bridge that gap. The designer must be explicit about the intermediate steps and how they affect the intermediate conditions. This is not usually a linear process in which the designer specifies all steps one by one from start to finish; rather, it tends to be a more unstructured refinement and reshuffling process. The exact order in which things are done may only be determined towards the end.

Or such a strict order may not exist at all. Many systems we need to describe or design aren't strictly sequential in nature; they use constructs such as pipelines and asynchronous calls, and are generally composed of various agents working together in some coordinated way, without all of the steps happening in a strictly sequential order. In interactive systems, users interacting with the system typically do not use fixed sets of sequences of actions, but they may wander through the systems in all sorts of ways. We need to be able to reason about such systems, too, and flowcharts, being sequential, cannot describe them well.

This has been recognized in industry, with lots of augmented flowcharting techniques as a result, such as

These add constructs for parallel execution and much more; some have a very rich set of constructs. However, they still only specify process steps and their compositions, without specifying the relevant pre- and postconditions. As a result, working with these formalisms still feels like programming potential solutions, rather than reasoning about the problem being solved.

This can be remedied by systematically inscribing the steps of such models with variables tested by testing steps and modified by the action steps. The variables can be used like the places in Petri nets.

You may argue that the need for such reasoning doesn't mean the results need to be visible within the process model. It can be specified separately. But in my experience, that's not what happens. Instead, people just write down the steps of their programs, with or without constructs for parallelism, and any reasoning about its correctness remains in the minds of the designers. If you're lucky, there will be a comment here and there.

This is not only true for computer programming, but it holds for all sorts of process specifications. Take, for instance, use case modeling or test case specifications. A modern interactive computer application is highly nondeterministic: at practically every point, a user has multiple different ways of continuing - for instance, multiple different buttons that can be pressed. The designer wants to leave the user as much freedom as possible. However, it must be proved that the program serves its intended purpose, and this is what use case and test specifications intend to do. What I've noticed is that in practice, these specification often take the form of a linear sequence of steps, or at best, a flowchart-like sequential algorithm. As a result, they do not describe any of the user's freedom at all. This has two risks: the implementation may end up straitjacketing the user into these overly sequential specifications, or, if it doesn't, the application may end up underspecified and undertested, and users may take untested paths with possibly disastrous consequences. You end up with a proof that a particular sequence of actions produces a particular result, without getting anything like a full proof of program correctness or completeness. All this because those writing the use case / test case specifications couldn't think of anything but a purely sequential specification. This can be remedied by using Petri nets or a similar formalism, with support for concurrency and explicit representation of intermediate application states.

Petri nets have limitations of their own, and using them won't magically solve your process design or test case specification problems, but at least it will enforce the mental hygiene of always thinking about the steps of a process together with its pre- and postconditions. In doing so, it supports a much greater degree of freedom of specification than allowed by flowchart-based techniques or simple state machines. These things are needed when reasoning about processes.

$\endgroup$
1
$\begingroup$

The state transition graph underlying a Petri Net model is called the Reachability Graph. Yes, it exists, and it is the foundation of Petri Net semantics. However, it is possible to define simple, easily understandable Petri Net models that have reachability graphs of a size and structure that no human could make sense of. They might also be graphs with an infinite number of states.

It's similar to programming languages: every conceivable algorithm or program could be written in assembly language. But there are dozens, if not hundreds, of higher level programming languages that make it easier, simpler, and faster for humans to write and understand programs, to express the algorithms and the processing they need to implement. And then a compiler or interpreter turns the high-level program into a stream of processor instructions.

Petri Nets are meant as a way for humans to create meaningful, understandable models, without drilling down to individual states and transitions. Then Petri Net tools handle the simulation and/or analysis of the models.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.