Distributed Computation with Continual Population Growth
share
Computing with synthetically modified bacteria is a vibrant and active field with numerous applications in bio-production, bio-sensors, and medicine. Recently, distributed approaches with communication among bacteria have gained interest, motivated by a lack of robustness and by resource limitations in single cells. In this paper, we focus on the problem of population growth happening in parallel, and possibly interfering, with the desired protocol. Specifically, we present a fast protocol in systems with continuous population growth for the majority consensus problem and prove that it correctly identifies the initial majority among two inputs with high probability if the initial difference is Ω(√(nlog n)) where n is the total initial population. We also present a fast protocol that correctly computes the NAND of two inputs with high probability. Combining both protocols, using the majority consensus protocol as an amplifier stage, it is possible to implement circuits computing arbitrary Boolean functions.
READ FULL TEXT