Derivation and Analysis of Distributed Computing Algorithms in Biological Systems
- Author(s): Chandrasekhar, Arjun
- Advisor(s): Navlakha, Saket
- et al.
There are numerous examples of biological systems outperforming human-designed algorithms at engineering tasks. Rather than relying on one central controller, these systems rely on distributed agents following simple local interaction rules that yield complex collective behavior. My research studies these biological systems systems in order to reverse-engineer optimization algorithms, with a focus on designing robust, efficient routing networks.
Repairing broken links is a fundamental problem for human-designed routing networks, as well as trail networks used by ants to travel between nests and food sources. Many ant species have evolved methods to solve the repair problem under more restrictive constraints than those faced by human engineers. Arboreal turtle ants are especially interesting, because their movements are constrained by the branches in the vegetation. I defined a mathematical model for the unique repair problem faced by turtle ants. I demonstrated techniques for using turtle ant behavioral data to derive a distributed repair algorithm and infer critical features of turtle ant behavior. The algorithm is biologically realistic, scalable, and robust to a variety of topologies. I then analyzed data on trail networks formed by turtle ants over several days to conclude that turtle ant trail networks eschew shorter branches in favor of nodes whose physical orientations allow for quicker pheromone reinforcement.
Human-designed routing networks often seek to maximize efficiency while minimizing cost. These objectives often conflict, which necessitates manage trade-offs. Neural arbors face a similar challenge of conducting signals quickly while conserving material. I defined a mathematical framework for the multi-objective optimization problem that neural arbors face. I showed that neural arbors are significantly better at optimizing trade-offs between material cost and signal delay than would be expected by chance. I showed how this framework can be used to predict an arbor's structure based on its function. My work confirms the value of using neural arbors as inspiration for network design algorithms, and identifies promising new avenues for neuroanatomy research.
My research highlights the symbiotic relationships between biology and computer science: collecting and analyzing behavioral data can inform algorithm design, while algorithmic thinking can elucidating novel behavioral patterns.