Robust Detection in Leak-Prone Population Protocols

Abstract : 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.
Type de document :
Communication dans un congrès
DNA 2017 - 23rd International Conference DNA Computing and Molecular Programming, Sep 2017, Austin, TX, United States. Springer, LNCS, 10467, pp.155-171, 2017, DNA Computing and Molecular Programming. 〈10.1007/978-3-319-66799-7_11〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01669203
Contributeur : Adrian Kosowski <>
Soumis le : mercredi 20 décembre 2017 - 16:13:11
Dernière modification le : jeudi 11 janvier 2018 - 06:28:03

Identifiants

Collections

Citation

Dan Alistarh, Bartlomiej Dudek, Adrian Kosowski, David Soloveichik, Przemyslaw Uznanski. Robust Detection in Leak-Prone Population Protocols. DNA 2017 - 23rd International Conference DNA Computing and Molecular Programming, Sep 2017, Austin, TX, United States. Springer, LNCS, 10467, pp.155-171, 2017, DNA Computing and Molecular Programming. 〈10.1007/978-3-319-66799-7_11〉. 〈hal-01669203〉

Partager

Métriques

Consultations de la notice

28