Working Group HicDiesMeus

Highly Constrained Discrete Agents for Modeling Natural Systems

Description

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.

Members

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

To receive announcements by email, please contact the organizers Matthias Függer and Thomas Nowak.

This working group is supported by Labex DigiCosme (project ANR-11-LABEX-0045-DIGICOSME) operated by ANR as part of the program "Investissement d'Avenir" Idex Paris-Saclay (ANR-11-IDEX-0003-02).

Upcoming Meetings

July 2, 2018 at 4 pm, Espace P. Vaillergues/ Espace N. et C. Batlouni (in the SA zone, 1st floor, near the rooms SA104/SA108), Bouygues building, CentraleSupélec

Computing with synthetic protocells (Patrick Amar)

In this talk I will present a new kind of computing device that uses biochemical reactions networks as building blocks to implement logic gates. The architecture of a computing machine relies on these generic and composable building blocks, computation units, that can be used in multiple instances to perform complex boolean functions. Standard logical operations are implemented by biochemical networks, encapsulated and insulated within synthetic vesicles called protocells. These protocells are capable of exchanging energy and information with each other through transmembrane electron transfer.

In the paradigm of computation we propose, protoputing, a machine can solve only one problem and therefore has to be built specifically. Thus, the programming phase in the standard computing paradigm is represented in our approach by the set of assembly instructions (specific attachments) that directs the wiring of the protocells that constitute the machine itself.

To demonstrate the computing power of protocellular machines, we apply it to solve a NP-complete problem, known to be very demanding in computing power, the 3-SAT problem. We show how to program the assembly of a machine that can verify the satisfiability of a given boolean formula. Then we show how to use the massive parallelism of these machines to verify in less than twenty minutes all the valuations of the input variables and output a fluorescent signal when the formula is satisfiable or no signal at all otherwise.

Past Meetings

June 18, 2018 at 11 am, Espace P. Vaillergues/ Espace N. et C. Batlouni (in the SA zone, 1st floor, near the rooms SA104/SA108), Bouygues building, CentraleSupélec

Black Board and Coffee Meeting (DaJung)

Bio-inspired Operations: Site-Directed Insertion/Deletion

Gene insertion and deletion are basic operations occurring in DNA recombination in molecular biology. Errors in DNA recombination cause mutation that plays a part in normal/abnormal biological processes such as cancer, the immune system, protein synthesis and evolution. Since mutational damage may not be easily identifiable, site-directed mutagenesis that deliberately creates mutation under enzymatic activities in vitro has been studied. From a formal language viewpoint, we characterize site-directed insertion and deletion technique into operations on strings: Given two strings $x$ and $y$, site-directed insertion inserts $y$ into $x$ if an outfix of $y$ matches to infix of $x$, and site-directed deletion partially deletes a substring of $x$ guided by the string $y$. We study closure properties of regular and context-free languages under site-directed insertion/deletion operations, and present efficient algorithms for decision problems related to the operations.

May 22, 2018 at 4 pm, Espace P. Vaillergues/ Espace N. et C. Batlouni (in the SA zone, 1st floor, near the rooms SA104/SA108), Bouygues building, CentraleSupélec

Black Board and Coffee Meeting (Population Protocols)

March 27, 2018 at 11:30 am at ENS Paris-Saclay, Salle de Conférence (Pavillon des Jardins): Ian Jones (Oracle)

Visualisation in Circuit Design

Visualisation techniques can enhance the understanding of circuit behaviour and their operating environment. Visualisation enables exploration of massive quantities of data from a high-level overview right down to low-level detail. During the presentation I will show two short animated movies that address clock domain crossing circuits, and whole-chip clock distribution. These visualisation aids are used to tune and debug designs, and have uncovered problems not found by the standard development tools.

Ian completed his PhD in Electrical Engineering at Imperial College, London in 1986. He was introduced to asynchronous circuit and systems design while working with Sutherland, Sproull and Associates, Inc. In 1987 Ian went to work in the Advanced Technology Group at Apple Computer. At Apple he helped develop a software-programmable gate array chip prototype -- one of his few clocked chip designs. He joined Sun Labs in 1992, which became Oracle Labs in 2010, where he has continued research work focusing on high speed asynchronous circuits and clock domain crossing circuits. Ian works closely with designers in product divisions, applying asynchronous circuit techniques to help improve their products.

January 29, 2018 at 4 pm, Espace P. Vaillergues/ Espace N. et C. Batlouni (in the SA zone, 1st floor, near the rooms SA104/SA108), Bouygues building, CentraleSupélec

Black Board and Coffee Meeting (Asymptotic Consensus)

December 14, 2017 at 3:30 pm in room C3.20, Bréguet Building, CentraleSupélec

Black Board and Coffee Meeting

