CS[ Bristol CS | Index ]

Deterministic Concurrency

Ian Holyer and David Carter. Technical Report CSTR-95-015, Department of Computer Science, University of Bristol, June 1995. Full paper: 42134 bytes gzipped PostScript.

Abstract

Existing functional languages appear not to be suitable for implementing systems which are inherently concurrent, such as operating system environments or reactive systems. Adaptations to functional languages developed to support such applications have in the past always involved the introduction of non-determinism. This paper proposes an adaptation of a functional language which provides concurrency without the introduction of non-determinism or timing information, and indeed without any alteration to the usual semantics, thus retaining the purely declarative nature of functional programming. The expressiveness of this deterministic form of concurrency is explored by presenting and discussing outlines of designs for a file manager, a window system and a process communication mechanism. Taken together, these demonstrate the feasibility of a deterministic design for a complete single-user concurrent working environment.
Dr. Ian Holyer, ian@cs.bris.ac.uk. Last modified on Friday 7 July 1995 at 10:31.