AF: Small: Distributed Algorithms for Dynamic, Noisy Platforms: Wireless Networks, Robot Swarms, and Insect Colonies

Massachusetts Institute Of Technology, Cambridge MA

Investigators

Abstract

Distributed systems are now everywhere, in the form of wired and wireless communication networks, distributed data-management systems, social networks, coordinated robots, and controlled transportation systems; their prevalence and importance will continue to grow. This project is developing theory for distributed systems. Most existing theory for distributed systems has focused on algorithms that achieve high performance on relatively well-behaved computing platforms, such as reliable, static networks or shared-memory multiprocessors. In contrast, this project focuses on theory for very badly behaved platforms such as wireless networks and robot swarms---platforms that exhibit noise and uncertainty and that change unpredictably over time. The project considers how one can design good distributed algorithms for such settings. The approach is inspired by the biological world, in which interacting entities, such as cells or organisms, live in unpredictable environments, and must contend regularly with noise and change. Wireless networks and robot swarms are similar in many ways to social insect colonies (such as ants or bees). In spite of their difficult environments, social insects can solve sophisticated problems, for example, problems of searching, construction, consensus, and task allocation. Understanding how they do this should help computing researchers to design better algorithms for wireless networks and robots. Thus, this project combines its study of algorithms for wireless networks and robot swarms with a theoretical study of insect colony behavior. Specifically, the project seeks new algorithms by which ad hoc wireless networks, robot swarms, and insect colonies can solve fundamental problems of communication, construction, reaching consensus, estimation, data processing, searching, shape formation, task allocation, and more. It also seeks corresponding lower bounds, especially bounds that highlight the costs of accommodating changes and uncertainty. It looks for general insights and principles for distributed computing in dynamic and noisy settings, including metrics for measuring tolerance to noise and change, strategies for designing algorithms, relationships between different models and problems, and results articulating the inherent costs of accommodating change and uncertainty. Algorithms that are studied are mostly probabilistic and synchronous. They tend to be simple, and not to use large local state or elaborate bookkeeping. Ideally, they should be self-stabilizing, that is, able to recover starting from arbitrary configurations. They may make extensive use of estimation of environmental and system properties. The project uses mathematical techniques from distributed computing theory and probability theory. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.