Optimistic regulation of concurrency
A.D. Robinson · 2002
Unregulated concurrency in applicative programs may lead to space demands that exceed available space, causing deadlock. Optimistic regulation views such excessive concurrency as a fault from which to recover. This paper sketches a theoretical foundation for the design of an optimistic regulator. The optimistic regulators advantage over other regulators is its guarantee that if a program is given space sufficient for sequential execution, concurrent execution cannot cause it to deadlock due to exhaustion of space. The regulator is based upon a graph-rewriting model. The model applies to programs that can be decomposed into a set of referentially transparent communicating processes. The model is general enough to analyze LISP-like future and 'delay' constructs in applicative programs, but specific enough to make useful observations about data flow, control flow, and atomic actions within such a system.>