Timing in chemical reaction networks
- Creators
- Doty, David
- Other:
- Chekuri, Chandra
Abstract
Chemical reaction networks (CRNs) formally model chemistry in a well-mixed solution. CRNs are widely used to describe information processing occurring in natural cellular regulatory networks, and with upcoming advances in synthetic biology, CRNs are a promising programming language for the design of artificial molecular control circuitry. Due to a formal equivalence between CRNs and a model of distributed computing known as population protocols, results transfer readily between the two models. We show that if a CRN respects finite density (at most O(n) additional molecules can be produced from n initial molecules), then starting from any dense initial configuration (all molecular species initially present have initial count Ω(n), where n is the initial molecular count and volume), every producible species is produced in constant time with high probability. This implies that no CRN obeying the stated constraints can function as a timer, able to produce a molecule, but doing so only after a time that is an unbounded function of the input size. This has consequences regarding an open question of Angluin, Aspnes, and Eisenstat concerning the ability of population protocols to perform fast, reliable leader election and to simulate arbitrary algorithms from a uniform initial state.
Additional Information
© 2014 SIAM. The author was supported by the Molecular Programming Project under NSF grant 0832824 and by NSF grants CCF-1219274 and CCF-1162589.Attached Files
Published - 1_2E9781611973402_2E57.pdf
Files
Name | Size | Download all |
---|---|---|
md5:637f3e31eb0ec784bc16528832a2e8d1
|
513.7 kB | Preview Download |
Additional details
- Eprint ID
- 70978
- Resolver ID
- CaltechAUTHORS:20161010-161629936
- CCF-0832824
- NSF
- CCF-1219274
- NSF
- CCF-1162589
- NSF
- Created
-
2016-10-11Created from EPrint's datestamp field
- Updated
-
2021-11-11Created from EPrint's last_modified field