2018 |DIGIT: Distributed Pulse Generation in Bacterial Colonies 

Axe & tâche scientifique DigiCosme : SciLex – IID
Coordinateurs : Matthias Függer et Thomas Nowak
Nom & Prénom du Candidat : Da-Jung Cho
Laboratoires :

  • Paris Saclay :
    • LSV, ENS Paris-Saclay
    • LRI, Unversité Paris-Sud

Adossé à l’action DigiCosme : GT HicDiesMeus
Durée & Dates de la mission : 1 an – start during March-June 2018

Contexte :
General goal of the post-doc is to work in a research team on the fundamentals for realistic distributed algorithms in bacterial colonies. While the focus is on theory of distributed algorithms, formal models and complexity analysis, collaboration with experts from synthetic biology, chip design, and control theory is central to our research team.

Objectif :
Aim of this research program is to study fault-tolerant distributed pulse generation algorithms in the context of bacterial colonies: bacteria sense and produce certain proteins in synchronized, periodic intervals, despite faults induced by harsh environmental conditions or bacteria deviating for their protocol.

The focus on pulse generation algorithms is motivated by their fundamental role in distributed computing, their non-trivial dynamic behavior, and our previous scientific background.

The project’s contribution will be in the domain of distributed computing and microbiological systems.
The fundamental computational and communication resource constraints of algorithms intended to be implemented into bacteria pose strong limitations on candidate algorithms: limited computational power and broadcasting techniques, highly unstable communication topologies, pronounced noise, potentially non-digital signal shapes, etc. Fault-tolerant distributed computing and circuit design communities have developed techniques to design robust and fault-tolerant algorithms and circuits, and thus present a promising line of attack to these challenges. We will study the problem of pulse generation algorithms along these attack lines.

Hereby the project’s focus is on:
(i) The study of models that are sufficiently simple to be analyzable by means of algorithmic analysis,
but sufficiently accurate to reproduce important aspects observed in simulations and experimental data.

(ii) The design and the algorithmic analysis of candidate algorithms.

Productions Scientifiques :
There is a multitude of highly relevant open problems related to fault-tolerant pulse generation algorithms for implementation in bacteria that reach from simulation, modeling, algorithm design and analysis, to experimental evaluation.
The focus in this project is on distributed, algorithmic design and analysis, which itself is challenging under the highly restrictive constraints upon algorithms intended to be implemented in bacteria.
We would like to note here that the algorithm design will be driven by realistic assumptions on bacteria, with intended physical implementation later on. Further, communication model assumptions will be tested in simulations and potentially by extracting data from.

Central objective is to demonstrate that a non-trivial problem like fault-tolerant pulse generation from microbiology profits from a combined distributed computing and VLSI approach.

In the following we list several sub-goals along this road, together with their deliverables. Note that while deliverables represent important milestones, the major goal in all these tasks is research-centered, i.e., finding a methodology.

(i) Realistic communication assumptions: Outcome will be a realistic, but sufficiently simple, communication model.
(ii) Approximate agreement and pulse generation: Outcome will be candidate distributed algorithms for approximate agreement and clock synchronization and their correctness proofs.
(iii) Metastability-containing circuits: Outcome will be a metastability-containing circuit level implementation of a candidate algorithm. Central to this outcome is its implementability in bacteria such as E. coli.