--- _id: '788' abstract: - lang: eng text: In contrast to electronic computation, chemical computation is noisy and susceptible to a variety of sources of error, which has prevented the construction of robust complex systems. To be effective, chemical algorithms must be designed with an appropriate error model in mind. Here we consider the model of chemical reaction networks that preserve molecular count (population protocols), and ask whether computation can be made robust to a natural model of unintended “leak” reactions. Our definition of leak is motivated by both the particular spurious behavior seen when implementing chemical reaction networks with DNA strand displacement cascades, as well as the unavoidable side reactions in any implementation due to the basic laws of chemistry. We develop a new “Robust Detection” algorithm for the problem of fast (logarithmic time) single molecule detection, and prove that it is robust to this general model of leaks. Besides potential applications in single molecule detection, the error-correction ideas developed here might enable a new class of robust-by-design chemical algorithms. Our analysis is based on a non-standard hybrid argument, combining ideas from discrete analysis of population protocols with classic Markov chain techniques. acknowledgement: "D. Alistarh - Supported by an SNF Ambizione Fellowship. A. Kosowski — Supported by Inria project GANG, ANR project DESCARTES, and\r\nNCN grant 2015/17/B/ST6/01897. D. Soloveichik — Supported by NSF grants CCF-1618895 and CCF-1652824.\r\n\r\n" alternative_title: - LNCS article_processing_charge: No author: - first_name: Dan-Adrian full_name: Alistarh, Dan-Adrian id: 4A899BFC-F248-11E8-B48F-1D18A9856A87 last_name: Alistarh orcid: 0000-0003-3650-940X - first_name: Bartłomiej full_name: Dudek, Bartłomiej last_name: Dudek - first_name: Adrian full_name: Kosowski, Adrian last_name: Kosowski - first_name: David full_name: Soloveichik, David last_name: Soloveichik - first_name: Przemysław full_name: Uznański, Przemysław last_name: Uznański citation: ama: 'Alistarh D-A, Dudek B, Kosowski A, Soloveichik D, Uznański P. Robust detection in leak-prone population protocols. In: Vol 10467 LNCS. Springer; 2017:155-171. doi:10.1007/978-3-319-66799-7_11' apa: Alistarh, D.-A., Dudek, B., Kosowski, A., Soloveichik, D., & Uznański, P. (2017). Robust detection in leak-prone population protocols (Vol. 10467 LNCS, pp. 155–171). Presented at the DNA Computing and Molecular Programming, Springer. https://doi.org/10.1007/978-3-319-66799-7_11 chicago: Alistarh, Dan-Adrian, Bartłomiej Dudek, Adrian Kosowski, David Soloveichik, and Przemysław Uznański. “Robust Detection in Leak-Prone Population Protocols,” 10467 LNCS:155–71. Springer, 2017. https://doi.org/10.1007/978-3-319-66799-7_11. ieee: D.-A. Alistarh, B. Dudek, A. Kosowski, D. Soloveichik, and P. Uznański, “Robust detection in leak-prone population protocols,” presented at the DNA Computing and Molecular Programming, 2017, vol. 10467 LNCS, pp. 155–171. ista: Alistarh D-A, Dudek B, Kosowski A, Soloveichik D, Uznański P. 2017. Robust detection in leak-prone population protocols. DNA Computing and Molecular Programming, LNCS, vol. 10467 LNCS, 155–171. mla: Alistarh, Dan-Adrian, et al. Robust Detection in Leak-Prone Population Protocols. Vol. 10467 LNCS, Springer, 2017, pp. 155–71, doi:10.1007/978-3-319-66799-7_11. short: D.-A. Alistarh, B. Dudek, A. Kosowski, D. Soloveichik, P. Uznański, in:, Springer, 2017, pp. 155–171. conference: name: DNA Computing and Molecular Programming date_created: 2018-12-11T11:48:30Z date_published: 2017-01-01T00:00:00Z date_updated: 2022-03-18T12:48:02Z day: '01' doi: 10.1007/978-3-319-66799-7_11 extern: '1' external_id: arxiv: - '1706.09937' language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/1706.09937 month: '01' oa: 1 oa_version: None page: 155 - 171 publication_status: published publisher: Springer publist_id: '6868' quality_controlled: '1' scopus_import: '1' status: public title: Robust detection in leak-prone population protocols type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 10467 LNCS year: '2017' ...