Modelling, Realisations and Limitations of Concurrent Delay-Insensitive Networks

Concurrent and distributed behaviour encompasses a wide range of ever evolving phenomena and features of computation such as communication, mobility, causality, failure recovery and reversibility. In order to understand better and make precise the properties of such behaviour, concurrent and distributed behaviour needs to be modelled abstractly and with formal rigour. Delay-insensitive networks are a class of asynchronous systems which makes no assumptions about the timing of signals or components. This makes them suitable for the implementation of highly concurrent systems. Unfortunately, concurrency within delay-insensitive networks is an underdeveloped concept which lacks formal rigour. Reversibility of such systems is also typically only studied in the context of serial systems without concurrency. In this thesis, a new model for describing the behaviour of delay-insensitive components is introduced which more naturally permits the modelling and study of concurrency. Reversibility of such components is discussed. The concept of an environment for a component is formalised, and its limitations in terms of interactivity with such a component is also studied. Algorithms for generating the environments for delay-insensitive components, such that desirable properties always hold are given. Universality results and properties of networks of such components are examined in-depth. A new process algebra which allows the encoding of these networks is introduced. This permits rigorously defined notions of implementation and other desirable run-time properties of these networks. A family of new novel cellular automata is defined which allows the encoding of delay-insensitive networks. These cellular automata are competitive with existing CA regarding universality, and number of rules and states. They have a feature we call direction-reversibility, which allows the inversion of behaviour simply by reversing the direction of signals. Finally, two pieces of software called Delay-Insensitive Network Tool Suite and STCA Simulator, developed to aid in this research, are also detailed.