Models and logics for true concurrency

Abstract

A distributed computer system consists of different processes or agents that function largely autonomously and coordinate their actions by communicating with each other. In such a situation, actions may be performed by different agents of the system locally, in a concurrent manner. In this paper, we first discuss formal models of distributed systems in which concurrency is specified explicitly, in contrast to more traditional approaches where concurrency is represented implicitly as a nondeterministic choice between all possible sequentializations of concurrent actions. This naturally leads to models based on partially-ordered sets of actions rather than sequences of actions and is often called thetrue concurrency approach. The models we focus on are distributed transition systems, elementary net systems and event structures. In the second half of the paper, we develop a family of logics to specify and reason about the behavioural properties of the models we have described. The logics we define are extensions of temporal logic with new modalities to directly describe concurrency. This paper is essentially a survey of work done by the authors during the last few years on modelling distributed systems with true concurrency and using logic to reason about these models. The emphasis is on motivating definitions through examples and on presenting major results, without going into too many formal details. We provide pointers to the literature where these details can be found.