Categories for synchrony and asynchrony

• Published in: Electronic notes in theoretical computer science 1995, Vol.1, p.66-90
• Main Authors: Cockett, J.R.B., Spooner, D.A.
• Format: Article
• Language: English
• ISSN: 1571-0661; 1571-0661
• DOI: 10.1016/S1571-0661(04)80005-7

The purpose of this paper is to show how one may construct from a synchronous interaction category, such as SProc, a corresponding asynchronous version. Significantly, it is not a simple Kleisli construction, but rather arises due to particular properties of a monad combined with the existence of a certain type of distributive law. Following earlier work we consider those synchronous interaction categories which arise from model categories through a quotiented span construction: SProc arises in this way from labelled transition systems. The quotienting is determined by a cover system which expresses bisimulation. Asynchrony is introduced into a model category by a monad which, in the case of transition systems, adds the ability to idle. To form a process category atop this two further ingredients are required: pullbacks in the Kleisli category, and a cover system to express (weak) bisimulation. The technical results of the paper provide necessary and sufficient conditions for a Kleisli category to have finite limits. Furthermore, they show how distributive laws can be used to induce cover systems on such Kleisli categories. These provide the ingredients for the construction of asynchronous settings.