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.