True concurrency in models of asynchronous circuit behaviour

Abstract. In the study of asynchronous designs most authors use the interleaving model of concurrency when describing the behavior of a network; this is usually done for simplicity. The interleaving model assumes the behavior of an asynchronous circuit can be adequately represented by allowing only one signal to change at a time. In contrast to this, true concurrency models allow an arbitrary number of simultaneous signal changes. It seems that little effort has been made to determine what effect the choice of model may have on the analysis of a network. In this paper, we attempt to discover the circumstances under which the assumption of single signal changes can be made without affecting the results of circuit analysis. We prove, in a formal network model, that, in the context of delay-insensitivity and semi-modularity, the single change assumption is valid. We also prove that the same is true for a different definition of delay-insensitivity, restricted to deterministic behaviors. Consequently, in these cases, the more complicated true concurrency analysis is not required