Distributed computation with continual population growth - Archive ouverte HAL Access content directly
Journal Articles Distributed Computing Year : 2021

Distributed computation with continual population growth

(1) , (2, 3) , (4, 5, 6) , (5, 7, 8, 9) , (5, 6) , (5, 6, 10)
1
2
3
4
5
6
7
8
9
10

Abstract

Computing via synthetically engineered bacteria is a vibrant and active field with numerous applications in bio-production, bio-sensing, and medicine. Motivated by the lack of robustness and by resource limitation inside single cells, distributed approaches with communication among bacteria have recently gained in interest. In this paper, we focus on the problem of population growth happening concurrently, and possibly interfering, with the desired bio-computation. 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 $\Omega( \sqrt{n \log 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. By combining Nand gates with the majority consensus protocol as an amplifier, it is possible to compute arbitrary Boolean functions. Finally, we extend the protocols to several biologically relevant settings. We simulate a plausible implementation of a noisy Nand gate with engineered bacteria. In the context of continuous cultures with a constant outflow and a constant inflow of fresh media, we demonstrate that majority consensus is achieved only if the flow is slower than the maximum growth rate. Simulations suggest that flow increases consensus time over a wide parameter range. The proposed protocols help set the stage for bio-engineered distributed computation that directly addresses continuous stochastic population growth.
Fichier principal
Vignette du fichier
A_B_Consensus.pdf (1.17 Mo) Télécharger le fichier
Vignette du fichier
Cho2021_Article_DistributedComputationWithCont.pdf (1.36 Mo) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-03519002 , version 1 (10-01-2022)

Licence

Attribution - CC BY 4.0

Identifiers

Cite

Da-Jung Cho, Matthias Függer, Corbin Hopper, Manish Kushwaha, Thomas Nowak, et al.. Distributed computation with continual population growth. Distributed Computing, 2021, ⟨10.1007/s00446-021-00404-8⟩. ⟨hal-03519002⟩
81 View
46 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More