Best Fairness Hierarchy in Elementary Nets

• Autorzy: Ochmański E.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

Petri net; elementary eet systems; fairness; conspiracies

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2004
• Tom: Vol. 60, nr 1-4
• Strony: 237--250
• Opis fizyczny: Bibliogr. 7 poz., wykr.

Twórcy

autor

Ochmański E.

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

Bibliografia

• [1] Eike Best: Fairness and Conspiracies. Information Processing Letters 18. pp. 215-220, 1984. Erratum: 1PL19. p. 162, 1984.
• [2] Nissim Francez: Fairness. Springer-Verlag, 1986.
• [3] Ekkart Kindler, Wil van der Aalst: Liveness, Fairness and Recurrence in Petri Nets. Information Processing Letters 70 (6) pp. 269-274, 1999.
• [4] D. Lehman. A. Pnueli, J. Stavi: Impartiality. Justice and Fairness: the Ethics of Concurrent Termination. LNCS 115. pp. 264-277. Springer-Verlag, 1981.
• [5] Agathe Merceron: Fair Processes. Advances in Petri Nets, LNCS 266. pp. 181-195. Springer-Verlag. 1987.
• [6] Wolfgang Reisig, Grzegorz Rozenberg (eds.): Lectures on Petri Nets. LNCS 1491. Springer-Verlag, 1998.
• [7] Grzegorz Rozenberg. Joost Engelfriet: Elementary Net Systems. In [6]. LNCS 1491. pp. 12-121. Springer-Verlag. 1998.