Speed faults in computation by chemical reaction networks

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 not rely on 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 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 predicates stably decidable by CRNs guaranteed to avoid speed faults are precisely the detection predicates: Boolean combinations of questions of the form "is a certain species present or not?". This implies, for instance, that no speed fault free CRN decides whether there are at least two molecules of a certain species—i.e., speed fault free CRNs "can't count".

Additional details