CaltechAUTHORS
  A Caltech Library Service

Speed faults in computation by chemical reaction networks

Chen, Ho-Lin and Cummings, Rachel and Doty, David and Soloveichik, David (2014) Speed faults in computation by chemical reaction networks. In: 28th International Symposium on Distributed Computing, October 12-14, 2014, Austin, TX. (Submitted) http://resolver.caltech.edu/CaltechAUTHORS:20140904-140207026

[img]
Preview
PDF - Accepted Version
See Usage Policy.

760Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20140904-140207026

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."


Item Type:Conference or Workshop Item (Paper)
Related URLs:
URLURL TypeDescription
http://www.disc-conference.org/wp/disc2014/Related ItemConference
Additional Information: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.
Funders:
Funding AgencyGrant Number
NSF0832824
NSF1317694
NSC101-2221-E-002-122-MY3
NSFCCF-1049899
NSFCCF-1217770
NSF Computing Innovation Fellowship1019343
NSFCCF-1219274
NSFCCF-1162589
NIGMS Systems Biology CenterP50 GM081879
Record Number:CaltechAUTHORS:20140904-140207026
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20140904-140207026
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:49250
Collection:CaltechAUTHORS
Deposited By: Kristin Buxton
Deposited On:04 Sep 2014 21:25
Last Modified:04 Sep 2014 21:25

Repository Staff Only: item control page