Can a petri net fire only one transition at a single moment?

Question

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?

Answer 1

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).

Answer 2

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.