Lookup NU author(s): Professor Maciej Koutny,
Dr Lukasz Mikulski
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License (CC BY-NC 4.0).
In the classical Mazurkiewicz trace approach the behaviour of a con-current system is described in terms of sequential observations that dier onlywith respect to their ordering of independent actions. This paper investigates anextension of the trace model to the case that actions can be observed as occurringsimultaneously. Thus observations are sequences of steps, i.e., sets of actions. Thisleads to a step trace model based on three relations between events: simultane-ity, serialisability, and interleaving. Whereas the underlying causal structures oftraces are based on dependencies between actions leading to a partial order in-terpretation, more general causal structures are needed to describe the invariantrelationships between the action occurrences in a step trace. We present a com-plete picture including dependence structures extending dependence graphs, anda characterisation of step traces in terms of invariant order structures.
Author(s): Janicki R, Kleijn J, Koutny M, Mikulski L
Publication type: Article
Publication status: Published
Journal: Acta Informatica
Print publication date: 01/02/2016
Online publication date: 10/06/2015
Acceptance date: 22/04/2015
Date deposited: 15/06/2015
ISSN (print): 0001-5903
ISSN (electronic): 1432-0525
Altmetrics provided by Altmetric