6th Workshop on Biological Distributed Algorithms
July 23rd, 2018 in London (Egham), UK
We are excited to announce the 6th workshop on Biological Distributed Algorithms (BDA). BDA is focused on the relationships between distributed computing and distributed biological systems and in particular, on analysis and case studies that combine the two. Such research can lead to better understanding of the behavior of the biological systems while at the same time developing novel algorithms that can be used to solve basic distributed computing problems.
BDA 2018 will include talks on distributed algorithms related to a variety of biological systems. We will devote special attention to communication and coordination in insect colonies (e.g. foraging, navigation, task allocation, construction) and networks in the brain.
Pre-selected invited speakers
- Vijay Balasubramanian, U Penn [website]
- Luca Cardelli, Microsoft Research [website]
- Roderich Gross, U Sheffield [website]
- Yoram Moses, Technion [website]
- Ana Sendova-Franks, UWE Bristol [website]
- Damien Woods, Inria [website]
Schedule
08:20 - 08:30 - Organziers Welcome
Ants and stochastic systems
08:30 - 09:00 - Ana Sendova-Franks, UWE Bristol [Invited] [slides]
Title: Distributed Algorithms and Universality of Individual Movement in Ant Colonies
09:00 - 09:20 - Chism, Marquardt, and Dornhaus [slides]
Title: The influence of nest architecture on colony organization in ants
Abstract:
We initiate the study neural networks frNest architecture in ants is an example of an extended phenotype, present across many social insect taxa. ‘Extended phenotypes’ are organism traits that extend into the environment: for example, in social insects, the nest, built by the colony, then can serve as a mechanism for microclimate regulation. Much attention has been given how the organism’s behavior shapes the extended phenotype, while the potential feedback from the phenotype (e.g. nest architecture) onto the colony’s behavior has been largely unexplored. The ant Temnothorax rugatulus provides an ideal model system to investigate the effects of nest architecture on colony organization, thus providing insight into the interactions between extended phenotypes and behavioral traits. We tested the hypotheses that (i) nest architecture affects worker and brood spatial distribution, in particular (ii) that nest architecture would determine extent and distribution of spatial fidelity zones (‘micro-territories’) of workers in the nest, and that (iii) nest architectures promote different queen movement patterns. Besides investigating the feedback between nest architecture and colony organization, our results provide insights into mechanisms of task allocation (worker task choices), since the spatial distributions of workers and brood affect how often different workers are likely to encounter task stimuli (e.g. brood). Our results illuminate the direct proximal influences of the extended phenotype on division of labor in social insects.
09:20 - 09:30 - Imrie and Herrmann [slides]
Title: Biologically Inspired Self-Organised Spatial Formation in Swarms using Turing Patterns
09:30 - 09:40 - Cannon, Daymude, Gokman, Randall, Richa [slides]
Title: A Local Stochastic Algorithm for Separation in Heterogeneous Self-Organizing Particle Systems
Abstract:
We investigate stochastic, distributed algorithms that can accomplish separation and integration behaviors in self-organizing particle systems, an abstraction of programmable matter. These particle systems are composed of individual computational units known as particles that each have limited memory, strictly local communication abilities, and modest computational power, and which collectively solve system-wide problems of movement and coordination. In this work, we extend the usual notion of a particle system to treat heterogeneous systems by considering particles of different colors. We present a fully distributed, asynchronous, stochastic algorithm for separation, where the particle system self-organizes into clustered color classes using only local information about each particle's preference for being near others of the same color. We rigorously analyze the correctness and convergence of our distributed, stochastic algorithm by leveraging techniques from Markov chain analysis, proving that under certain mild conditions separation occurs with high probability. These theoretical results are complemented by simulations.
09:40 - 10:00 - Boczkowski, Feinerman, Korman, and Natale [slides]
Title: Limitations on Information Dissemination via Noisy Communication and Implications to Animal Group Behavior
Abstract:
Biological systems can share and collectively process information to yield emergent effects, despite inherent noise in communication. While man-made systems often employ intricate structural solutions to overcome noise, the structure of many biological systems is more amorphous. It is not well understood how communication noise may affect the computational repertoire of such groups. To approach this question we consider the basic collective task of rumor spreading, in which information from few knowledgeable sources must reliably flow into the rest of the population.
In order to study the effect of communication noise on the ability of groups that lack stable structures to efficiently solve this task, we consider a noisy version of the uniform PULL model. We prove a lower bound which implies that, in the presence of even moderate levels of noise that affect all facets of the communication, no scheme can significantly outperform the trivial one in which agents have to wait until directly interacting with the sources. Our results thus show an exponential separation between the uniform PUSH and PULL communication models in the presence of noise. Such separation may be interpreted as suggesting that, in order to achieve efficient rumor spreading, a system must exhibit either some degree of structural stability or, alternatively, some facet of the communication which is immune to noise.
We corroborate our theoretical findings with a new analysis of experimental data regarding recruitment in Cataglyphis niger desert ants.
10:00 - 10:10 - Umino, Kitamura, and Izumi [slides]
Title: Differentiation in Population Protocols
Abstract:
Recently the population protocol model attracts much attention as a theoretical model connecting distributed computing with natural systems. In this study, we propose the R-generalized partition problem (GPP(R)). The goal of this problem is to divide all agents into several groups whose sizes follow a given ratio R. An instance of the generalized partition problem is specified by a tuple of integers R=(a_1, a_2, ... , a_{k}).There are several results for the partition problem in population protocol models. The first paper considering that problem is by Yasumi et al., where the algorithm for the uniform bipartition problem (i.e., forming two N/2 groups) is presented, as well as its self-stabilizing matters. The follow-up work by Yasumi et al. considers the uniform k-partition problem for any constant k > 1, and proposes the algorithm using 3k - 2 states. While both of the results consider only the case of uniform partition, it is possible to solve GPP(R) by using any uniform k-partition algorithm: First, we divides all the agents into uniform sum_i a_i groups, and then decodes each group ID properly. However, the space complexity of this approach inherently requires Omega(sum_i a_i) states. In this paper, we propose an algorithm uses O(sum_i log_2 a_i) states, which substantially improves the algorithm based on the uniform partition.
10:10 - 10:30 - Mallmann-Trenn, Pajak, Lynch, Radeva, and Dornhaus [slides]
Title: Self-Stabilizing Task Allocation In Spite of Noise
Abstract:
We study the problem of distributed task allocation inspired by the behavior of social insects, which perform task allocation in a setting of limited capabilities and noisy environment feedback. We assume that each task has a demand that should be satisfied but not exceeded, i.e., there is an optimal number of ants that should be working on this task at a given time. The goal is to assign a near-optimal number of workers to each task in a distributed manner and without explicit access to the values of the demands nor the number of ants working on the task.
We seek to answer the question of how the quality of task allocation depends on the accuracy of assessing whether too many (overload) or not enough (lack) ants are currently working on a given task. Concretely, we address the open question of solving task allocation in the model where each ant receives feedback that depends on the deficit defined as the (possibly negative) difference between the optimal demand and the current number of workers in the task. The feedback is modeled as a random variable that takes value lack or overload with probability given by a sigmoid of the deficit. Each ants receives the feedback independently, but the higher the overload or lack of workers for a task, the more likely it is that all the ants will receive the same, correct feedback from this task; the closer the deficit is to zero, the less reliable the feedback becomes. We measure the performance of task allocation algorithms using the notion of regret, defined as the absolute value of the deficit summed over all tasks and summed over time.
We propose a simple, constant-memory, self-stabilizing, distributed algorithm that quickly converges from any initial distribution to a near-optimal assignment. We also show that our algorithm works not only under stochastic noise but also in an adversarial noise setting. Moreover we show a lower bound on the regret for any constant-memory algorithm, which matches, up to a constant factor, the regret achieved by our algorithm.
10:30 - 11:00 - Coffee Break 1
11:00 - 11:30 - Damien Woods, Inria [Invited] [slides]
Title: Molecular computation with DNA self-assembly
11:30 - 11:50 - Rashid, Taubenfeld, and Bar-Joseph [slides]
Title: Genome Wide Epigenetic Modifications as a Shared Memory Consensus Problem
Abstract:
A distributed computing system is a collection of processors that
communicate either by reading and writing from a shared memory or
by sending messages over some communication network.
Most prior biologically inspired distributed computing methods, especially those that are based on ideas from molecular biology, rely on message passing. Here we model the process of genome wide epigenetic modifications which allow cells to utilize the DNA, as a shared memory system. We do so by formulating a particular consensus problem for the shared memory model, and then present algorithms, derive upper bounds on run time and discuss, analyze and simulate improved methods for solving the problem. The computational results enable us to understand the biological process of genome wide epigenetic modifications better.
11:50 - 12:20 - Luca Cardelli, Microsoft Research [Invited] [slides]
Title: Programming with Chemical Reactions
12:20 - 12:30 - Becchetti, Bonifaci, and Natale [slides]
Title: Pooling or Sampling: Collective Dynamics for Electrical Flow Estimation
Abstract:
The computation of electrical flows is a crucial primitive for many
recently proposed optimization algorithms on weighted networks.
While typically implemented as a centralized subroutine, the ability
to perform this task in a fully decentralized way is implicit in a
number of biological systems. Thus, a natural question is whether
this task can provably be accomplished in an efficient way by a
network of agents executing a simple protocol.
We provide a positive answer, proposing two distributed ap-
proaches to electrical flow computation on a weighted network:
a deterministic process mimicking Jacobi’s iterative method for
solving linear systems, and a randomized token diffusion process,
based on revisiting a classical random walk process on a graph
with an absorbing node. We show that both processes converge to
a solution of Kirchhoff’s node potential equations, derive bounds
on their convergence rates in terms of the weights of the network,
and analyze their time and message complexity.
12:30 - 13:30 - Lunch Break
Neuroscience and related
13:30 - 14:00 - Vijay Balasubramanian, UPenn [Invited] [slides]
Title: The brain
distributes computation to function efficiently
14:00 - 14:10 - Chandrasekhar and Navlakha [slides]
Title: A distributed algorithm for generating Pareto-optimal neural arbors
Abstract:
Neural arbors can be viewed as graphs connecting the cell body of the neuron to various post-synaptic partners. Several constraints have been proposed on the topology of these graphs, including minimizing the total amount of wire necessary for constructing the arbor (wiring cost), and minimizing the graph distances between the cell body and synapses (conduction delay). These two objectives compete with each other --- optimizing one results in poorer performance on the other --- raising the question how well neural arbors balance this network design trade-off. Here, we describe how well neural arbors resolve this trade-off using the theory of Pareto optimality. We describe a simple centralized algorithm that closely approximates Pareto-optimal topologies, and we use this algorithm to study how close neural arbors come to realizing Pareto-optimal topologies. Analyzing 5544 neural arbors, we demonstrate that neural arbors are much closer to Pareto-optimal than would be expected by chance and other reasonable baselines, indicating the utility of these two principles for explaining neural arbor topology. Finally, we propose a distributed algorithm that attempts to construct Pareto-optimal arbors in a manner consistent with putative growth processes of neurons.
14:10 - 14:20 - Rinkus [slides]
Title: Sparse distributed representations, hierarchy, critical periods, metaplasticity: The keys to lifelong fixed-time learning and best-match retrieval
Abstract:
Among the more important hallmarks of human intelligence, which any artificial general intelligence (AGI) should have, are the following.
1.It must be capable of on-line learning, including with single/few trials.
2.Memories/knowledge must be permanent over lifetime-long durations, i.e., not subject to catastrophic forgetting. Some confabulation, i.e., semantically plausible retrieval errors, may gradually accumulate over time.
3.The time to both: a) learn a new item; and b) retrieve the best-matching / most relevant item(s), i.e., do similarity-based retrieval, must remain constant throughout the lifetime.
4.The system should never become full: it must remain able to store new information, i.e., make new permanent memories, throughout very long lifetimes.
No artificial computational system has been shown to have all these properties. Here, we describe a neuromorphic associative memory model, Sparsey, which does, in principle, possess them all. We cite prior results supporting possession of hallmarks 1 and 3. We sketch the argument that it possesses hallmarks 2 and 4, the empirical validation of which is our current primary research focus.
14:20 - 14:40 - Dasgupta, Sheehan, Stevens, and Navlakha [slides]
Title: A neural approach to novelty detection
14:40 - 14:50 - Cruciani, Natale, and Scornavacca [slides]
Title: On the Metastability of Quadratic Majority Dynamics on Clustered Graphs and its Biological Implications
Abstract:
We investigate the behavior of a simple majority dynamics on network topologies that exhibit a clustered structure. By leveraging recent advancements in the analysis of dynamics, we prove that, when the initial states of the nodes are randomly initialized or when they satisfy a slight bias condition, the network rapidly and stably converges to a configuration in which the clusters maintain internal consensus on two different states. This is the first analytical result on the behavior of dynamics for non-consensus problems on non-complete topologies, based on the first symmetry-breaking analysis in such setting. Our result has implications in different contexts in which dynamics are adopted for biological modeling purposes.
In the context of evolutionary biology, dynamics such as the Moran process have been used to model the spread of mutations in genetic populations. Our result shows that, when the probability of adoption of a given mutation by a node of the evolutionary graph depends super-linearly on the frequency of the mutation in the neighborhood of the node, and the underlying evolutionary graph has a clustered structure, there is a non-negligible probability for species differentiation to occur.
In the context of neuroscience, evolutionary graph dynamics have been used to model the innervation of synapses on muscular junctions during development. Our result, corroborated by numerical simulations on a wider class of dynamics, provide evidence that, in order for the model to comply with experimental evidence on the outcome of the innervation process, either the innervation sites do not exhibit spatial bottlenecks or the dynamics cannot be based on majority-like mechanisms.
Robots and swarms
14:50 - 15:00 - Augustine and Moses Jr [slides]
Title: Dispersion of Mobile Robots: A Study of Memory-Time Trade-offs
Abstract:
We model cooperation among insects using the framework of mobile robots on a graph. Within this framework, we propose and study the problem of dispersion. In this problem, $n$ robots are placed in an $n$ node graph arbitrarily and must coordinate with each other to reach a final configuration such that exactly one robot is at each node. We study this problem through the lenses of minimizing the memory required by each robot and of minimizing the number of rounds in a synchronous system required to achieve dispersion.
Dispersion is of interest for three reasons. First, in the context of insect coordination, this problem asks that if a group of insects were arbitrarily moved around due to some external event (eg. a sudden landslide or strong wind), could they quickly coordinate and cover a designated area of space (let the graph represent a discretization of this space). Second, from a theoretical perspective, dispersion is related to the problems of scattering on a graph, exploration using mobile robots, and load balancing on a graph and results for dispersion shed light on these other problems. Third, a solution to dispersion has an immediate real world application due to its relationship to the problem of recharging electric cars, as each car can be considered a robot and recharging stations and the roads connecting them nodes and edges of a graph respectively. Since recharging is a costly affair relative to traveling, we want to distribute these cars amongst the various available recharge points where communication should be limited to car-to-car interactions.
We provide lower bounds on both the memory required for robots to achieve dispersion and the minimum running time to achieve dispersion on any type of graph. We then analyze the trade-offs between time and memory for various types of graphs. We provide deterministic asymptotically time optimal and memory optimal algorithms for several types of graphs and show the power of having more memory or knowing all robots start at the same node in terms of running time.
15:00 - 15:30 - Coffee Break 2
15:30 - 16:00 - Roderich Gross, U Sheffield [Invited] [slides]
Title: Less is More? Controlling Swarms and Turing Learning
16:00 - 16:20 - Talamali, Marshall, Bose, and Reina [slides]
Title: Count to ten before speaking: Strategies to improve decision accuracy in a robot swarm
Abstract:
Designing decentralised algorithms to control
robot swarms presents a major research challenge. Here we
investigate a decentralised value-sensitive decision-making algorithm
inspired by house-hunting honeybees. A key control
parameter in our study represents the ratio of interactive and
independent behaviours by robots. Optimal parameterisation
requires knowledge of the number of options under consideration,
which the swarm should not possess. Here we show
that a robot swarm is able to find the best option without
knowing the number of alternatives available when the control
parameter is increased over time. This enables swarms of
simulated robots to converge on the best available option,
even when outnumbered by lower quality, easier to discover
options. Similar abilities have been demonstrated in social insect
colonies, and reproducing these in artificial systems is of
great potential benefit for swarm engineering.
16:20 - 16:30 - Gmyr, Hinnenthal, Kostitsyna, Kuhn, Rudolph, Scheideler, and Strothmann [slides]
Title: Forming Tile Shapes With Simple Robots
Abstract:
Motivated by the problem of manipulating nanoscale materials, we investigate the problem of reconfiguring a set of tiles into certain shapes by robots with limited computational capabilities. As a first step towards developing a general framework for these problems, we consider the problem of rearranging a connected set of hexagonal tiles by a single deterministic finite automaton. After investigating some limitations of a single-robot system, we show that a feasible approach to build a particular shape is to first rearrange the tiles into an intermediate structure by performing very simple tile movements. We introduce three types of such intermediate structures, each having certain advantages and disadvantages. Each of these structures can be built in asymptotically optimal $O(n^2)$ rounds, where $n$ is the number of tiles. As a proof of concept, we give an algorithm for reconfiguring a set of tiles into a triangle through one of the intermediate structures.
16:30 - 16:50 - Pavlic, Hanson, Valentini, Walker, Pratt [slides]
Title: Quorum sensing without counting, a discounting approach, or: Nobody goes there anymore, it’s too crowded
Abstract:
Quorum sensing is ubiquitous in nature, but the underlying mechanisms that individuals use to sense quorums are not well understood beyond bacterial quorum sensing. Encounter rate appears to be an important cue of quorum attainment in ants, but how ants synthesize their individual-level experiences to determine whether they have reached a critical encounter rate is still unknown. Computer scientists have suggested quorum-sensing strategies that are implemented on an individual agents with some way to count discrete encounters with other individuals. Instead, motivated by observations of honeybees and classic research on temporal discounting in psychology, we propose a quorum sensing algorithm based on the likelihood that an ant will re-encounter a nest entrance within a short time period of the last encounter with another ant. Simulations of the resulting mechanism show both outcome and response-time characteristics that are qualitatively similar to ants, and the implementation does not require maintaining a count of previous encounters with other agents.
16:50 - 17:00 - Collet and Korman [slides]
Title: Intense Competition can Drive Selfish Explorers to Optimize Coverage
Abstract:
We consider a game-theoretic setting in which selfish individuals compete over resources of varying quality. The motivating example is a group of animals that disperse over patches of food x of different abundances f(x). In such scenarios, individuals are biased towards selecting the higher quality patches, while, at the same time, aiming to avoid costly collisions or overlaps. Our goal is to investigate the impact of collision on the parallel coverage of resources by the whole group.
Consider M sites, where a site x has value f(x). We think of f(x) as the reward associated with site x, and assume that if a single individual visits x exclusively, it receives this exact reward. Typically, we assume that if l>1 individuals visit x then each receives at most f(x)/l. In particular, when competition costs are high, each individual might receive an amount strictly less than f(x)/l, which could even be negative. Conversely, modeling cooperation at a site, we also consider cases where each one gets more than f(x)/l. There are k identical players that compete over the rewards. They independently act in parallel, in a one-shot scenario, each specifying a single site to visit, without knowing which sites are explored by others. The group performance is evaluated by the expected coverage, defined as the sum of f(x) over all sites that are explored by at least one player. Since we assume that players cannot coordinate before choosing their site we focus on symmetric strategies.
The main takeaway message of this paper is that the optimal symmetric coverage is expected to emerge when collision costs are relatively high, so that the following ``Judgment of Solomon'' type of rule holds: If a single player explores a site x then it gains its full reward f(x), but if several players explore it, then neither one receives any reward. Under this policy, it turns out that there exists a unique symmetric Nash Equilibrium strategy, which is, in fact, evolutionary stable. Moreover, this strategy yields the best possible coverage among all symmetric strategies. Viewing the coverage measure as the social welfare, this policy thus enjoys a (Symmetric) Price of Anarchy of precisely 1, whereas, in fact, any other congestion policy has a price strictly greater than 1.
17:00 - 17:30 - Yoram Moses, Technion [Invited] [slides]
Title: The Interplay Between Knowledge and Action in DA and BDA
Call for presentations
We solicit submissions of extended abstracts describing recent results
relevant to biological distributed computing. We especially welcome extended
abstracts describing new insights and / or case studies regarding the
relationship between distributed computing and biological systems even if
these are not fully formed. Since a major goal of the workshop is to explore
new directions and approaches, we especially encourage the submission of
ongoing work. Selected contributors would be asked to present, discuss and
defend their work at the workshop. Submissions should be in PDF and
include title, author information, and a 4-page extended abstract. Shorter
submissions are also welcome, particularly for poster presentation.
Please use the following EasyChair submission link:
https://easychair.org/conferences/?conf=bda20183
Note: The workshop will not include published proceedings. In particular,
we welcome submissions of extended abstracts describing work that has appeared or is
expected to appear in other venues.
Important Dates:
May 7, 2018 - Extended abstract submission deadline, 23:59 AoE time
May 26, 2018 - Decision notifications
July 23, 2018 - Workshop
Financial support for all presenters
This year, we will provide financial support for all our presenters. Specifically, for each accepted presentation, we will pay for an economy class return flight to London (up to 1,000 EUR) as well as reimburse the workshop registration fee of one author.
More information on applying for financial support will be forthcoming.
Program Committee
Ziv Bar-Joseph - CMU
Anna Dornhaus - University of Arizona
Nancy Lynch - MIT
Melanie Moses - UNM
Merav Parter - MIT
Andrea Richa - ASU
Nir Shavit - MIT
PC Chairs
Yuval Emek - Technion
Amos Korman - CNRS and University of Paris Diderot
Saket Navlakha - Salk Institute
Organizing Committee
Amos Korman (Chair) - CNRS and University of Paris Diderot
Yuval Emek - Technion
Saket Navlakha - Salk Institute
Sponsors
This workshop is partially funded by the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation program (grant agreement No 648032).
