On Ethics of Mazurkiewicz Traces

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

Abstrakty

EN

We extend the well-known hierarchy ∞-fair ⊆0-fair ⊆ just for sequences (sequential computations) to that of traces (concurrent processes). The fairness hierarchy for traces is similar, but more involved than for sequences. We study this hierarchy, first in general, abstracting from concrete concurrent system, then for basic classes of Petri nets - elementary and place/transition nets. Finally, we define the fairness notions in a non-interleaving way and compare them with the former ones.

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2007
• Tom: Vol. 80, nr 1-3
• Strony: 259--272
• Opis fizyczny: bibliogr. 19 poz., wykr.

Twórcy

autor

Ochmański E.

autor

Pieckowska J.

• Faculty of Mathematics and Computer Science, Nicolaus Copernicus University, Chopina 12/18, 87-100 Toruń, Poland,

Bibliografia

• [1] Best, E.: Fairness and Conspiracies. Information Processing Letters , 18, 1984, 215-220.
• [2] Desel, J., Reising, W.: Place/Transition Petri Nets. In [15] LNCS, 1491, Springer, 1998, 122-173.
• [3] Diekert, V.: Combinatorics on Traces. Lectures on Petri Nets. LNCS, 454, Springer, 1990.
• [4] Diekert, V.: A Partial Trace Semantics for Petri Nets. Theoretical Computer Science , 134(1), 1994, 87-105.
• [5] Francez, N.: Fairness. Springer, 1986.
• [6] Francez, N., Back R.-J., Kurki-Suonio, R.: On Equivalence-Completions of Fairness Assumptions. Formal Aspects of Computing , 4, 1992, 582-591.
• [7] Gastin, P., Petit, A.: Infinite Traces. In Diekert/Rozenberg (eds.) "Book of Traces", World Scientific, 1995.
• [8] Hoogers, P.W., Kleijn, H.C.M., Thiagarajan, P.S.: A Trace Semantics for Petri Nets. Information and Computation, 117(1), 98-114, 1995.
• [9] Kwiatkowska, M.: Defining Process Fairness for Non-Interleaving Concurrency. LNCS, 472, 286-300, Springer, 1990.
• [10] Lamport, L.: Fairness and hyperfairness. Distributed Computing, 13(4), 239-245, 2000.
• [11] Lehman, D., Pnueli, A., Stavi, J.: Impartiality, Justice and Fairness: the Ethics of Concurrent Termination. LNCS, 115, 264-277, Springer, 1981.
• [12] Mazurkiewicz, A.: Concurrent program schemes and their interpretations. Report DAIMI-PB-78, Aarhus University, 1977.
• [13] Merceron, A.: Fair Processes. In Advances in Petri Nets, LNCS, 266, 181-195, Springer, 1987.
• [14] Peled, D., Pnueli, A.: Proving Partial Order Properties. Theoretical Computer Science, 126, 143-182, 1994.
• [15] Reisig, W., Rozenberg, G. (eds.): Lectures on Petri Nets. LNCS, 1491, Springer, 1998.
• [16] Rozenberg, G., Engelfriet, J.: Elementary Net Systems. In [15], LNCS, 1491, 12-121, Springer, 1998.
• [17] Völzer, H.: Refinement-Robust Fairness. CONCUR 2002, LNCS, 2421, 547-561, Springer, 2002.
• [18] Völzer, H.: On Conspiracies and Hyperfairness in Distributed Computing. DISC 2005, LNCS, 3724, 33-47, Springer, 2005.
• [19] Völzer, H., Varacca, D., Kindler, E.: Defining Fairness. CONCUR 2005, LNCS 3653, 458-472, Springer, 2005.