Report

Teaser, summary, work performed and final results

Periodic Reporting for period 3 - DBA (Distributed Biological Algorithms)

Teaser

Biologists are is seeking for rigorous tools to understand complex, interactive, and dynamic biological ensembles. This project suggests that a holistic approach to biology could benefit from theoretical algorithmic investigations. Our general perspective is to view biological...

Summary

Biologists are is seeking for rigorous tools to understand complex, interactive, and dynamic biological ensembles. This project suggests that a holistic approach to biology could benefit from theoretical algorithmic investigations. Our general perspective is to view biological ensembles as composed of probabilistic agents that aim to collectively solve certain computational tasks. Our approach is, first, to translate the biological process into a formal algorithmic model and then mathematically analyze the model while aiming to gain fundamental understandings regarding the behavior of the motivating biological process. We concentrate our experimental studies on several selected biological systems, including ant colonies and bat groups.

Analyzing biological processes, we focus our attention on the following objectives: (1) identify quantitative connections between computational resources, (2) analyze biological processes and evaluate performances using algorithmic measures, (3) identify the algorithmic challenges that the biological systems face (e.g., using lower bounds), and (4) explain empirical observations based on rigorous algorithmic analysis. Overall, to illustrate the impact of our methodology, we aim to obtain predictions based on theoretical algorithmic considerations and then verify them empirically by designing suitable experiments. The project contains three related tasks. Task A considers searching and navigation by biological organisms, Task B considers algorithmic aspects in foraging ants and bats, and Task C considers opinion formation problems, such as consensus and rumor spreading.

Work performed

\"Overall, the project has proceeded even better than expected. The action\'s implementation is highly positive and follows the expected time schedule. Indeed, significant advances are indicated by intermediate results related to all tasks A, B, and C. In particular, the project has yielded several publications that were published in prestigious venues in both computer science and biology. In addition to these publications, we are currently conducting several research projects that are highly promising.

Below I provide references to several of the selected publications (omitting the list of authors, for brevity):

A. Navigation in unreliable environments.

[1] \"\"A locally-blazed ant trail achieves efficient collective navigation despite limited information\"\", eLife 2016.

[2] \"\"Searching a Tree with Permanently Noisy Advice\"\", ESA 2018.

Paper [1] studies collaborative transport by ants and discovers a new kind of ant trail. The paper concerns mostly Task A and partially Task B, and provides advances with respect to Objectives 2 and 3. It has received significant media coverage, including articles centered around it in \"\"Le Monde\"\" and \"\"Haaretz\"\" daily newspapers. Paper [2] introduces a new model of search with noisy advice, focusing on tree structures.

B. On the importance of forming stable structures in biological systems.

[3] \"\"Minimizing Message Size in Stochastic Communication Patterns: Fast Self-Stabilizing Protocols with 3 bits\"\", Distributed Computing, 2019. (Extended abstract in SODA 2017.)

[4] \"\"Breathe before Speaking: Efficient Information Dissemination despite Noisy, Limited and Anonymous Communication\"\", Distributed Computing, 2017.

[5] \"\"Limits on reliable information flows through stochastic populations\"\", PLoS Computational Biology 14(6), 2018. (Extended abstract in ITCS 2018.)

These papers concern Task C and indicate advances with respect to Objective 3. We consider a small group of agents that have reliable knowledge that needs to be transmitted to other agents. In [4,5] communication is noisy. When the structure is stable it is known that the noise can be overcome to yield efficient distributed computations. However, when there is no structure, and the pattern of communication is random, we show in [5] that when all facets of the communication are noisy, even the most basic task of broadcast cannot be completed efficiently. We further demonstrated this fundamental lower bound through an experiment in Cataglyphis niger ants. The general theoretical lower bound implies that in order to overcome inherent noise in communication, biological systems should either form stable structures (e.g., the brain) or strive to obtain a non-noisy component of the communication, and rely on it. [3] demonstrates that when the communication is not noisy, distributed computations can still be very efficient, even under many other conditions of unreliability and lack of structure. The combination of [3-5] shows that under noisy communication, there is an exponential separation between the PUSH and PULL models of communication. This is a surprising result, as these two models were typically considered as equivalent.

