Delay-insensitivity and ternary simulation

Consider a network N constructed from a set of modules interconnected by wires. Suppose that there is a formal specification Sigma for N, and that the behavior of N satisfies this specification. Let (N) over cap consist of the same modules, but suppose that these modules and the interconnecting wires have arbitrary delays. We say that N is delay-insensitive if the behavior of any network (N) over cap defined as above still satisfies Sigma. An important problem in asynchronous circuits is to determine, given a specification Sigma and a set F of module types, whether there exists a delay-insensitive network of modules from F with a behavior satisfying Sigma. If such a network exists, we say that it implements Sigma delay-insensitively. In the case where the components are logic gates, it is known that very few specifications have delay-insensitive implementations. The proofs of several such results involve "ternary simulation" -an analysis method based on ternary algebra - and rely on a key theorem linking binary analysis and ternary simulation. In this paper we survey the known results concerning delay-insensitivity, and outline one proof that a simple specification cannot be implemented. (C) 2000 Elsevier Science B.V. All rights reserved.