After reading several articles about petri nets, I am confused on how firing works. Can Petri net system fire only one transition out of all active (fire-able transitions) at a single moment? Or are multiple transitions allowed to fire at a single moment?
2 Answers
Both.
Only one transition being able to fire at a time is known as interleaving semantics. Multiple transitions firing simultaneously is known as step semantics. Some people doing concurrency theory only call the latter real concurrency, and they care deeply about the difference; I'm sure the difference has consequences, but I've worked with Petri nets and I've never run into a situation where it mattered.
In a Petri net editor I used to work on, durations could be assigned to transitions - so these "transitions" represent tasks or processes that take a certain time. Once that is possible, clearly it makes a great difference whether two of them can be firing at the same time or not. But I would say such "timed transitions" really aren't transitions; rather, they are shorthands for a transition (start), a place (execution), and another transition (finish).
How many transitions fire at once depends on the interpretation assigned to the Petri Net.
If you want more than one transition to fire at once, you should consider:
1. Will the transitions fire using one processor?
This is fine. A Petri Net can handle this type of firing because the transitions actually fire one at a time. Consider the Petri Net in the following diagram:
Let m0 be the mark in place P0. Consider the firing rule for T1: m0 = m0 - 1,and the firing rule for T2: m0 = m - 1. It is easy to check if a transition is enabled before firing the transition.
2. Will each of the transition to fire use a different processor?
This is probably not fine. Using the same example above, consider a processor is responsible for firing T0 and another processor is responsible for firing T2. Each processor checks if its transition is enabled. If it is enabled, the processor fires the transition. Each check may indicate that the transition is enabled. So each processor will proceed to fire the transition. Depending on when each processor reads m0 and writes the computed value of m0, the value of m0 may be 0 or -1.
Postscript
A PDF version of the original answer may be found at http://www.aespen.ca/AEnswers/1416178160.pdf (and the equations are much better to look at). The modifier answer may be found at http://www.aespen.ca/AEnswers/1416975962.pdf.
-
$\begingroup$ You are imposing a model of execution that isn't inherent to Petri nets. Nothing in the semantics of Petri nets assumes the existence of "processors". Don't think of checking for enabledness and firing as two separate actions - doing them separately is invalid, they must always be done together atomically, with no possibility of other transitions interfering. $\endgroup$ Nov 25, 2014 at 7:47
-
$\begingroup$ I apologize for not being clear what I mean by "Petri Nets". $\endgroup$ Nov 25, 2014 at 15:19
-
$\begingroup$ [Sorry for the incomplete comment. Here is the rest.] I agree that a model of execution should not be part of the definition of a Petri Net. The idea of a “processor” plus a Petri Net should probably be given a name. I also apologize for the confusion about firing transitions. I edited my answer for “2. Will each of the transition …” I did not mean to imply that it is okay to fire any transition. I agree that only enabled transitions can fire. The modified version is at aespen.ca/AEnswers/1416975962.pdf. $\endgroup$ Nov 26, 2014 at 4:36
-