PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Tytuł artykułu

Characterising Concurrent Histories

Wybrane pełne teksty z tego czasopisma
Identyfikatory
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
Non-interleaving semantics of concurrent systems is often expressed using posets, where causally related events are ordered and concurrent events are unordered. Each causal poset describes a unique concurrent history, i.e., a set of executions, expressed as sequences or step sequences, that are consistent with it. Moreover, a poset captures all precedence-based invariant relationships between the events in the executions belonging to its concurrent history. However, concurrent histories in general may be too intricate to be described solely in terms of causal posets. In this paper, we introduce and investigate generalised mutex order structures which can capture the invariant causal relationships in any concurrent history consisting of step sequence executions. Each such structure comprises two relations, viz. interleaving/mutex and weak causality. As our main result we prove that each generalised mutex order structure is the intersection of the step sequence executions which are consistent with it.
Wydawca
Rocznik
Strony
21--42
Opis fizyczny
Bibliogr. 26 poz.
Twórcy
autor
  • Department of Computing and Software McMaster University Hamilton, ON, L8S 4K1, Canada
autor
  • LIACS Leiden University P.O.Box 9512, NL-2300 RA Leiden, The Netherlands
autor
  • School of Computing Science Newcastle University Newcastle upon Tyne, NE1 7RU, U.K.
autor
  • Faculty of Mathematics and Computer Science Nicolaus Copernicus University Toru´n, Chopina 12/18, Poland
Bibliografia
  • [1] Best, E., Devillers, R.: Sequential and Concurrent Behaviour in Petri Net Theory, Theoretical Computer Science, 55(1), 1987, 87–136.
  • [2] Esparza, J., Heljanko, K.: Unfoldings: A Partial-Order Approach to Model Checking, Monographs in Theoretical Computer Science, Springer, 2008.
  • [3] Gaifman, H., Pratt, V. R.: Partial OrderModels of Concurrency and the Computation of Functions, in: LICS, IEEE Computer Society, 1987, 72–85.
  • [4] Guo, G., Janicki, R.: Modelling Concurrent Behaviours by Commutativity and Weak Causality Relations, in: AMAST, vol. 2422 of Lecture Notes in Computer Science, Springer, 2002, 178–191.
  • [5] Janicki, R.: Relational Structures Model of Concurrency, Acta Informatica, 45, 2008, 279–320.
  • [6] Janicki, R., Kleijn, J., Koutny, M., Mikulski, Ł.: Causal Structures for General Concurrent Behaviours, in: CS&P, vol. 1032 of CEUR Workshop Proceedings, CEUR-WS.org, 2013, 193–205.
  • [7] Janicki, R., Koutny, M.: Invariants and Paradigms of Concurrency Theory, in: PARLE, vol. 506 of Lecture Notes in Computer Science, Springer, 1991, 59–74.
  • [8] Janicki, R., Koutny, M.: Order Structures and Generalisations of Szpilrajn’s Theorem, in: FSTTCS, vol. 761 of Lecture Notes in Computer Science, Springer, 1993, 348–357.
  • [9] Janicki, R., Koutny,M.: Structure of Concurrency, Theoretical Computer Science, 112(1), 1993, 5–52.
  • [10] Janicki, R., Koutny,M.: Semantics of Inhibitor Nets, Information and Computation, 123(1), 1995, 1 – 16.
  • [11] Janicki, R., Koutny,M.: Fundamentals ofModelling Concurrency Using Discrete Relational Structures, Acta Informatica, 34, 1997, 367–388.
  • [12] Juhás, G., Lorenz, R., Mauser, S.: Causal Semantics of Algebraic Petri Nets Distinguishing Concurrency and Synchronicity, Fundamenta Informaticae, 86(3), 2008, 255–298.
  • [13] Kleijn, J., Koutny, M.: The Mutex Paradigm of Concurrency, in: Petri Nets, vol. LNCS 6709 of Lecture Notes in Computer Science, Springer, 2011, 228–247.
  • [14] Kleijn, J., Koutny, M.: Mutex Causality in Processes and Traces, Fundamenta Informaticae, 122, 2013, 119–146.
  • [15] Lamport, L.: The Mutual Exclusion Problem, Journal of the ACM, 17, 1986, 441–449.
  • [16] Le, D. T. M.: On Three Alternative Characterizations of Combined Traces, Fundamenta Informaticae, 113(3), 2011, 265–293.
  • [17] Mazurkiewicz, A.: Concurrent Program Schemes and Their Interpretations, DAIMI Rep. PB 78, Aarhus University, 1977.
  • [18] McMillan, K. L.: Using Unfoldings to Avoid the State Explosion Problem in the Verification of Asynchronous Circuits, in: CAV, vol. 663 of Lecture Notes in Computer Science, Springer, 1992, 164–177.
  • [19] Mikulski, Ł., Koutny, M.: Folded Hasse Diagrams of Combined Traces, Information Processing Letters, 114(4), 2014, 208 – 216.
  • [20] Nielsen, M., Plotkin, G. D., Winskel, G.: Petri Nets, Event Structures and Domains, Part I, Theoretical Computer Science, 13, 1981, 85–108.
  • [21] Pratt, V.: Some Constructions for Order-theoretic Models of Concurrency, in: Logics of Programs, vol. 193 of Lecture Notes in Computer Science, Springer, 1985, 269–283.
  • [22] Rodríguez, C., Schwoon, S., Khomenko, V.: Contextual Merged Processes, in: Petri Nets, vol. 7927 of Lecture Notes in Computer Science, Springer, 2013, 29–48.
  • [23] Schröder, E.: Vorlesungen über die Algebra der Logik (Exakte Logik). Dritter Band: Algebra und Logik der Relative, B. G. Teubner, 1895.
  • [24] Szpilrajn, E.: Sur l’extension de l’ordre partiel, Fundam. Math., 16, 1930, 386–389.
  • [25] Wiener, N.: A Contribution to the Theory of Relative Position, Proc. of the Cambridge Philosophical Society, 33(2), 1914, 313–326.
  • [26] Winkowski, J., Maggiolo-Schettini, A.: An Algebra of Processes, Journal of Computer and System Sciences, 35(2), 1987, 206–228.
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-f78d0759-64cb-441d-870d-bb23bbe49aed
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.