Firing Partial Orders in a Petri Net

摘要

Petri nets have the simple firing rule that a transition is enabled to fire if its preset of places is marked. The occurrence of a transition is called an event. To check whether a sequence of events is enabled, we simply try to fire the sequence from 'start' to 'end' in the initial marking of the net. It is a bit of a stretch to call this an algorithm, but its runtime complexity is in O(|P| · | V|), where P is the set of places and V is the set of events. Petri nets model distributed systems. An execution of a distributed system is a partial order of events rather than a sequence. Compact tokenflows are tailored to an efficient algorithm that decides if a partial order of events is enabled in a Petri net. Yet, the runtime complexity of this algorithm is in O(|P| · |V|~3). In practical applications dealing with a huge amount of behavioral data, the gap between just firing a sequence and deciding if a partial order is enabled, makes a big difference. In this paper, we present an approach to just firing a partial order of events in a Petri net. By firing a partial order, we obtain a lot of information about whether or not the partial order is enabled. We show that just firing is often enough if done correctly.