On Fairness in Petri Nets

Abstract

Introduction: Fairness is to be understood as performing actions in the order of their announcements. Related problems are studied in the Petri net model where actions correspond to the firings of transitions. An action in announced if a transition becomes firable, it is performed if this transition fires. Fairness in Petri nets means firing of transitions in the order of their anabling. Therefore, fairness is a property of firing sequences: some of them satisfy fairness conditions while others do not and have to be excluded. To ensure fairness the firings must be controlled by a queue regime giving temporary priorities to the transitions with longest waiting time. The queue policy can be performed by finite automata controlling the firings of the Petri net. While in other fairness considerations the performability of a waiting action is not influenced by other actions, the situation in Patri nets may be different: a firable transition may loose its concession by firings of other transitions, i. e. an announced action may be non-performable when it should be executed with respect to its waiting period. This leads to certain constraits for the net (to permit fair firings) or to modified fairness conditions. The problems like reachability, boundedness, liveness etc. are considered for nets firing under fairness conditions. They can be proved to be undecidable in the case of unbounded nets since we can simulate counter machines by Petri nets where the firings are constraited by fairness. Thus fairness gives the Petri nets more computational power and hence in general it is not possible to modify a Petri net in such a way that the possible firings are exactly the fair firings of the original net.