H. Zhang
Delay-Insensitive Networks,
MMath Thesis,
Department of Computer Science,
University of Waterloo, Waterloo, Ontario, Canada N2L 3G1,
June 1997.
(Supervised by J. A. Brzozowski)

Abstract

An asynchronous network is said to be delay-insensitive if its functional correctness is independent of the delays in its components and in the wires connecting the components. In this thesis, we study delay-insensitivity of autonomous networks, i.e., networks without external inputs, whose components can be arbitrary sequential machines of the Moore type. A formal model for this type of network and their behavior is established. We introduce a new definition of delay-insensitivity which uses the notion of behavioral equivalence in the presence of arbitrary delays. In particular, a network N is delay-insensitive if the behavior of any network N' derived from N by the addition of delays is (weakly) bisimilar to the behavior of N. We relate the delay-insensitivity of a network to the concept of semi-modularity of its behavior. Roughly speaking, a behavior is semi-modular if an enabled action cannot be disabled by another action. We generalize the existing definition of semi-modularity (due to Muller) to reflect nondeterminism in network behaviors. We prove that the semi-modularity of a network's behavior implies the delay-insensitivity of its components, in the sense that each component's trace structure satisfies Udding's delay-insensitivity rules. Furthermore, we prove several results relating delay-insensitivity to semi-modularity, among which is the equivalence between delay-insensitivity and semi-modularity for delay-dense networks, where a network is delay-dense if, of each pair of adjacent components in the network, at least one is a delay element. A discussion of the problem of testing whether a given network is delay-insensitive is also included.