Priority scheduling of distributed systems based on model checking (Q453501)

One can imagine the design of concurrent systems in two stages. The first one consists in the description of the behaviour of the isolated processes while the second one consists in the definition of the inter-processes synchronization, i.e., the rules that lead to the activation or deactivation of a process depending on the current states of the other processes that compose the system. However, a further constraint must be added to make this design methodology realistic. Namely, the activation/deactivation of the processes need to result from local knowledge of the system. This is an issue since very often the synchronization expresses a global constraint. In this article, the authors address this issue in the framework of Petri nets with priorities. Priorities are defined by a partial order relation among the transitions of the Petri nets. An enabled transition can be fired only if there is no higher priority transition that is also enabled. The issue that is addressed is how transforming a prioritized Petri net \(P\) to a classical Petri net \(P'\) that implements the priority of \(P\). Moreover, \(P'\) makes use of local information. The method that is proposed in this article is based on formal methods of model checking that make possible to identify the situations where local information is sufficient to implement priorities.