Strong Delay-Insensitivity and the JTU-Rules

H. Zhang
Department of Computer Science
University of Waterloo
Waterloo, Ontario, Canada N2L 3G1
email: richard@dgp.utoronto.ca

J. A. Brzozowski
Department of Computer Science
University of Waterloo
Waterloo, Ontario, Canada N2L 3G1
email: brzozo@maveric.uwaterloo.ca

Abstract

We begin with a network N of components connected by delay-free wires. We analyze the behavior of N, assuming arbitrary component delays, and take this behavior to be correct. We then study the effects of wire delays, and consider N to be a delay-insensitive network if its behavior remains correct with arbitrary wire delays. It is known that network delay-insensitivity is equivalent to a generalized form of semi-modularity, as long as we associate delays with both components and wires. We prove in this paper that, under this assumption, 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 rules, when the component operates within the network. Our results have the effect of unifying three concepts: Muller's semi-modularity, our notion of network delay-insensitivity, and Udding's rules for delay-insensitive components.