Nancy Lynch’s research group has been studying biological distributed algorithms for around six years, mainly algorithms for social insect colonies (for problems like searching, task allocation, house-hunting and density estimation) and algorithms for brain networks (for problems like winner-take-all, neural coding, counting and learning of structured concepts).
Robust Ant Colony Algorithms: Density Estimation and House-Hunting
Presented by Nancy Lynch, MIT
Wednesday, October 30, 2019
1:30–3:30 p.m.
Brickyard (BYENG) 209, Tempe campus [map]
Abstract
These algorithms have many interesting characteristics: they tend to be simple to describe, but hard to analyze. They are typically probabilistic, and solve problems only approximately. They are flexible (work in different environments), robust (to failures) and adaptive (to changes during operation). These are interesting features not just for biological distributed algorithms but also for engineered distributed algorithms. We are studying these algorithms for two reasons: in order to understand the behavior of biological systems, and in order to extract ideas from biological systems that may help in designing and analyzing algorithms for wireless networks and other engineered systems.
Another issue we are interested in is the composition of algorithms. We would like to understand how one can combine (probabilistic, approximate) biological distributed algorithms for simple problems to obtain algorithms for more complex problems. This talk will focus on a particular example: an ant colony density estimation algorithm recently developed by (Lynch, Musso and Su), and an ant colony house-hunting algorithm from Mira Radeva’s thesis. I will describe these algorithms and their guarantees separately, and then show how they can be combined. This suggests many new directions for further research. Joint work with Cameron Musco, Mira Radeva and Hsin-Hao Su.
About the speaker
Nancy Lynch is the NEC Professor of Software Science and Engineering in MIT’s EECS department, and until recently, an associate department head. She heads the Theory of Distributed Systems research group in the MIT Computer Science and Artificial Intelligence Laboratory. She received her doctoral degree from MIT and her bachelor’s from Brooklyn College, both in mathematics. Lynch has (c0-)written many research articles about distributed algorithms and impossibility results, and about impossibility result for reaching consensus in asynchronous distributed systems in the presence of failures, with Fischer and Paterson, followed by results with Dwork and Stockmeyer on algorithms for reaching consensus under restricted failure assumptions. Other contributions include the I/O automata textbook Distributed Algorithms and co-author of The Theory of Timed I/O Automata and Atomic Transactions.
She is an ACM Fellow, a member of both National Academies (Engineering and Sciences), and a Fellow of the American Academy of Arts and Sciences. She has been awarded the Dijkstra Price (twice), the van Wijngaarden prize, the Knuth prize, the Piore award, the Athena Lecturer award and an IEEE Technical Achievement award for distributed computing. She has supervised approximately 100 doctoral students, master’s students and postdocs. Lynch is interested in all aspects of distributed computing theory, including modeling, algorithm design, analysis, lower bounds and applications. Currently, she is especially interested in algorithms for “difficult” platforms, which are subject to noise, failures and changes. Recently her work has focused on wireless network algorithms and biological distributed algorithms (insect colonies and brains).
