4th Workshop on Biological Distributed Algorithms
Monday July 25, 2016 in Chicago, IL USA
We are excited to announce the fourth 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 2016 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 (e.g. learning, decision-making, attention).
Bernard Chazelle (Princeton)
Melanie Moses (UNM)
Konrad Kording (Northwestern)
All attendees must register through the registration website of PODC 2016 at http://www.podc.org/podc2016/registration/. There are several registration packages, so make sure that you choose one that covers (possibly among other activities) the July 25 workshop day. During the registration process, you will be asked to indicate the workshops that you plan to attend. Please make sure to tick the Biological Distributed Algorithms checkbox (you may tick several checkboxes).
Early registration deadline ends June 27th.
08:25 - 08:30 - Organziers: Welcome
08:30 - 09:10 - Melanie Moses, UNM [Invited]
09:10 - 09:35 - Anna Dornhaus and Evan Kelemen [Contributed]
Title: Benefits of individual variation in collective systems: individual efficiency, robustness, flexibility, and cost in social insects
The components of complex systems may vary in quality, robustness, and other traits. Individuals may for example be specialized for performing particular tasks. Employing specialists, however, comes at various costs: one is that these individuals perform badly if allocated to the 'wrong' tasks, which can lead to reduced group-level flexibility. Highly efficient individuals may also be fragile, i.e. not robust to disturbances (such as food shortages in insects), or they may be costly to produce. However, to achieve group-level flexibility, it is not necessary to have all individuals be flexible: only as many as needed to compensate for typical task demand fluctuations need to frequently switch tasks. Similarly, a small proportion of 'robust' workers may be enough to carry the group-level function over periods of disturbance while still achieving high group efficiency at other times. Groups may therefore benefit from not employing all-specialist workers, but instead maintaining a mixture of specialized and flexible, robust and fragile, and/or cheap and expensive workers. We discuss how these traits are associated with body size in the case of bumble bee colonies, and how this enables or limits collective function in different environments.
09:35 - 10:00 - Arjun Chandrasekhar, Deborah Gordon, Saket Navlakha. [Contributed]
Repairing network failures: a distributed algorithm inspired by arboreal turtle ants
Arboreal turtle ants live in the thick forest canopies of western Mexico, where their movements are constrained by a natural graph, formed by overlapping branches, vines, and twigs of trees. Numerous natural environmental perturbations can disconnect foraging trails, which must be repaired without the benefit of centralized control. Despite extensive study in distributed graph search, most algorithms for this problem require greater computational complexity and memory requirements of individual agents than those believed to be possessed by turtle ants. We develop a simple distributed algorithm for repairing network breaks by studying turtle ant behavior in their natural habitat. We validate our algorithm using simulation studies and field experiments.
10:00 - 10:30 - Coffee Break 1
10:30 - 10:55 - Cameron Musco, Hsin-Hao Su and Nancy Lynch. [Contributed]
Ant-Inspired Density Estimation via Random Walks
Many ant species employ distributed population density estimation in applications ranging from quorum sensing [Pra05], to task allocation [Gor99], to appraisal of enemy colony strength [Ada90]. It has been shown that ants estimate density by tracking encounter rates – the higher the population density, the more often the ants bump into each other [Pra05, GPT93]. We study distributed density estimation from a theoretical perspective. We show that a group of anonymous agents randomly walking on a grid are able to estimate their density d to within a multiplicative factor (1 +/- \epsilon) with probability (1 - \delta) in just \tilde O(log(1/\delta) log(1/d\epsilon)/d\epsilon^2) steps by measuring their encounter rates with other agents. Despite dependencies inherent in the fact that nearby agents may collide repeatedly (and, worse, cannot recognize when this happens), this bound nearly matches what is required to estimate d by independently sampling grid locations. From a biological perspective, our work helps shed light on how ants and other social insects can obtain relatively accurate density estimates via encounter rates. From a technical perspective, our analysis requires novel understanding of collision probabilities of multiple random walks using local mixing properties of the underlying graph. Our results extend beyond the grid to more general graphs and we discuss applications to biologically-inspired algorithms for social network size estimation, density estimation by robot swarms, and sensor network sampling.
10:55 - 11:20 - El Mahdi El Mhamdi and Rachid Guerraoui. [Contributed]
Title: When Neurons Fail
Neural networks are considered robust in the sense that the failure of neurons can be compensated by additional learning phases. Nevertheless, in a critical application such as flight control, for which neural networks are now appealing solutions, one cannot afford any additional learning at run-time. In this paper, we view a neural network as a distributed system of which neurons can fail, and we evaluate its robustness in the absence of any (recovery) learning phase. We give, for the first time, tight bounds on the number of neurons that can fail, without harming the result of a computation or making any assumption on the learning algorithm. To determine our bounds, we leverage the very fact that neuronal activation functions are Lipschitzian, in the sense that their growth is controllable. In particular, in the case of multilayer (often called "deep") neural networks, our results provide a guidance on how to distribute synaptic weights over layers to increase robustness, or what waiting rules to set per layer in case of asynchronously firing neurons without losing accuracy at the output level.
11:20 - 12:00 - Konrad Kording, Northwestern [Invited]
Title: What kinds of algorithms would it take for a neuroscientist to understand a microprocessor?
I will discuss our finding that current neuroscience techniques are insufficient to even understand relatively simple systems, like microprocessors and try to sketch approaches one could take to overcome these problems. Many of these approaches boil down to fitting hierarchical, structural generative models to observed data. This is a surprisingly hard problem and even approximate methods will require massive scale computing. Lastly, I will discuss emerging methods that produce huge datasets about brains that could form the basis of structure discovery.
12:00 - 13:00 - Lunch
13:00 - 13:45 - Poster Session
13:45 - 14:10 - Dan Alistarh, James Aspnes, David Eisenstat, Rati Gelashvili and Ron Rivest. [Contributed]
Title: Time-Space Trade-offs in Molecular Computation
There has recently been significant research interest in understanding the computational power of biological systems. Such systems have been studied by several different research communities, using a wide range of mathematical models and tools. Population protocols [AAD+06] are a popular such model, in which randomly-interacting agents with little computational power cooperate to jointly per- form computational tasks. While early work studied the computational power of population protocols, more recently research has focused on the complexity of fundamental tasks in the population model, such as leader election (which requires convergence to a single agent in a special ‘’leader” state), and majority or consensus (in which agents must converge to a decision as to which of two possible initial states had higher initial count). Recent upper and lower bound results point towards an inherent trade-off between the time complexity of these protocols, and the space complexity, i.e. size of the memory available to each agent. In this extended abstract, we describe new results exploring this trade-off. We exhibit a new unified lower bound, which relates the space available per node with the time complexity achievable by a protocol: for instance, our result implies that any protocol solving either leader election or majority for n agents using O(log log n) states must take Ω(n/polylog n) expected time. This is the first result to characterize time complexity for protocols which employ super-constant number of states per node, and proves that fast, poly-logarithmic running times require protocols to have non-trivial complexity in terms of space per node.
14:10 - 14:35 - Lucas Boczkowski, Amos Korman and Emanuele Natale. [Contributed]
Title: Self-Stabilizing Broadcast with O(1)-Bit Messages
In the biological world, broadcast is a common phenomenon in which a piece of information is propagated from one or few individuals across the population. Examples for such a process include: a single ant that has found food and recruit others, few cells that trigger large population responses, a group of fish that reaches consensus around a group of leaders, or a small number of observant individuals that alert their herd. Such information propagation is achieved in what appears to be highly unpredictable, uncoordinated, noisy and limited communication settings. How biological systems manage to operate effectively despite such communication limitations is a fundamental question whose understanding is currently very preliminary. In this study we take a distributed computing perspective to tackle few aspects of the aforementioned general question. We study a simple, abstract broadcast problem in which a source agent wishes to broadcast a single opinion bit over a well mixed population. Our focus is on understanding the difficulties that arise from the inability of individuals to reliably detect when the protocol has actually started and if their current opinion is up-to-date. To capture such situations we consider a self-stabilizing context, in which the system must converge to a correct solution from any initial configuration. We find that efficient broadcast can be performed in a self-stabilizing manner using only 4 bits per interaction. Reducing the message size further remains an open problem. We provide some supporting evidence for the existence of efficient protocols that use a single bit per interaction.
14:35 - 15:00 - Zahra Derakhshandeh, Robert Gmyr, Andrea W. Richa, Christian Scheideler and Thim Strothmann. [Contributed]
Title: Universal Shape Formation for Programmable Matter
We envision programmable matter consisting of systems of computationally limited devices (which we call particles) that are able to self-organize in order to achieve a desired collective goal without the need for central control or external intervention. A central problem for these particle systems is shape formation. In this paper, we present a universal shape formation algorithm which takes an arbitrary seed shape composed of equilateral triangles of unit size and lets the particles build that shape at a scale depending on the number of particles in the system. Our algorithm runs in O(sqrt(n)) asynchronous execution rounds, where n is the number of particles in the system, provided we start from a well-initialized configuration of the particles. This is optimal in a sense that for any shape deviating from the initial configuration, any movement strategy would require Omega(sqrt(n)) rounds in the worst-case (over all asynchronous activations of the particles). Our algorithm relies only on local information (e.g., particles do not have ids, nor do they know n, or have any sort of global coordinate/orientation system), and requires only a constant-size memory per particle.
15:00 - 15:30 - Coffee Break 2
15:30 - 15:55 - Junxing Yang, Radu Grosu, Scott A. Smolka and Ashish Tiwari [Contributed]
V-Formation as Optimal Control
We present a new formulation of the V-formation problem for migrating birds in terms of model predictive control (MPC). In our approach, to drive a collection of N birds towards a desired formation, an optimal velocity adjustment (acceleration) is performed at each time-step on each bird’s current velocity using a model-based prediction window of T time-steps. We present both centralized and distributed versions of this approach. The optimization criteria we consider are based on fitness metrics of candidate accelerations that V-formations are known to exhibit. These include velocity matching, clear view, and upwash benefit. We validate our MPC-based approach by showing that for a significant majority of simulation runs, the flock succeeds in forming the desired formation. Our results help to better understand the emergent behavior of formation flight, and provide a control strategy for flocks of autonomous aerial vehicles.
15:55 - 16:35 - Bernard Chazelle, Princeton [Invited]
How Do We Analyze Network-Based Dynamical Systems?
Living systems are often modeled as dynamical systems that enable
the emergence of collective behavior from the distributed application of local rules.
This approach raises two issues: How realistic are the models? Can their analyses go
beyond numerical simulation? This talk will focus on the second question
and report on our recent efforts to build new analytical tools to study
processes in opinion dynamics, synchronization, swarming, and social learning.
16:35 - 17:00 - Closing remarks and discussion
1. Shlomi Dolev, Sergey Frenkel, Michael Rosenblit, Ram Prasadh Narayanan and Muni Venkateswarlu K. Energy Harvesting in-vivo Nano-Robots in Caterpillar Swarm
2. Julie Miller. Slave-making ants as an alternative model of collective decision-making
3. Xiaohui Guo, Michael R. Lin, Kang Yun and Jennifer Fewell. Environmental and spatial heterogeneity’s effects on information flow in ant colonies: An agent-based model study
4. Yipei Guo, Mikhail Tikhonov and Michael Brenner. Natural local growth rules can lead to metabolically efficient colony structure
5. Clarissa Bruno Tuxen, Sergio Gramacho and Avani Wildani. Socially Driven Computer Networks
6. Daniel Charbonneau and Anna Dornhaus. Who needs 'lazy' ants? How inactive workers can increase colony flexibility and robustness
7. Vivek Mishra and Dr Fumin Zhang. A Bio-inspired Souce Seeking Algorithm using Stochastic Optimization Technique
8. Xiaohui Guo, Jennifer Fewell and Kang Yun. Does individual variation matter in spreading alarm signal on social network of seed harvester ants’ colonies (Pogonomyrmex californicus)?
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. By default, the
submissions will be evaluated for either oral or poster presentation,
though authors may indicate in their submission if it should be only
considered for one of the presentation types. 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:
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: [UPDATED ON APRIL 20th TO EXTEND DEADLINE TO April 30th]
April 30, 2016 - Extended abstract submission deadline, 23:59 Honolulu time
May 25, 2016 - Decision notifications
June 15, 2016 - Deadline for registration and financial support requests
July 25, 2016 - Workshop
Program / Organizing committee
Ziv Bar-Joseph - CMU
Anna Dornhaus - University of Arizona
Yuval Emek - Technion (Co-chair)
Amos Korman - CNRS and University of Paris Diderot
Nancy Lynch - MIT
Saket Navlakha - Salk Institute (Co-chair)
We will have several NSF-sponsored travel fellowships for students and post-docs available. Applications will be handled after the decision notification (May 25th).