Technical reports

Event structures with persistence

Lucy G. Brace-Evans

February 2008, 113 pages

This technical report is based on a dissertation submitted October 2007 by the author for the degree of Doctor of Philosophy to the University of Cambridge, St. John’s College.

DOI: 10.48456/tr-710

Abstract

Increasingly, the style of computation is changing. Instead of one machine running a program sequentially, we have systems with many individual agents running in parallel. The need for mathematical models of such computations is therefore ever greater.

There are many models of concurrent computations. Such models can, for example, provide a semantics to process calculi and thereby suggest behavioural equivalences between processes. They are also key to the development of automated tools for reasoning about concurrent systems. In this thesis we explore some applications and generalisations of one particular model – event structures. We describe a variety of kinds of morphism between event structures. Each kind expresses a different sort of behavioural relationship. We demonstrate the way in which event structures can model both processes and types of processes by recalling a semantics for Affine HOPLA, a higher order process language. This is given in terms of asymmetric spans of event structures. We show that such spans support a trace construction. This allows the modelling of feedback and suggests a semantics for non-deterministic dataflow processes in terms of spans. The semantics given is shown to be consistent with Kahn’s fixed point construction when we consider spans modelling deterministic processes.

A generalisation of event structures to include persistent events is proposed. Based on previously described morphisms between classical event structures, we define several categories of event structures with persistence. We show that, unlike for the corresponding categories of classical event structures, all are isomorphic to Kleisli categories of monads on the most restricted category. Amongst other things, this provides us with a way of understanding the asymmetric spans mentioned previously as symmetric spans where one morphism is modified by a monad. Thus we provide a general setting for future investigations involving event structures.

Full text

PDF (0.9 MB)

BibTeX record

@TechReport{UCAM-CL-TR-710,
  author =	 {Brace-Evans, Lucy G.},
  title = 	 {{Event structures with persistence}},
  year = 	 2008,
  month = 	 feb,
  url = 	 {https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-710.pdf},
  institution =  {University of Cambridge, Computer Laboratory},
  doi = 	 {10.48456/tr-710},
  number = 	 {UCAM-CL-TR-710}
}