Delay-insensitivity and ternary simulation

AbstractConsider a network N constructed from a set of modules interconnected by wires. Suppose that there is a formal specification Σ for N, and that the behavior of N satisfies this specification. Let N̂ 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̂ defined as above still satisfies Σ. An important problem in asynchronous circuits is to determine, given a specification Σ and a set T of module types, whether there exists a delay-insensitive network of modules from T with a behavior satisfying Σ. If such a network exists, we say that it implements Σ 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