Chen, Ho-Lin and Cummings, Rachel and Doty, David and Soloveichik, David (2014) Speed faults in computation by chemical reaction networks. In: Distributed Computing. Lecture Notes in Computer Science. No.8784. Springer Berlin Heidelberg , Freiburg, Germany, pp. 16-30. ISBN 978-3-662-45174-8 http://resolver.caltech.edu/CaltechAUTHORS:20140904-140207026
- Accepted Version
See Usage Policy.
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20140904-140207026
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."
|Item Type:||Book Section|
|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.|
|Usage Policy:||No commercial reproduction, distribution, display or performance rights in this work are provided.|
|Deposited By:||Kristin Buxton|
|Deposited On:||04 Sep 2014 21:25|
|Last Modified:||15 Jan 2016 00:45|
Repository Staff Only: item control page