5th Workshop on Biological Distributed Algorithms

Abstract: What can we learn from a connectome? We constructed a connectome-based simplified model of the first two stages of the fruit fly visual system, the lamina and medulla. The resulting hexagonal lattice convolutional network was trained using backpropagation through time to perform object tracking in natural scene videos. Networks initialized with weights from connectome reconstructions automatically discovered well-known orientation and direction selectivity properties in T4 neurons and their inputs, while networks initialized at random did not. Our work is the first demonstration, that knowledge of the connectome can enable in silico predictions of the functional properties of individual neurons in a circuit, leading to an understanding of circuit function from structure alone.

Abstract: We initiate the study neural networks from the perspective of distributed algorithms. Our ultimate aim is to abstract real neural networks in a way that, while not capturing all interesting features, preserves high-level behavior and allows us to make biologically relevant conclusions.

Towards this goal, we consider the implementation of various algorithmic primitives in a simple yet biologically plausible model of stochastic spiking neural networks. Our model captures the spiking behavior observed in real neural networks along with the widely accepted notion that spike responses and neural computation in general are inherently stochastic.

We first show how this stochastic behavior can be leveraged to solve a basic symmetry-breaking task in which we are given neurons with identical firing rates and want to select a distinguished one. In computational neuroscience, this is known as the winner-take-all (WTA) problem, and it is believed to serve as a basic building block in many tasks, e.g., learning, pattern recognition and clustering. Our main contribution is an explicit construction of an efficient WTA circuit, a proof of correctness and runtime bounds, and a concrete application to the problem of selecting a neuron of maximum firing rate from a group.

We next consider the use of stochastic behavior in a somewhat orthogonal task, developing randomized neural algorithms for similarity testing. We present a neural network which, given two $n$-length patterns of firing neurons, is able to whether the patterns are equal or $\epsilon$-far from being equal. Randomization allows us to solve this task with a very compact network, using just $\tilde O(\sqrt{n}/\epsilon)$ auxiliary neurons. At the heart of our solution is the design of a $t$-round neural random access memory (or neuro-RAM) mechanism that can be implemented with $O(n/t)$ auxiliary neurons. We show that this tradeoff between runtime and network size, which can also be achieved using deterministic threshold gates, is nearly optimal. This demonstrates a neural primitive in which stochastic behavior does not seem to give any computational advantages, contrasting with the key role of randomness in solving the WTA and similarity testing problems.

Abstract: Similarity search, such as identifying similar images in a database or similar documents on the Web, is a fundamental computing problem faced by many large-scale information retrieval systems. We discovered that the fly's olfactory circuit solves this problem using a novel variant of a traditional computer science algorithm (called locality-sensitive hashing). The fly's circuit assigns similar neural activity patterns to similar input stimuli (odors), so that behaviors learned from one odor can be applied when a similar odor is experienced. The fly's algorithm, however, uses three new computational ingredients that depart from traditional approaches. We show that these ingredients can be translated to improve the performance of similarity search compared to traditional algorithms when evaluated on several benchmark datasets. Overall, this perspective helps illuminate the logic supporting an important sensory function (olfaction), and it provides a conceptually new algorithm for solving a fundamental computational problem.

Abstract: In past work, we presented an abstract model for the house-hunting process, in which Temnothorax ant colonies search for, decide on, and move to a new nest site when their current nest becomes unsuitable. We gave an optimal algorithm under our model in terms of runtime -- a colony of $n$ ants can chose between $k < n$ potential nest sites and relocate to the chosen site in $O(\log n)$ rounds of computation, matching an $\Omega(\log n)$ round lower bound.

However, this optimal algorithm is not very `natural'. It requires ants to count the number of other ants in a given nest site exactly, and completely breaks down when population estimates are computed noisily. In light of this, we proposed a more natural algorithm which used the number of ants in a candidate site to obtain a probability of recruiting to this site. Intuitively, this algorithm seems much less sensitive to noisy population estimates.

In this work, we formalize this intuition, showing that our simple house-hunting process is robust to noise. Even when ants can only obtain noisy population measurements, our algorithm allows an $n$ ant colony to decide between $k$ candidate nests in $O(k^3 \log^{1.5} n)$ rounds, nearly matching our lower bound in the natural case that $k << n$.

Our model of noise is very general -- our algorithm works given population estimates that are drawn from any distribution which is bounded in a reasonable range and correct in expectation. We demonstrate, for example, that randomized algorithms for population estimation in ant colonies produce estimates satisfying our requirements, and thus can be used as subroutines in our house-hunting algorithm. We hope that this approach to demonstrating algorithmic robustness using a `probabilistic adversary' which can draw values from any of a broad class of distributions, is useful in studying distributed algorithms in engineered systems operating in noisy or fault prone environments.

