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

点击翻译按钮获取中文摘要

Distributed systems are now everywhere, in the form of wired and wireless communication networks, distributed data-management systems,social networks, coordinated robots, and controlled transportationsystems; their prevalence and importance will continue to grow. Thisproject is developing theory for distributed systems. Most existingtheory for distributed systems has focused on algorithms that achieve highperformance on relatively well-behaved computing platforms, such asreliable, static networks or shared-memory multiprocessors. Incontrast, this project focuses on theory for very badly behavedplatforms such as wireless networks and robot swarms---platforms thatexhibit noise and uncertainty and that change unpredictably over time. The project considers how one can design good distributedalgorithms for such settings. The approach is inspired by thebiological world, in which interacting entities, such as cells ororganisms, live in unpredictable environments, and must contendregularly with noise and change. Wireless networks and robot swarmsare similar in many ways to social insect colonies (such as ants orbees). In spite of their difficult environments, social insects cansolve sophisticated problems, for example, problems of searching,construction, consensus, and task allocation. Understanding how theydo this should help computing researchers to design better algorithmsfor wireless networks and robots. Thus, this project combines itsstudy of algorithms for wireless networks and robot swarms with atheoretical study of insect colony behavior.Specifically, the project seeks new algorithms by which ad hocwireless networks, robot swarms, and insect colonies can solvefundamental problems of communication, construction, reachingconsensus, estimation, data processing, searching, shape formation,task allocation, and more. It also seeks corresponding lower bounds,especially bounds that highlight the costs of accommodating changesand uncertainty. It looks for general insights and principles fordistributed computing in dynamic and noisy settings, including metricsfor measuring tolerance to noise and change, strategies for designingalgorithms, relationships between different models and problems, andresults articulating the inherent costs of accommodating change anduncertainty. Algorithms that are studied are mostly probabilistic andsynchronous. They tend to be simple, and not to use large local stateor elaborate bookkeeping. Ideally, they should be self-stabilizing,that is, able to recover starting from arbitrary configurations. Theymay make extensive use of estimation of environmental and systemproperties. The project uses mathematical techniques from distributedcomputing 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.