A Necessary and Sufficient Timing Assumption for Speed-Independent Circuits

摘要

This paper presents a proof that the adversary path timing assumption is both necessary and sufficient for correct SI circuit operation. This assumption requires that the delay of a wire on one branch of a fork be less than the delay through a gate sequence beginning at another branch in the same fork. Both the definition of the timing assumption and the proof build on a general, formal notion of computation given with respect to production rule sets. This underlying framework can be used for a variety of proof efforts or as a basis for defining other useful notions involving asynchronous computation.