Optimistic regulation of concurrency

Abstract

Unregulated concurrency in functional programs may lead to space demands that exceed available space, causing deadlock. This thesis proposes regulating concurrency optimistically with rollbacks. Excessive concurrency is viewed as a fault from which to recover. An optimistic regulator has two parts: a recovery-point manager and a process scheduler. This thesis presents a formal model that characterizes data flow and control flow within concurrent functional programs. The model guides the design of the recovery-point manager and process scheduler. The proposed regulator guarantees that concurrent execution of a program does not deadlock if the program is given space sufficient for sequential execution.

The advantage of the optimistic regulation is that concurrency is tailored to fit available space instead of vice versa. Furthermore, the optimistic approach allows errors on the side of too much concurrency rather than too little, and may be able to obtain better speedup than pessimistic regulation.