Toggle Main Menu Toggle Search

Open Access padlockePrints

Causal Structures for General Concurrent Behaviours

Lookup NU author(s): Professor Maciej Koutny, Dr Lukasz Mikulski




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.

Publication metadata

Author(s): Janicki R, Kleijn J, Koutny M, Mikulski L

Editor(s): Szczuka, MS; Czaja, L; Kacprzak, M

Publication type: Conference Proceedings (inc. Abstract)

Publication status: Published

Conference Name: 22nd International Workshop on Concurrency, Specification and Programming, CS&P

Year of Conference: 2013

Pages: 193-205

ISSN: 1613-0073



Series Title: CEUR Workshop Proceedings