True Concurrency
- Day - Time: 30 November 2016, h.11:30
- Place: Area della Ricerca CNR di Pisa - Room: C-29
Speakers
- Jetty Kleijn (LIACS, Leiden University, The Netherlands)
Referent
Abstract
In a distributed system, actions may occur concurrently. This leads in a natural way to a partial order model of concurrency. In this set-up, the runs of a system are represented as labelled partial orders of action occurrences (events) expressing that concurrent events can be executed in any order (the so-called 'true concurrency' paradigm). Elementary Net systems, a basic class of Petri Nets, and the semantical model of Mazurkiewicz traces exemplify this approach. However, merely distinguishing between order and the absence of order is in general not enough to describe the behaviour of concurrent systems. Partial orders and their associated (step) sequences cannot express the 'not later than' and 'mutual exclusion' relations that may exist between events. In this talk we identify the general order structures that can capture *any* concurrent run represented by step sequences. They moreover match exactly with step traces, the generalisation of Mazurkiewicz traces to the level of step sequences. Elementary Net systems extended with inhibitor arcs and mutex arcs provide a corresponding system model.
This presentation is based on joint work with Ryszard Janicki, Maciej Koutny, and Lukasz Mikulski.