Home
Scholarly Works
Concurrency Traces
Chapter

Concurrency Traces

Abstract

This chapter presents the basics of the theory of concurrency traces which are elements of equational partially commutative monoids of sequences. The theory of trace monoids has been developed and applied within diverse areas, such as combinatorics and, in particular, concurrency theory. Its origins are rooted in the theory of formal languages with its powerful repertoire of analysis tools and well developed structural properties. Trace theory attempts to transfer these ideas into the realm of concurrent system behaviours. A key novelty is the explicit treatment of independence between events within sequences of executed actions. This allows one to identify those sequences which differ only by the ordering of independent actions, resulting in a clear notion of equivalence between system executions. This approach has proved to be particularly suited for dealing with a wide range of distributed and concurrent systems. The restriction is that independence is introduced statically, at the level of actions rather than events, so it cannot be changed during the system execution. Applications of concurrency traces in the field of concurrent systems are motivated mainly by the fact that traces can represent partial orders capturing causality in system executions. This chapter presents the basic notions concerning concurrency traces and, in particular, makes explicit their relationship with causal partial orders.

Authors

Janicki R; Kleijn J; Koutny M; Mikulski Ł

Book title

Studies in Computational Intelligence

Volume

1020

Pagination

pp. 77-99

Publication Date

January 1, 2022

DOI

10.1007/978-3-662-64821-6_4
View published work (Non-McMaster Users)

Contact the Experts team