2nd Workshop on Biological Distributed Algorithms
October 11-12, 2014 in Austin, Texas USA - in conjunction with DISC 2014
Partially supported by the Division of Computer and Communication Foundations at the
National Science Foundation (NSF)
We are excited to announce the second 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 computational algorithms that can be used to solve basic distributed computing problems.
The first BDA workshop, BDA 2013, was collocated with DISC 2013 (the 27th International Symposium on Distributed Computing) in Jerusalem. BDA 2014 will be collated with DISC 2014 in Austin, Texas. It will take place just before DISC, on Saturday and Sunday, October 11-12, 2014.
BDA 2014 will include talks on distributed algorithms related to a variety of biological systems. However, this time 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).
10:00-10:15 - Organziers: Intro
10:15-10:45 - Anna Dornhaus - University of Arizona
Title: Insect colonies and distributed algorithms; insect colony researcher viewpoint.
10:45-11:30 - Nancy Lynch (MIT) [Slides] and Saket Navlakha (CMU) [Slides]
Title: Distributed algorithms and biological systems
11:30-12:00 - Ofer Feinerman - Weizmann Institute
Title: Queen for a moment: Collective load transport in ants
Abstract: We study collective load retrieval, the process in which a large number of ants cooperate to carry a large food item to the nest, in the species Paratrechina longicornis. We track the ants and the load over distances of about 1000 ant lengths and use image analysis to obtain highly detailed information including load position and orientation, single ant trajectories, pheromonal deposition locations and more. We show that the collective motion is highly cooperative and guided by temporary leaders that are knowledgeable regarding the correct direction home. Cooperativity and susceptibility to leadership are, to some extent, opposing features since the joint force of highly coordinated carriers can be much larger than the forces that can be applied by a single leader. We present a theoretical model that suggests that the ant-load system is poised at a critical point between random and ballistic motions which renders it highly susceptible to a knowledgeable leader.
12:00-12:20 - Contributed Paper: Nancy Lynch, Cameron Musco and Tsvetomira Radeva [Slides]
Title: Studying House-Hunting in the Temnothorax Ant Using Distributed Computing Theory
Abstract: We propose using tools from distributed computing to understand the behavior of the Temnothorax ant colonies when relocating to a new nest. We attempt to model the house-hunting process of the ants and study upper and lower bounds for different algorithmic metrics in this model. Given extensive experimental data about the house-hunting process from the biology community, we can evaluate whether (1) the ants' behavior matches our solutions and/or the optimal solutions, or (2) there are hidden costs and uncertainties that were not addressed by our model and solutions. In either case, we gain understanding in the house-hunting process and hopefully develop mathematically-sound arguments to explain specific aspects of the ant behavior.
12:20-1:30 - Lunch break (lunch served at the meeting, chance to mingle and chat)
1:30-2:00 - Stephen Pratt - Arizona State University [Slides]
Title: Distributed information processing by insect societies
Abstract:
Insect societies are the leading examples of collective cognition by social groups. Much like a single animal, a colony of ants can evaluate its surroundings, process information, and make decisions. Cognition emerges from a network of interacting ants, just as individual cognition emerges from interactions among neurons in the brain. The special appeal of these societies is that their parts—individual insects—are themselves complex cognitive entities, providing a unique opportunity to study the interplay between information processing at these two levels. In this talk I will show how individual behavioral rules and communication networks allow many poorly informed ants to make effective collective decisions. I will further show how colonies amplify the limited cognitive capacity of single ants and how they evade certain irrational consequences of individual choice. Finally, I will consider the limits of collective cognition by exploring when it can improve performance by integrating multiple agents, and when it can instead lead to harmful information cascades.
2:00-2:30 - Radhika Nagpal - Harvard
Title: Cells, Termites, and Robot Collectives
Abstract: Biological systems, from cells to social insects, get tremendous mileage from the cooperation of vast numbers of cheap, unreliable, and limited individuals. What would it take to create our own artificial collectives of the scale and complexity that nature achieves? In this talk, I will discuss recent progress on two such projects - the Termes robots and the Kilobot robot swarm - where we use inspiration from biology to create distributed robot systems that tackle group tasks like collective construction, collective transport, and pattern/shape formation. In each case, we use inspiration from biology to design simple decentralized cooperation, and techniques from computer science to analyze and generalize these algorithms to new tasks.
2:30-3:00 - Amos Korman - CNRS and University of Paris Diderot [Slides]
Title: Confidence sharing: an economic strategy for efficient information flows in animal groups
Abstract: Social animals may share information to obtain a more complete and accurate picture of their surroundings. However, physical constraints on communication limit the flow of information between interacting individuals in a way that can cause an accumulation of errors and deteriorated collective behaviors. Here, we theoretically study a general model of information sharing within animal groups. We take an algorithmic perspective to identify efficient communication schemes that are, nevertheless, economic in terms of communication, memory and individual internal computation. We present a simple algorithm in which each agent compresses all information it has gathered into a single parameter that represents its confidence in its behavior. Confidence is communicated between agents by means of active signaling. We rigorously show that this algorithm competes extremely well with the best possible algorithm that operates without any computational constraints. We also show that this algorithm is minimal, in the sense that further reduction in communication may significantly reduce performances.
Our proofs rely on the Cramer-Rao bound and on our definition of a Fisher Channel Capacity. We use these concepts to quantify information flows within the group and to obtain lower bounds on collective performance. Our results suggest confidence sharing as a central notion in the context of animal communication.
This talk is based on a joint work with Ofer Feinerman and Efrat Greenwald.
3:00-3:30 - Coffee break
3:30-4:00 - Deborah Gordon - Stanford [Talk summary]
Title: The ecology of collective behavior
Abstract: Ant colonies operate without central control, using networks of local interactions to regulate their behavior. Ants are a large and diverse taxon that have evolved in very diverse environments. Examples from ants provide a starting point for examining distributed solutions to environmental problems.I will discuss how environmental constraints, such as the patchiness of resources, the operating costs of maintaining the interaction network that regulates the system’s behavior, and the threat of rupture of the network, all shape the evolution of the algorithms used. Examples are the use of autocatalysis in harvester ants to regulate foraging, analogous to TCP-IP in data networks (“Anternet”), and the regulation of load balancing in the trail circuits of a tropical arboreal species.
4:00-4:30 - Laurent Keller - University of Lausanne
Title: TBA
4:30-6:00 - Poster session
8:00-9:00 - Breakfast (DISC)
9:00-9:30 - Dmitri Chklovskii - HHMI Janelia Farm [Slides]
Title: A neural network for linear subspace tracking
9:30-10:00 - James Marshall - University of Sheffield [Slides]
Title: From house-hunting honeybees to neural models and psychophysics
Abstract: Effective decision-making is crucial for organisms at all levels of biological complexity. I will present a model of collective decision-making based on empirical observations of a novel cross-inhibitory behaviour in house-hunting honeybee swarms. The pattern of interactions observed in collectively-deciding honeybees gives rise to a number of important value-sensitive decision-making characteristics. The model is able to achieve stable deadlock for poor but equal alternatives, but spontaneously choose between good alternatives. This enables sophisticated 'wait and see' decision-making. The model's sensitivity to value is similar to Weber's law of just-noticable-difference from psychology. When differences are large enough to be noticeable, the model exhibits speed-accuracy trade-offs in decision-making similar to classic models from psychology. Given the simplicity of the model, the importance of value-sensitivity, and the similar patterns of interaction seen in other decision-making systems, I will ask whether genetic switches and neural circuits may exist that implement the same basic decision mechanism, and present preliminary data from psychophysical experiments designed to test the behavioural predictions of the model.
10:00-10:20 - Contributed Paper: Yuval Emek, Stephan Holzer and Roger Wattenhofer [Slides]
Title: The Power of a Leader in the Stone Age
Abstract: It is known that in cellular networks modeled by the stone age model of distributed computing [PODC 2013] certain computations are not possible. This includes electing a leader, computing shortest paths and the diameter of a graph [STOC 1980],[ICALP 2014]. However, certain organisms such as the true slime mold Physarum polycephalum seem to be able to compute shortest paths [Nature 2000] and structures close to minimum spanning trees [Science 2010]. When such an organism is modeled using the stone age model, this behavior is only possible when a leader is available. In a first attempt to explain the true slime molds abilities using the stone age model we equip the cellular network with a leader and show that this enables the network to identify cells of maximal distance to each other.
10:30-11:00 - Coffee Break
11:00-11:30 - Ila Fiete - UT Austin
Title: Distributed neural codes for navigation in mammals
11:30-12:00 - Alex Cornejo - Harvard [Slides]
Title: Task allocation in ant colonies
Abstract:
In this paper we propose a mathematical model for studying the phenomenon of division of labor in ant colonies. Inside this model we investigate how simple task allocation mechanisms can be used to achieve an optimal division of labor. We believe the proposed model captures the essential biological features of division of labor in ant colonies and is general enough to study a variety of different task allocation mechanisms. Within this model we propose a distributed randomized algorithm for task allocation that imposes only minimal requirements on the ants; it uses a constant amount of memory and relies solely on a primitive binary feedback function to sense the current labor allocation. We show that with high probability the proposed algorithm converges to a near-optimal division of labor in time which is proportional to the logarithm of the colony size.
12:00-12:20 - Contributed Paper: Shashank Singh, Saket Navlakha and Ziv Bar-Joseph [Slides]
Title: Distributed and computationally efficient belief propagation based on swarms of foraging bacteria
Abstract: We develop a belief propagation model for swarms of bacterial cells using chemotaxis to locate food sources based on two information sources: local food density information for each cell and shared movement and position information from other cells. Compared to prior algorithms for collective navigation, our methods do not assume identifiability of individual agents and minimize both communication and computation, while still being able to handle complicated environments with several other cells and obstacles. The limited computation and communication model we assume makes this method appropriate to problems in which severe constraints exist on these resources. We show empirically that this reduced model can also exhibit superior search performance in certain settings.
12:30-1:30 - Lunch break
1:30-2:00 - Andrea Richa - Arizona State University [Link to project]
Title: Programmable Matter: Models and Problems
Abstract: The term programmable matter refers to matter which has the ability to change its physical properties (shape, density, moduli, conductivity, optical properties, etc.) in a programmable fashion, based upon user input or autonomous sensing. This has many applications like smart materials, autonomous monitoring and repair, and minimal invasive surgery. While programmable matter might have been considered pure science fiction more than two decades ago, in recent years a large amount of research has been conducted in this field. Often programmable matter is envisioned as a very large number of small locally interacting computational particles. The Amoebot model, inspired by the behavior of amoeba, builds upon this vision of programmable matter. The Amoebot model offers a versatile framework to model self-organizing particles and facilitates rigorous algorithmic research in the area of programmable matter. In this talk, we will address several problems of interest under this model, including “smart paint” (coating), shape formation, and bridging problems. In particular, we will present a unified algorithmic framework that allows us to handle several variations of the coating problem.
2:00-2:20 - Contributed Paper: Chris Reid, Hannelore MacDonald, Tanya Latty, Richard Mann and Simon Garnier
Title: Cellular Decision-making: How an Amoeboid Organism Solves the Two-Armed Bandit Problem
Abstract: A fundamental conundrum in decision making is the exploration-exploitation tradeoff; do I exploit well-known but potentially sub-optimal options, or do I risk further exploration for potentially more rewarding ones? The problem faces casino gamblers and foraging organisms alike, but there remains no known generally optimal solution. Several studies in humans and other animals have examined the tradeoff using the 2-Armed Bandit problem, where a player aims to maximize their gain when faced with two slot machines, each with a distinct but unknown reward rate. Studies thus far have only been undertaken in organisms with brains, yet the exploration-exploitation tradeoff also applies to unicellular foragers, which must tackle the problem without the aid of neurons. Also, solutions offered by collective systems have never been investigated. We tested the slime mold Physarum polycephalum, which behaves as a self-organized collective system, with the 2-Armed Bandit problem by assessing the effect of sampling on foraging patch choice in a T-maze. We generate insight into the basic processes of decision making in a unicellular organism, including the use of relative vs absolute reward criteria (in both the frequency of reward, and the combination of frequency and magnitude), and the effect of static vs dynamic exploration environments – factors demonstrated to affect human decision making processes. We then propose several biologically plausible decision criteria the slime mould may be using, and use Bayesian inference to determine which of these models best explains the empirical data. These results can directly inform new models of slime mould decision making and behaviour, improving on the existing, largely biomechanical framework, by incorporating new insight into slime mould ‘psychology’. Our study challenges the common view that neurological hardware is required to solve complex problems, and provides insight into basic processes of decision making, beyond phylogenetic boundaries and orders of biological organization.
2:20-2:40 - Contributed Paper: Yuval Emek, Tobias Langner, David Stolz, Jara Uitto and Roger Wattenhofer [Slides]
Title: Towards More Realistic ANTS
Abstract: In this paper, we summarize our results on a variant of the \emph{Ants Nearby Treasure Search (ANTS)} problem, where $n$ mobile agents, controlled by asynchronous randomized finite automata, search collaboratively for a treasure hidden by an adversary.
We show that despite these restrictions, the treasure can be located in an optimal run-time of $O(D + D^2/n)$. Moreover, we consider slight variations of the above model and showed that the minimum of agents required to solve the ANTS problem depends crucially on the computational capabilities of the agents as well as the timing parameters of the execution environment.
Lastly, we present a protocol for a synchronous environment that allows the agents to locate the treasure in time $O(D + D^2/n + Df)$ when $f$ agents may crash at any time during the execution, while we allow $f$ to be at most a constant fraction of $n$.
3:00-3:30 - Coffee break
3:30-3:50 - Contributed Paper: Yehuda Afek, Roman Kecher and Moshe Sulamy [Slides]
Title: Optimal Phermone Utilization
Abstract: The minimal amount of pheromones necessary and sufficient to deterministically find a treasure (food) by a colony of ants, each modeled by either a Finite State Machine or a Turing Machine, is considered. The k mobile agents (ants), initially located at the origin (nest) of an infinite grid, communicate only through pheromones to perform a collaborative search for an adversarially hidden treasure at an unknown distance D. We begin by proving a tight lower bound of Ω(D) on the number of pheromones required by a FSM to even complete the search, and continue to reduce the lower bound to Ω(k) for the stronger ants modeled as TM. Matching optimal algorithms, in terms of run time as well as pheromone usage, are provided both for synchronous and asynchronous models in each case.
3:50-4:10 - Contributed Paper: Theodore Pavlic and Stephen Pratt [Slides]
Title: Numerical Methods within the Ant Colony: The Illuminating Case of Multi-Objective Macronutrient Regulation in Eusocial Insects
Abstract: Recently, it has been shown that colony-living ants are able to simultaneously regulate the colony-level intake of several macronutrients to set levels. In this extended abstract, we discuss the self organization necessary for this task and draw parallels to parallel and distributed numerical processing in computer science. Moreover, we show how primitive models of social foraging can be enhanced to better understand the mechanisms behind eusocial insect macronutrient regulation. We then show how one such expanded social foraging model is a template for a novel decentralized algorithm for optimization problems with non-separable constraints. Unlike traditional constrained-optimization approaches, this algorithm requires no explicit message passing and instead achieves coordination through physical stigmergy in the environment. Consequently, it is very well suited for physical resource allocation applications, such as intelligent lighting and distributed power generation. Thus, we close with an experimental demonstration of the algorithm on a small-scale intelligent-lighting testbed.
4:10-5:00 - General discussion, continue as needed
6:00-8:00 - DISC reception
Posters
1. Ila Fiete, David Schwab and Ngoc Tran. A binary Hopfield network with $1/\log(n)$ information rate and applications to grid cell decoding.
2. Mahnush Movahedi and Mahdi Zamani. On Optimal Decision-Making in Ant Colonies.
3. James Zou and Anders Johansson. Distributed Slime Mold Solver for Linear Programming Problems.
4. Chris R. Reid, Matthew Lutz, Scott Powell, Iain D. Couzin and Simon Garnier. An ant bridge too far: living architecture and self-organized shortcuts in army ants.
5. Helen Mccreery and Nikolaus Correll. Know when you’re beaten: Efficient cooperative transport requires either a directional bias or that outnumbered individuals give up quickly.
6. Daniel Charbonneau and Anna Dornhaus. When doing nothing is something. How task allocation mechanisms compromise between flexibility, efficiency, and inactive agents.
7. Peter Krafft. Implications of Impossibility Results from Distributed Algorithms for Consensus Strategies in Animal Groups.
Participants
- Yehuda Afek - Tel Aviv University
afek@post.tau.ac.il
- Dmitri Chklovskii - Simons Foundation
mitya@simonsfoundation.org
- Alex Cornejo - Harvard
acornejo@csail.mit.edu
- Zahra Derakhshandeh - Arizona State University
zderakhs@asu.edu
- Anna Dornhaus - University of Arizona
dornhaus@email.arizona.edu
- Yuval Emek - Technionyemek@ie.technion.ac.il
- Ofer Feinerman - Weizmann Institute
ofer.feinerman@weizmann.ac.il
- Ila Fiete - UT Austin
fiete@mail.clm.utexas.edu
- Deborah Gordon - Stanford
dmgordon@stanford.edu
- Stephan Holzer - MIT
stephan.holzer@yahoo.de
- Roman Kecher - Tel-Aviv University
roman.kecher@cs.tau.ac.il
- Laurent Keller - University of Lausanne
Laurent.Keller@unil.ch
- Amos Korman - CNRS and University of Paris Diderot
amos.korman@gmail.com
- Tobias Langner - ETH Zurich
tobias.langner@tik.ee.ethz.ch
- Nancy Lynch - MIT
lynch@csail.mit.edu
- James Marshall - University of Sheffield
james.marshall@sheffield.ac.uk
- Helen McCreery - University of Colorado, Boulder
hmccreery@gmail.com
- Yoram Moses - Technion
moses@ee.technion.ac.il
- Mahnush Movahedi - University of New Mexico
movahedi@cs.unm.edu
- Cameron Musco - MIT
cnmusco@mit.edu
- Radhika Nagpal - Harvard
rad@eecs.harvard.edu
- Saket Navlakha - Carnegie Mellon University
navlakha@cs.cmu.edu
- Theodore P. Pavlic - Arizona State University
tpavlic@asu.edu
- Stephen Pratt - Arizona State University
stephen.pratt@asu.edu
- Mira Radeva - MIT
radeva@csail.mit.edu
- Chris R. Reid - New Jersey Institute of Technology
chrisreidresearch@gmail.com
- Andrea Richa - Arizona State University
Andrea.Richa@asu.edu
- Shashank Singh - Carnegie Mellon University
sss1@andrew.cmu.edu
- Ngoc Tran - University of Texas at Austin
tran.mai.ngoc@gmail.com
- Jara Uitto - ETH Zurich
uitto@tik.ee.ethz.ch
- Mahdi Zamani - University of New Mexico
zamani@cs.unm.edu
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:
http://www.easychair.org/conferences/?conf=bda2014
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:
July 23, 2014 - Extended abstract submission deadline (postponed due to requests of PODC participants)
July 18, 2014 - Extended abstract submission deadline
August 18, 2014 - Decision notifications
September 1, 2014 - Deadline for financial support requests
October 11-12, 2014 - Workshop
Financial support for student/postdoc participants
We will cover the registration fee and up to $500 of travel costs for selected participants at the student/postdoc level. In order to apply for this financial support, send an email to bda14workshop@gmail.com answering the following questions:
- What is your name and affiliation?
- Who is your advisor/host?
- What is your field of research? (A short paragraph would suffice.)
- Where will you be traveling from?
- Did you submit an extended abstract for poster or oral presentation at BDA 2014? What is the submission number?
Deadline for financial support requests: September 1, 2014
Program / Organizing committee
Ziv Bar-Joseph - CMU (co-chair)
Anna Dornhaus - University of Arizona
Yuval Emek - Technion (co-chair)
Amos Korman - CNRS and University of Paris Diderot (co-chair)
Nancy Lynch - MIT
Radhika Nagpal - Harvard
Saket Navlakha - CMU
Nir Shavit - MIT
