Among many of the fascinating things that we computer scientists do with graphs
is use them as a visual representation of computing devices. There are many subtle problems that can come up in all sorts of contexts where being able to see what’s going on can make a huge difference. Graphs are, generally, the preferred metaphor for most computing tasks. For example, think of finite state machines, flowcharts, UML diagrams, etc.
One of the most interesting cases of this for one of the biggest programming problems today is visual representations of concurrency. Concurrent program is incredibly hard, and making a concurrency regime correct is a serious challenge – communicating that regime and its properties to another developer is even harder.
Which brings us to todays topic, Petri nets. Actually, I’m probably going to spend a couple of days writing about Petri nets, because they’re fun, and there are a lot of interesting variations. The use of Petri nets really isn’t just an academic exercise – they are seriously used by people in a lot of real, significant fields – for one example, they’re very commonly used to specify behaviors of network communication protocols.
Today, I’m going to introduce the simplest version of a Petri net – the basic, simple, Petri net. A Petri net is a bipartite, weighted digraph used as a representation of concurrent computation – in particular, the coordination aspects of multi-threaded computations. The two sets of nodes in a PetriNet are called places (drawn as circles or ovals) and transitions (drawn as narrow rectangles). Since it’s a bipartite graph, there are edges from places to transitions; and transitions to places, but never places to places or transitions to transitions. So for example, the below is a petri-net.
Places are containers for tokens, which are inputs or results of computations. An edge carries tokens from a place to a transition, or a transition to a place. Transitions represent computations which can occur. The computation associated with a transition is not explicitly represented in the
net – the net only models concurrency and coordination.
In addition to the basic Petri-net graph, there is a marking, which assigns a number of tokens to each place in the graph. The marking represents the current state of a computation in the net. Given a list of places [p1, …, pn], you can represent
a marking of a Petri net using an integer vector, where each position contains the number of tokens in the corresponding place.
The way that a petri-net operates is by firing transitions. Each step, the net non-deterministically selects and fires an enabled transition. A transition is enabled when all of the places that have edges to it have a number of tokens greater than or equal to the weight of their edge. So in our example, transition “y” can fire when place “d” has at least 2 tokens, and “e” has at least 1 token.
When a transition fires, for each incoming edge, it removes the edge’s weight in tokens from the edges source place; and for each outgoing edge, it adds the edges weight in tokens to the target place. So, in our example, if “d” has 3 tokens, “e” had 4 tokens, “g” had 1 token, we could fire “y”, which would leave “d” with 1 token, “e” with 3 tokens, and “g” with 3 tokens. There’s no necessary relation between
the number of tokens that come in to the transition and the number of tokens that are output by the transition.
For an extremely simple example of how Petri nets are used, look at the example to the right, which illustrates a common model of concurrency, called fork-join. In a fork-join computation, you have one primary thread, which creates other threads that execute in parallel. Then at the end, the main thread stops and waits until the other threads are finished before it proceeds. In our fork-join Petri-net, all of the edges have weight 1, and I’ve color-coded the places for the three threads. The green places are the original main thread. The main thread first forks off the red thread; then it forks off the blue thread. Then each of the thread goes off and does its own computation (the color-coded transitions), and then all meet up at the bottom, black transition.
The computation starts off with a marking with one token in “Start”, and no tokens anywhere else. Since the one transition adjacent to start is the only selected transition, it fires, which removes the token from start, and puts one token each in places a and f. Then it has a choice – it can fire either the red-thread transition from f, or the green thread transition from a. If it fires the green, then there will be one token each in b, d, and f, as shown in the diagram.
After that, It will continue firing transitions, until it reaches the marking shown below, where, there’s a token in each of c, e, and g. No matter what transitions it fires, no matter what order it fires them in, it must eventually wind up in this state. This fires the last transition, and then the only token is in “End”. Once that happens, there are no more selected transitions, and since there are no selected transitions, the computation is over.
Those are some nice-looking diagrams, Mark. What program are you using to create them?
Yes, Petri nets are indeed pretty fascinating and useful. There are a couple of ways in which they’re a little less convenient than the more familiar kinds of Finite State Machines, though. The one I keep running into is where places should (according to the application logic) be mutually exclusive but there’s no good way to express that without creating a big spaghetti mess of interconnected transitions and places just to drain extraneous tokens.
Indeed, very interesting. The shading suggest Ommnigraffle on the mac?
I look forward to future discussions. I have been building a kinda dataflow system for some time now. One of the problems I have is representing and actually handling what I think is called (at least, I call it that), the rendezvous problem: making sure that any given multi-term computation happens when all its inputs are satisfied with data items tagged as being of the same generation. At least, that is where I am at present. but I have a hard time diagramming it in a way that lets me see correctness. Systems are constructed by editing their flow graphs, and in a way I am searching for a representation I can use as the design/run tool that has this property. petri heading this way?
look at his ponytail, the guy’s a linux user. š
are the graphs made with graphviz?
I believe MarK uses OmniGraffle on the Mac. Read the comments in this blog entry:
http://scientopia.org/blogs/goodmath/2007/08/directed-graphs
lanwolf: your problem is exactly the kind of thing Petri nets are for:
They allow you to built a completely dataflow-oriented model of your system.
They allow you to draw the system model as a diagram, if it’s small enough.
They also allow you to simulate execution step by step (you’ll see the tokens hop around in the diagram). In practice many potential problems in the model will not be easily found by visual inspection of the diagram but may be found by simulating the system until you arrive at a situation you know shouldn’t be possible.
They allow static analysis, i.e. all kinds of properties you’d like to know about your system can be decided; e.g. boundedness (whether the number of tokens always stays below some fixed number) or liveness (whether the system will never block). There is a lot of theory and software for this.
The price for being able to do static analysis is that the formalism isn’t very expressive. Take your problem, for instance: it looks exactly like a Petri net problem, except that standard Petri nets cannot express the notion of “being of the same generation”. If you just want to model what happens to a single generation, or a fixed number of generations, standard Petri nets will do. If you want to describe the interaction of an arbitrary number of generations, they don’t. So what Petri net people do is add information to the tokens; in your case, a “generation id”. (I have been involved in developing a Petri net editor and simulator that happens to do exactly that.) Now most of the static analysis algorithms will no longer work, but we can still diagram and visually simulate our models.
In short, wait until you read Mark’s followup articles.
Hi Mark,
Thanks for the posts on Petri Nets.
I am still amazed at how powerful “networking” can be.
I don’t agree with putting Petri nets into the data-flow corner, because the ordinary Petri nets describe their tokens as anonymous. Even with higher order Petri nets modelling data flow is not what they were ment for. Securing access to resources and describe the use of it ist still the domain.
You should take a look at reference nets RENEW, its a nice tool for rapid developing concurrent systems with a net formalism directly coupled to java. This means, that you can use java as the inscription language.
fsimmi: Agreed, Petri nets aren’t particularly associated with “dataflow” as that concept is explained in Wikipedia. And agreed once more that the purpose of a Petri net model is usually to identify and resolve on concurrency issues such as mutual exclusion, while the details of data are ignored as far as possible.
The higher-order Petri nets and Renew object nets you mention are types of coloured Petri nets, which Mark will devote a separate article to.
Actually, a *colored* Petri Net (which MarkCC proposes to discuss soon) allows you to overcome the anonymity issue. If you regard each of the correlated sets of tokens as having the same (dynamic, anonymous) “type”, then you’re set.
Dang it. Should’ve phrased that more delicately. I suppose that what I’ve described is an extension of CPNs, where “type” can be understood as applying to a set of tokens, across the inputs to a transition. It’s got some issues, some of which are ameliorated in a data-flow regime.
Concurrency and sequential dynamics are important in mathematical models of actual organisms. Here’s an exemplary recent paper.
Large-scale prediction and verification of indirect regulatory interactions in model organisms
Authors: Koon-Kiu Yan, Sergei Maslov, Ilya Mazo, Anton Yuryev
Comments: 17 pages, 6 figures, including supplementary materials
Subjects: Quantitative Methods (q-bio.QM); Molecular Networks (q-bio.MN)
We develop a network-based algorithm to predict and verify indirect regulatory interactions in a large-scale genetic regulatory network. Indirect regulations are important as they constitute the majority of experimental data. Our approach is based on the network topology and can be easily incorporated using a matrix formalism. The essence of the method is to extend the transitivity of indirect regulations (i.e. A regulates B and B regulates C implies A regulates C) to longer cascades and effectively take care of the signs of the regulations. This algorithm is tailored for large and heavily interconnected networks, which are of growing importance due to the accruement of data from high-throughput experiments. We apply the algorithm to the regulatory networks of Homo sapiens, Saccharomyces cerevisiae, Arabidopsis thaliana and Drosophila melanogaster, resulting in novel predictions with calibrated reliability.
can u name me 3 specific examples of systems that u think are good candidates for being modeled using Petri Net…n please help me explauned ur answer…