Categories in Concurrency

Summary

Introduction

Computational behaviours are often distributed, in the sense that they may be seen as spatially separated activities accomplishing a joint task. Many such systems are not meant to terminate, and hence it makes little sense to talk about their behaviours in terms of traditional input-output functions. Rather, we are interested in the behaviour of such systems in terms of their often complex patterns of stimuli/response relationships varying over time. For this reason such systems are often referred to as reactive systems.

Many structures for modelling reactive systems have been studied over the past 20 years. Here we present a few key models. Common to all of them, is that they rest on an idea of atomic actions, over which the behaviour of a system is defined. The models differ mainly with respect to what behavioural features of systems are represented. Some models are more abstract than others, and this fact is often used in informal classifications of the models with respect to expressibility. One of our aims is to present principal representatives of models, covering the landscape from the most abstract to the most concrete, and to formalise the nature of their relationships by explicitly representing the steps of abstraction that are involved in moving between them. In following through this programme, category theory is a convenient language for formalising the relationships between models.

To give an idea of the role categories play, let us focus attention on transition systems as a model of parallel computation.