Dr. Łukasz Mikulski

Abstract:

Mazurkiewicz traces are a well-established, classical, and basic model for representing and structuring sequential observations of concurrent behaviour.

The fundamental assumption underlying trace theory is that independent events (occurrences of actions) may be observed in any order. Sequences that differ only with respect to their ordering of independent events are identified as belonging to the same concurrent run of the system under consideration. Thus a trace is an equivalence class of sequences comprising all (sequential) observations of a single concurrent run.

Being based on equating independence and lack of ordering, the concurrency paradigm of Mazurkiewicz traces and the corresponding partial order interpretation of concurrency is rather restricted.

I will show how to extend the trace approach to a more general situation by assuming that observers may not only register the occurrence of one action before another, but can also record simultaneous occurrences of actions. Thus here observations consist of sequences of steps, i.e. sets of one or more actions that occur simultaneously. Retaining the original philosophy underlying Mazurkiewicz traces, the set-up will be based on just a few explicit and simple design choices. It leads to the concept of a concurrency alphabet with three basic relations between pairs of different actions: simultaneity indicating that actions may occur together in a step; serialisability indicating a possible execution order for potentially simultaneous actions; and interleaving indicating that actions can not  occur simultaneously though no specific ordering is required. These three relations can then be used to identify step sequences as observations of the same concurrent run. The resulting equivalence classes of step sequences are called step traces. It is the main aim of my talk to characterise such traces.

I will take a fresh look at the way in which a theory of traces consisting of step sequences could be developed. I will do this by extending original theory obtaining more and more expressible intermediate models of causal structures. The soundness of the proposed improvement will be demonstrated in the second part of the talk by showing how a recently proposed model of causal structures matches exactly the introduced extension of Mazurkiewicz traces.

(Joint work with Ryszard Janicki (McMaster University, Canada), Jetty Kleijn (LIACS,Leiden University, The Netherlands) and Maciej Koutny (Newcastle University, United Kingdom))