Counted Petri Nets, and Useless Protocol Specification Tools

There's one variant of Petri nets, called counted Petri nets, which I'm fond of for personal reasons. As Petri net variants go, it's a sort of sloppy but simple one, but as I said, I'm fond of it.

As a warning, there's a bit of a diatribe beneath the fold, as I explain why I know about this obscure, strange Petri net variant.

My first project in grad school involved building a simulator for a network protocol specification language called Estelle. Estelle is, as I like to describe it, a formal specification language with absolutely no useful formal qualities.

The problem with Estelle is that it's based on something called augmented heirarchical communicating finite state machines. Communicating FSMs are fine; heirarchical FSMs are fine. They're not my favorite model, but they're useful, valid techniques for describing things.

Where Estelle got into trouble was the "augmented" part. What that meant is that
each FSM had a bunch of data associated with it, and each transition had a set of guard conditions and effect code written in Pascal. So a state transition could run an arbitrary Pascal program that altered the state of the FSM without changing the visible FSM state; and that change could affect the guard conditions determining what transitions could occur later. So every Estelle transition is basically unlimited in its effects. Any analysis that tried to answer questions about a specification that used this capability generally reduced to the halting problem; but you really needed to use it to represent the state
involved in communication protocols!

Anyway, I got roped into this, and I was supposed to port a huge Smalltalk simulator of Estelle to C. Only I'd never really used Smalltalk. I knew the theory of it, but I'd never had access to a real Smalltalk interpreter. So as a way to learn Smalltalk, and to get into the swing of this protocol specification stuff, I wrote a simple counted Petri net simulator.

Interestingly, I can't find anything about counted Petri nets on the internet, so I assume they died an ignomious death. I'll revive them for a brief moment, because they're an interesting simple example of how to extend Petri nets. The extension is very simple and very minimal, and has some theoretical awkwardness, but it's useful for expressing certain kinds of fairly common concurrency patterns.

All that you do when you extend to counted Petri nets is to add an integer to each transition. The transition can fire not when all of its input edges have tokens waiting, but when some collection of tokens from the input arcs can provide enough tokens. The counts on the edges become a bound on the maximum number of tokens that can move across the arc.

What this is useful for is things like the worker pool pattern. In this kind of concurrency, you have one main thread, and many workers. The main thread creates tasks which are put into a pool. The workers each grab tasks from the pool and perform the tasks, until no tasks are left in the pool. The reason for using a pool is load balancing: the tasks take different amounts of time to complete, and you don't know which tasks are going to take longer. So each of the workers grabs a random task from the pool, and runs it. If it's a fast one, it finishes it quickly, and then grabs another. This means that the processors will all be busy processing tasks for roughly the same amount of time, but they'll end up processing different numbers of tasks. The synchronization scheme for this is for the main thread to set up the task pool, and then wait after putting the tasks into the pool, the main thread waits until all of
the tasks are complete.


How would you represent a worker pool with a Petri net? You have a pool of workers thread, all of which are basically equivalent. The main thread puts tokens (representing the tasks) into a place representing the task pool. The task pool has a collection of out edges, one for each thread, which carry the task tokens to a subnet representing the task threads. The worker threads each have a place at the
end where they deposit tokens for completed tasks. The main thread waits on a transition which doesn't get a token until all of the tasks are completed. That token comes from a place which gets its token only when all of the tasks are complete. Since the different tasks will have performed different numbers
of tasks, we use a transition that fires when all of the tasks are complete. A very simple example of this, with two worker tasks is in the image to the right. The main thread is colored green; the places and transitions that control the synchronization of worker threads are red, and the worker threads themselves are blue.

The counted net is a strange sort of hybrid. It's basically adding a primitive sort of counting to the nets, which is useful. But it does it in a way which is extremely limited. For example, in a real task pool scenario, you wouldn't know how many tasks were going to be dispatched to the pool; but the transition needs to be marked with a specific value. So for the purposes of the net, you pretend to know.

As I mentioned, this adds a bit of theoretical awkwardness. One of the great things about Petri nets is that they've got a very strong notion of synchronization. But with counted nets, that gets weakened. It doesn't show in this example - but for non-trivial nets, you can get cases where things get tangled - where you want at least 1 token from each of some group of places, but you can't guarantee that properly
without adding a bunch of extra layers of places and transitions - which messes up the simplicity and clarity which is the main reason for using Petri nets.