C. Parallel search and foraging.

[6] \"\"The ANTS Problem\"\", Distributed Computing 2017.

[7] \"\"Parallel Bayesian Search with No Coordination\"\", J. ACM 2019. (Extended abstract in STOC 2016.)

[8] \"\"Intense Competition can Drive Selfish Explorers to Optimize Coverage\"\", SPAA 2018.

[9] \"\"Multi-Round Cooperative Search Games with Multiple Players\"\", ICALP 2019.

These papers concern Task B and partially Task A, and indicate advances with respect to Objective 1. Paper [6] establishes the basic framework for relating information parameters and time efficiency parameters with respect to central search foraging. Paper [7] refines the time lower and upper bounds for parallel search and establishes simple and efficient algorithms operating over multiple rounds. These papers highlight the significance of non-coordinating algorithms\"

Final results

In general, our studies at the forefront of distributed computing and algorithm theory introduce new methodologies for studying collective animal behavior. Indeed, theoretical investigations that accompany biological experiments are typically based on computer simulations, or on analysis based on PDE. In contrast, a proof-based algorithmic investigation of the fundamental properties of the underlying process is highly uncommon. Demonstrating the usefulness of this approach is one of the main goals of the project. We demonstrated this methodology in two of our papers. In [1] we discovered a new kind of ant trail. This discovery is expected to attract significant interest from the community of collective animal behavior. In order to study the rationale behind this novel behavior, we used algorithmic analysis to understand the computational challenges faced by ants and show how the new kind of ant trail can be used to overcome these challenges. The paper received considerable media coverage and articles centered around it appeared in “Le Monde” and “Haaretz” daily newspapers. In [5] we established lower bounds theorems that are general enough to constrain a vast class of computational systems, including many from the realm of biology. We complemented our theoretical finding by providing empirical support concerning the noisy recruitment process employed by desert ants. To the best of our knowledge, this paper is the first ever in which lower bounds from computer science have been demonstrated by experiments on animal behavior!

Analyzing biological processes through an algorithmic perspective was also done in [12]. This paper provides new lower and upper bounds for random walk processes with multiple step-lengths, that have been observed empirically in numerous species across taxa.

Focusing on the computational challenges faced by biological systems allowed us to obtain a fresh look at computational models in general. This led to the initiation of several types of models that are expected to find interest in the theoretical computer science community. For example, Papers [6-9] initiated the problems of non-coordinating search. Papers [4,5] initiated the computational study of noise in communication in the context of stochastically interacting agents, a new subject at the interface of computer science, physics and biology. Paper [2] introduces a new model of search with noisy advice.

Regarding future work, we are currently in the process of studying several promising research topics, all of which are expected to be completed by the end of the project. Below is a short description of these.

1. A large experimental study with theoretical insights on the foraging strategies of Leptonycteris bats is almost ready for submission (Task B.2). This study, encapsulating several years of work, collects and analyzes unprecedently large amounts of data regarding the foraging decisions of bats in the field.

2. A large experimental study with theoretical insights on collective navigation by P. longicornis ants (Task A.3) has just been submitted to a prestigious biology journal. This work too took several years of work. The corresponding experiment was conducted by the group of Prof. Feinerman. The experiment aims to identify the level of locality in the ants’ algorithm, as they collectively navigate in a percolated environment.

3. We theoretically study the computational benefits of utilizing a Levy flight type of search process (Task A.1). Due to numerous empirical observations of such processes across taxa, this question has received a large amount of attention from biologists and physicists during the last two decades, yielding dozens of papers in prestigious biological journals. So far the theoretical evidence for the optimality of such processes in higher dimensions than 1 was not overwhelming. Our study takes a different perspective to previous work, questioning the ability of a search process to find targets of varying

Website & more info

More info: https://amoskorman.com/dba.