Best Fairness Hierarchy in Elementary Nets

Issue title: Concurrency Specification and Programming (CS&P 2003)

Article type: Research Article

Authors: Ochmański, Edward

Affiliations: Faculty of Mathematics and Computer Science, Nicolaus Copernicus University, Toruń, Poland

Abstract: The fairness hierarchy and conspiracies, the notions introduced by Best, are studied in the context of elementary nets. Proving that sequential as well as persistent systems are conspiracy-free, we indicate two main roots of conspiracies: distributed memory and conflicts. Using the notion of marking-fairness, due to Merceron, we prove that T0-fairness + M0-fairness = T∞-fairness. This result gives a method of a local control ensuring globally fair executions. Next we show how to check, if a given elementary net is conspiracy-free, and prove the obtained criterion to be effectively decidable. Finally, we give a characterization of live concurrent systems, using the notion of ∞-fairness.

Journal: Fundamenta Informaticae, vol. 60, no. 1-4, pp. 237-250, 2004