A Caltech Library Service

A Necessary and Sufficient Timing Assumption for Speed-Independent Circuits

Keller, Sean and Katelmany, Michael and Martin, Alain J. (2009) A Necessary and Sufficient Timing Assumption for Speed-Independent Circuits. In: 15th International Symposium on Advanced Research in Asynchronous Circuits and Systems : (ASYNC 2009) : proceedings : 17-19 May 2009 Chapel Hill, North Carolina, USA. IEEE Computer Society , Los Alamitos, CA, pp. 65-76. ISBN 9781424439331.

PDF - Accepted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Additional Information:© 2009 IEEE. Acknowledgment is due to Chris J. Myers, Piyush Prakash, and to the members of our research groups for their excellent comments and insights. The research described in this paper is in part supported by a grant from the National Science Foundation.
Group:Computer Science Technical Reports
Funding AgencyGrant Number
Subject Keywords:DI, PRS, QDI, SI, adversary path, asynchronous circuits, asynchronous logic, delay-insensitive, isochronic fork, production rule sets, quasi-delay insensitive, speed-independent
Other Numbering System:
Other Numbering System NameOther Numbering System ID
Computer Science Technical Reports2009.001
Record Number:CaltechAUTHORS:20100506-101621122
Persistent URL:
Official Citation:Keller, S.; Katelman, M.; Martin, A.J.; , "A Necessary and Sufficient Timing Assumption for Speed-Independent Circuits," Asynchronous Circuits and Systems, 2009. ASYNC '09. 15th IEEE Symposium on , vol., no., pp.65-76, 17-20 May 2009 doi: 10.1109/ASYNC.2009.27
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:18164
Deposited By: Tony Diaz
Deposited On:14 May 2010 16:44
Last Modified:03 Oct 2019 01:38

Repository Staff Only: item control page