---
_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'
...