Next week, I'll describe colored Petri nets, which are a much stronger, much cleaner way of extending the capability of Petri nets. The basic idea is that tokens can carry information, and lamba calculus functions can be associated with transitions.

More like this

Colored Petri Nets The big step in Petri nets - the one that really takes them from a theoretical toy to a serious tool used by protocol developers - is the extension to colored Petri nets (CPNs). Calling them "colored" is a bit of a misnomer; the original idea was to assign colors to tokens, and…
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,…
A couple of people pointed out that in my wednesday post about Go, I completely left out the concurrency stuff! That's what I get for rushing the post - I managed to leave out one of the most interesting subjects! Go provides very strong support for communicating processes. I haven't done a lot…
Multitasking refers to the simultaneous performance of two or more tasks, switching back and forth between different tasks, or performing a number of different tasks in quick succession. It consists of two complementary stages: goal-shifting, in which one decides to divert their attention from one…

I can't figure out how a transition with a number is supposed to work. You don't provide an example, and your prose just isn't doing it for me. A before picture and an after picture would be good...

The standard definition of a Petri Net.

A Petri net is a tuple (S,T,F,M0,W):
S - set of states.
T - set of transitions.
F - flow relation
M0 - initial marking.
W - is the set of arc weights.

The function of the arc weights W in the standard definition of a Petri Net is the same as the numbers which you assign on transitions of a "Counted Petri Net". The reason why you can not find anything about "Counted Petri Nets" on internet is that they do not exists as a model. They are subsumed by standard Petri nets.

By Alexandru (not verified) on 05 Oct 2007 #permalink

Alexandru: Mark's paragraph starting "All that you do (...)" contradicts your first remark. I interpret it as stating that a transition is enabled whenever some bag of tokens on its input places exists such that for each input place the count is at most the capacity of the input arc, while the total count is the number inscribed on the transition itself, and that any such bag can be removed when the transition fires.

On the subsumption I think you are right: such Petri nets can be automatically rewritten to standard Petri nets. I don't even think they need to grow more than linearly in size, if you'll accept extra steps (weak bisimulation).


As Reiner beat me to saying:

The difference between a counted net a standard net is that in
a counted net, a transition labeled "n" is enabled whenever any combinations of its predecessor places can contribute a total of N tokens. In a standard net, that "N" must be equal to the sum of the capacities of all of the incoming arcs. In a counted, that "N" can be less than or equal to the sum of the incoming arcs.

The counted net is strictly not any more powerful than the standard net. But it's more expressive in the limited sense of allowing smaller graphs to express the same coordination regime.

Thanks Reiner and Mark. Now the model seems more clear.


Suppose we have a Petri Net P=(S,T,F,M0,W) and its underlying graph G(P) generated by the initial marking M0. Also a Counted Petri Net C=(S,T,F,M0,W') with the same initial marking M0 and its underlying underlying G(C). What I think is that there is a simulation relation between G(C) and G(P), where the simulation relation is a preorder.
You have mentioned about weak bisimulation. I don't really see how one can relate G(C) and G(P) by weak bisimulation, as weak bisimulation involves sequence of transitions and more than that in G(C) there are transition which G(P) can not simulate (mimic). Unless you meant something else.

By Alexandru (not verified) on 06 Oct 2007 #permalink

Alexandru / Mark: see for what I mean. (IMG elements don't appear to work here.) I wish I could draw pictures like Mark ...

As far as I see, the translation sketched in that picture is a simulation, and even a weak bisimulation: for each transition with inflow m and capacity n in the original, it replaces it with m+2 transitions in the result, and each firing of an original corresponds to a sequence of n+2 firings of those transitions in the result. The size of the result is linear in the size of the original, if we count arcs with multiplicities as multiple arcs.


I don't know precisely but I think that in the right picture (the proposed translation), the arc between p_H_2 and H_2 (p_H_2->H_2) should be labeled with (1) and not with (4). The reason is that the case when p1=1, p2=1, p3=1 will be not considered.

By Alexandru (not verified) on 08 Oct 2007 #permalink

Sorry about the mistake; actually the arc between t1_1 and p_t1_l should have had multiplicity 4. Fixed now.