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.