Controllable Delay-Insensitive Processes

Issue title: The Fourth Special Issue on Applications of Concurrency to System Design (ACSD05)

Article type: Research Article

Authors: Josephs, Mark B. | Kapoor, Hemangee K.

Affiliations: Centre for Concurrent Systems and VLSI, London South Bank University, UK. E-mail: [email protected] | Dhirubhai Ambani Institute of Information and Communication Technology, Gandhinagar, India. E-mail: [email protected]

Abstract: Josephs and Udding's DI-Algebra offers a convenient way of specifying and verifying designs that must rely upon delay-insensitive signalling between modules (asynchronous logic blocks). It is based on Hoare's theory of CSP, including the notion of refinement between processes, and is similarly underpinned by a denotational semantics. Verhoeff developed an alternative theory of delay-insensitive design based on a testing paradigm and the concept of reflection. The first contribution of this paper is to define a relation between processes in DI-Algebra that captures Verhoeff's notion of a closed system passing a test (by being free of interference and deadlock). The second contribution is to introduce a new notion of controllability, that is, to define what it means for a process to be controllable in DI-Algebra. The third contribution is to extend DI-Algebra with a reflection operator and to show how testing relates to controllability, reflection and refinement. It is also shown that double reflection yields fully-abstract processes in the sense that it removes irrelevant distinctions between controllable processes. The final contribution is a modified version of Verhoeff's factorisation theorem that could potentially be of major importance for constructive design and the development of design tools. Several elementary examples are worked out in detail to illustrate the concepts. The claims made in this paper are accompanied by formal proofs, mostly in an annotated calculational style.

Keywords: Process algebra, refinement, testing, controllability, reflection, factorisation

Journal: Fundamenta Informaticae, vol. 78, no. 1, pp. 101-130, 2007