Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published 2014 | Accepted Version
Book Section - Chapter Open

Speed faults in computation by chemical reaction networks

Abstract

Chemical reaction networks (CRNs) formally model chemistry in a well-mixed solution. Assuming a fixed molecular population size and bimolecular reactions, CRNs are formally equivalent to population protocols, a model of distributed computing introduced by Angluin, Aspnes, Diamadi, Fischer, and Peralta (PODC 2004). The challenge of fast computation by CRNs (or population protocols) is to ensure that there is never a bottleneck "slow" reaction that requires two molecules (agent states) to react (communicate), both of which are present in low (O(1)) counts. It is known that CRNs can be fast in expectation by avoiding slow reactions with high probability. However, states may be reachable (with low probability) from which the correct answer may only be computed by executing a slow reaction. We deem such an event a speed fault. We show that the problems decidable by CRNs guaranteed to avoid speed faults are precisely the detection problems: Boolean combinations of questions of the form "is a certain species present or not?". This implies, for instance, that no speed fault free CRN could decide whether there are at least two molecules of a certain species, although a CRN could decide this in "fast" expected time — i.e. speed fault free CRNs "can't count."

Additional Information

© 2014 Springer Verlag Berlin. The third, and fourth authors were supported by the Molecular Programming Project under NSF grants 0832824 and 1317694, the first author was supposed by NSC grant number 101-2221-E-002-122-MY3, the second author was supported by NSF grants CCF-1049899 and CCF-1217770, the third author was supported by a Computing Innovation Fellowship under NSF grant 1019343, NSF grants CCF-1219274 and CCF-1162589, and the fourth author was supported by NIGMS Systems Biology Center grant P50 GM081879.

Attached Files

Accepted Version - sfccrn.pdf

Files

sfccrn.pdf
Files (779.0 kB)
Name Size Download all
md5:7ed41bf52e418911eae02e611ca148cd
779.0 kB Preview Download

Additional details

Created:
August 19, 2023
Modified:
January 13, 2024