Abstract: We study the distributed task allocation problem in multi-agent systems, where each agent selects a task in such a way that, collectively, they achieve a proper global task allocation. In this paper, inspired by ant colonies, we propose several scalable and efficient algorithms to dynamically allocate the agents as the task demands vary. Similar to ants, in our algorithms, each agent obtains sufficient information to make its local decision by gossiping with the other ants. Our algorithms vary in their advantages and disadvantages, with respect to (1) how fast they react to dynamic demands change, (2) how many agents need to switch tasks, (3) whether extra agents are needed, and (4) whether they are resilient to faults.

Abstract: The complexity and size of contemporary defense and commercial systems are reaching boundaries that are difficult to manage. The number of users and connected devices, the amount of data generated and stored, and the size of the geo-spatial region spanned by different system components makes use of standard software development techniques to design and develop solutions for these complex systems a daunting task. Therefore, many applications today, e.g., in cyber security, command and control, and intelligence, surveillance and reconnaissance (ISR), are increasingly using decentralized approaches where a collection of autonomous and relatively simple entities or agents work together to cooperatively solve complex real-world problems. Moreover, some applications such as behavior of entities (e.g., marketing bots, influencing bots, and humans on social media) are inherently decentralized where the collective behavior and outcome completely relies on the interaction of multiple agents with each other and other entities. We will discuss how these applications pose new challenges to the state-of-the-art decentralized and multi-agent systems and how they create new opportunities in biological distributed algorithms.

Abstract: What can be computed by a network of $n$ randomized finite state machines communicating under the \emph{stone age} model [Emek and Wattenhofer 2013] (a generalization of the \emph{beeping} model's communication scheme)? The inherent linear upper bound on the total space of the network implies that its global computational power is not larger than that of a randomized linear space Turing machine, but is this tight? Motivated by applications in biological cellular networks, we answer this question affirmatively for bounded degree networks by introducing a stone age algorithm (operating under the most restrictive form of the model) that given a designated \emph{I/O node}, constructs a \emph{tour} in the network that enables the simulation of the Turing machine's tape. To construct the tour, we first show how to \emph{$2$-hop color} the network concurrently with building a spanning tree with high probability.

Abstract: We envision programmable matter as a system of computationally limited devices (called particles) that are able to self-organize in order to achieve a desired collective goal without the need for central control or external intervention. In this paper, we present an algorithm for the convex hull problem, which, given a particle system P that is connected to a static object O, reconfigures P such that it forms the convex hull of O. Our preliminary analysis indicates that the algorithm runs in O(n+m) asynchronous rounds in the worst case, where n = |P| and m is the area occupied by O. This would be worst-case optimal when n = O(m), since any algorithm solving the problem needs Omega(m) rounds in the worst case to move the first particle from the inner face of the convex hull to the outer face. Our algorithm relies only on local information (e.g., particles do not have unique identifiers, do not know n, and share no common global orientation or coordinate system), and requires only a constant amount of memory per particle.

Abstract: Many programmable matter systems have been developed, including modular and swarm robotics, synthetic biology, DNA tiling, and smart materials, with each tailored toward a specific task or physical setting. In our work on self-organizing particle systems, we abstract away specific settings and instead describe programmable matter as a collection of simple computational elements (particles) with limited memory that each execute fully distributed, local, asynchronous algorithms to solve system-wide problems such as movement, configuration, and coordination. Recent work taking a stochastic approach has yielded surprisingly fruitful results, producing local algorithms that are robust, nearly-oblivious, and truly decentralized. For the compression problem, in which a particle system is tasked with gathering as tightly as possible, we gave a Markov chain based solution that minimizes the overall perimeter of the system via individual particles making decisions based only on information about their local neighborhoods. Variants of this algorithm produced a variety of other useful behaviors, including expansion over as wide an area as possible, coating an arbitrarily shaped surface, and spanning fixed sites. Subsequently we presenting a distributed stochastic algorithm for particle systems forming shortcut bridges, a behavior also observed in army ants, where balancing between two competing global objectives is observed. For all of these problems, tools from Markov chain analysis and distributed algorithms allow us to relate local and globally optimal behavior.

Abstract: We present an adaptable swarm central place foraging algorithm based on Levy-walks (ALSA) and compare it's performance to an ant-inspired algorithm (CPFA) and a distributed spiral search benchmark.

Abstract: “Place” cells are mammalian neurons, commonly found in the hippocampal formation, that have receptive fields associated with particular regions in a given environment. Interestingly, they appear to reflect the animal’s current estimate of its position but are not driven simply from sensory inputs. Through exploration of an environment, we hypothesize that these place cells could be synaptically linked to form a map. Using this network of neurons, we explore the use of spike propagation for path planning on this map and propose a novel time-domain winner-take-all for detecting appropriate movements associated with the shortest path between places. We will also describe a neuromorphic VLSI chip that has been used to simulate portions of this work.