\input zb-basic
\input zb-ioport
\iteman{io-port 01493504}
\itemau{Brzozowski, J.A.}
\itemti{Delay-insensitivity and ternary simulation.}
\itemso{Theor. Comput. Sci. 245, No.1, 3-25 (2000).}
\itemab
Summary: 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 $\hat 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 $\hat N$ defined as above still satisfies $\Sigma$. An important problem in asynchronous circuits is to determine, given a specification $\Sigma$ and a set $T$ of module types, whether there exists a delay-insensitive network of modules from $T$ 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.
\itemrv{~}
\itemcc{}
\itemut{asynchronous; circuit; delay-insensitive; fundamental mode; general multiple-winner; input-output mode; network; semi-modular; speed-independent; ternary algebra; ternary simulation}
\itemli{doi:10.1016/S0304-3975(99)00273-X}
\end