October 5, 2017 at 3 pm at LSV, ENS Paris-Saclay, LSV library: Javier Esparza (TU München)

Large Flocks of Small Birds: On the Minimal Size of Population Protocols

Population protocols are a well established model of distributed computation by mobile finite-state agents with very limited storage. A classical result establishes that population protocols compute exactly predicates definable in Presburger arithmetic. We initiate the study of the minimal amount of memory required to compute a given predicate as a function of its size. We present results on the predicates x \geq n for n>0, and more generally on the predicates corresponding to systems of linear inequalities. We show that they can be computed by protocols with O(log n) states (or, more generally, logarithmic in the coefficients of the predicate), and that, surprisingly, some families of predicates can be computed by protocols with O(\log\log n) states. We give essentially matching lower bounds for the class of 1-aware protocols.

This is a seminar of the INFINI research team: http://www.lsv.fr/axes/INFINI/infini?l=en

October 4, 2017 at 2 pm at LRI, Université Paris-Sud, salle 445: Javier Esparza (TU München)

Verification of population protocols

Population protocols (Angluin et al., PODC 2004) are a formal model of sensor networks consisting of identical, finite-stae mobile devices. When two devices come into the range of each other, they interact and change their states. Computations are infinite sequences of pairwise interactions where the interacting processes are picked by a fair scheduler.

A population protocol is well specified if for every initial configuration C of devices and for every fair computation starting at C, all devices eventually agree on a consensus value that only depends on C. If a protocol is well-specified, then it is said to compute the predicate that assigns to each initial configuration its consensus value. The main two verification problems for population protocols are: Is a given protocol well-specified? Does a given protocol compute a given predicate ?

While the class of predicates computable by population protocols was already established in 2007 (Angluin et al., Distributed Computing), the decidability of the verification problems remained open until 2015, when my colleagues and I finally proved it (Esparza et al., CONCUR 2015, improved version to appear in Acta Informatica). However, the complexity of our decision procedures is very high. We have recently identified a class of procotols that, while being as expressive as the complete class, is far more tractable. I report on these results, and on some experimental results.

July 25, 2017 at 2 pm at LRI, Université Paris-Sud, salle 465: Jürgen Maier (Vienna University of Technology)

Involution Delay Model: Faithful Delay Prediction in Digital Circuits

Rapid developements in circuit design over the last decades have not only led to an increased performance at lower area requirements but also increased the complexity to accurately model the signal traces, such that analog simulation tools like SPICE nowadays quickly reach their limit with increasing size. Therefore high level approaches, which abstract certain parts of the circuit, are required to achieve a reasonable computational effort while still maintaining an adequate accuracy.

In this talk I will present our digital involution delay model that faithfully predicts signal delays in electronic circuits. Faithful in this sense means that a circuit can only be modelled if it can be implemented in actual hardware and vice versa. The delay of a single transition is determined as a function f(T) with T being the previous-output-to-input transition time difference and f(.) an involution, i.e., fulfilling -f(-f(T)) = T. Compared to the established pure and inertial delay our approach allows accurate modeling of pulse degradation effects, which become very important for example for power estimations.

Despite the good results we already achieved the model is far from being finished. I will therefore also present some extensions we are currently investigating such as introducing non-determinism, reducing the characterization effort or increasing the accuracy.

July 24, 2017 at 11 am at ENS Paris-Saclay, Bâtiment d'Alembert, Salle Condorcet (niveau 2): Jeff Hasty (University of California, San Diego)

Engineered Gene Circuits: From Clocks to Synchronized Delivery

Intracellular variability is a major obstacle to the fidelity required for a genetic circuit to execute a series of "pre-programmed" instructions. Over the past five years we have explored how determinism can arise from the synchronization of a large number of cells; in other words, synchronize gene circuits operating in individual cells and view the colony as the primary design element. We are currently using our understanding of these processes to engineer bacteria for the safe production and delivery of anti-tumor toxins. The long-held monolithic view of bacteria as pathogens has given way to an appreciation of the widespread prevalence of functional microbes within the human body. Given this vast milieu, it is perhaps inevitable that certain bacteria would evolve to preferentially grow in environments that harbor disease and thus provide a natural platform for the development of engineered therapies. We have engineered a clinically relevant bacterium to lyse synchronously at a threshold population density and to release genetically encoded cargo. Following quorum lysis, a small number of surviving bacteria reseed the growing population, thus leading to pulsatile de- livery cycles. Working with Sangeeta Bhatia (MIT) and Tal Danino (Columbia), we have begun to demonstrate the therapeutic potential of the bacteria in animal models using luciferase to monitor in vivo bacterial population dynamics. This work represents our early progress in transversing the scales of Synthetic Biology from the level of mathematically designed circuitry to therapeutically relevant animal models.

See here for details: https://parsys.lri.fr/seminar-hasty.html