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)

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).

We are looking for excellent candidates for a 1-year post-doc position in the area of distributed algorithms in microbiological systems for our working group HicDiesMeus.

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.

- Start: between March and June 2018
- Duration: 1 year
- Location: ENS Paris-Saclay and Universite Paris Sud, both located near Paris, France

For more information regarding the position please contact Matthias Fuegger and Thomas Nowak by mail. For applications, please include:

- a curriculum vitae
- a complete list of your publications

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

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.

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.

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