Highly Constrained Discrete Agents for Modeling Natural Systems

Axe : Scilex
Coordinateurs : Matthias Függer et Thomas Nowak
Objectif : Investigate problems from physical, biological, or sociological domains within a distributed computing context.
Financement Labex : 2017

The general scientific aim of the working group is to investigate problems from physical, biological, or sociological domains within a distributed computing context. This includes natural systems, such as bird flocks and slime mold, and man-made systems, such as Very Large Scale Integrated (VLSI) circuits. The focus, hereby, is on natural systems. However, both natural systems and VLSI circuits can similarly be viewed as systems of highly resource limited computing devices, bearing several similarities with modern circuits, rendering a combined study of both topics a promising approach. Further, high speed VLSI circuits (i) have a non-negligible risk of its storage elements becoming metastable, thereby leaving the Boolean abstraction, and (ii) non-negligible propagation delay and jitter, rendering handshake-based solutions a promising alternative.

The idea is to model such systems by multi-agent systems. Computational capabilities and communication primitives of involved agents are typically highly restricted, compared to classical distributed computing settings: In case of a VLSI circuit, an agent will typically have computational power of several gates, and not of a full processing unit with memory. In case of a biological individual, e.g., a bird, computation is typically restricted to computing convex combinations, with “easily” and locally computable weights.

In the working group two specific domains will play a leading role: (i) VLSI circuits, and (ii) swarms of biological individuals, such as birds, fish, and bacteria.

Note that we see the main purpose of the working group in studying and understanding the fundamentals of these systems. We will thus make drastic simplifications in their modeling. For example, when considering bird flocking, environmental forces are not considered and position update rules are by convex combinations of easily computable weights, that depend on an agent’s local view of other agent states, disregarding, e.g., birds obscuring other birds.

By this, we hope to gain a better understanding of which local rules/effects influence swarm behavior, such as convergence rate or stability to faulty individuals.

Note that while physical/natural systems are typically modeled as continuous time systems, e.g., by differential equations, a distributed computing perspective strives for discrete agents operating at discrete points in time by receive-compute-send steps. A priori, it is not clear if a certain discretization introduces artifact behavior: e.g., a stability properties may hold in the continuous model, but not in the discrete agent-based model. We thus also plan to address the discrepancy between discrete and corresponding continuous time models in our studies, comparing convergence and stability properties in corresponding models.

  • Joffroy Beauquier (Université Paris-Sud)
  • Janna Burmann (Université Paris-Sud)
  • Bernadette Charron-Bost (CNRS & Ecole polytechnique)
  • Laurent Fribourg (CNRS & ENS Paris-Saclay)
  • Matthias Függer (CNRS & ENS Paris-Saclay)
  • Jérémie Jakubowicz (Télécom SudParis)
  • Patrick Lambein (Ecole polytechnique)
  • Thomas Nowak (Unversité Paris-Sud)
  • Ami Paz (Technion)
  • Nicolas Sabouret (Université Paris-Sud)
  • Cristina Stoica Maniu (CentraleSupélec)

Associated Post-doc project: DIGIT - Distributed Pulse Generation in Bacterial Colonies.
Coordinators : Matthias F¨ugger & Thomas Nowak
Candidate : Da-Jung Cho
Institutions : LSV, LRI
Administrator laboratory : LSV
Durée & Dates de la mission : En cours

Webpage : Groupe de Travail HicDiesMeus
Events and talks will be announced on this page. Please write an email to Thomas Nowak or Matthias Fuegger if you would like to
participate, or be informed about upcoming talks.
Workshops :
  • November 8, 2018 - Exploiting bacteriophage-derived signals as external wires for biological computing (Manish Kushwaha)
  • July 2, 2018 - Computing with synthetic protocells (Patrick Amar)
  • June 18, 2018 - Bio-inspired Operations: Site-Directed Insertion/Deletion
  • May 22, 2018 - Black Board and Coffee Meeting
  • March 27, 2018 - Visualisation in Circuit Design
  • January 29, 2018 - Black Board and Coffee Meeting
  • December 14, 2017 - Black Board and Coffee Meeting
  • October 5, 2017 - Large Flocks of Small Birds: On the Minimal Size of Population Protocols
  • October 4, 2017 - Verification of population protocols
  • July 25, 2017 - Involution Delay Model: Faithful Delay Prediction in Digital Circuits
  • July 24, 2017 - Engineered Gene Circuits: From Clocks to Synchronized Delivery

Scientifics publications
  • Da-Jung Cho and Yo-Sub Han and Hwee Kim,Bound-decreasing duplication system, journal"Theoretical Computer Science",year "2019",
  • Da-Jung Cho and Yo-Sub Han and Kai Salomaa and Taylor J. Smith, Site-directed insertion: Language equations and decision problems, journal "Theoretical Computer Science, year "2019",
  • Daniel Ohlinger, Jurgen Maier, Matthias Fugger and Ulrich Schmid, the Involution Tool for Accurate Digital Timing and Power Analysis, 2019, 29th International Symposium on Power and Timing Modeling, Optimization and Simulation (PATMOS),

Working on a common ANR project DREAMY in the lines of HicDiesMeus. The project was rejected in the 2nd round. We will resubmit.
  • Organizing the CELLS workshop (Workshop on Computing among Cells)currently in progress.
  • Work with interns on HicDiesMeus related projects:
    • Corbin Hopper (ENS Paris-Saclay): working on phage infection models, wet-lab experiments
    • Quentin Soubeyran (Ecole polytechnique): working on phage infection simulations, analytical models
  • Work in dedicated subgroups:
  • Collaboration with CentraleSupelec:
    • Da-Jung Cho, Matthias Fuegger, Cristina Stoica Maniu, and Thomas Nowak are collaborating with
    • Catherine Bonnet (Inria Paris-Saclay-Ile-de-France, CentraleSupelec) and
    • Lotfi Baour (student at Univ. Cergy-Pontoise)on modeling and analyzing oscillation conditions for E. coli with engineered quorum sensing capabilities.
    • Collaborations with Micalis, INRA:

Continued work on phage infection models, started wet-lab experiments to test for gp3-induced immunity.

Work on orthogonal phage library.
  • Setting up a related ERC project.