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

AF：小型：适用于动态、嘈杂平台的分布式算法：无线网络、机器人群和昆虫群

• 批准号: 2003830
• 负责人: Nancy Lynch
• 金额: $ 34.94万
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2020
• 资助国家: 美国
• 起止时间: 2020-07-01 至 2025-06-30
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2003830&HistoricalAwards=false
• 关键词: AF; Small; Distributed; Algorithms; Dynamic

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.

分布式系统现在无处不在，以有线和无线通信网络、分布式数据管理系统、社交网络、协调机器人和受控运输系统的形式出现;它们的流行程度和重要性将继续增长。 这个项目是发展分布式系统的理论。 大多数分布式系统的现有理论都集中在在相对良好的计算平台上实现高性能的算法上，例如可靠的静态网络或共享内存的多处理器。 相比之下，这个项目的重点是非常糟糕的平台，如无线网络和机器人群的理论-这些平台受到噪音和不确定性的影响，并且随着时间的推移而不可预测地变化。该项目考虑如何为这种设置设计良好的分布式算法。 这种方法受到生物世界的启发，在生物世界中，相互作用的实体，如细胞或有机体，生活在不可预测的环境中，必须定期与噪音和变化作斗争。 无线网络和机器人群在许多方面与社会性昆虫群体（如蚂蚁或蜜蜂）相似。 尽管生活在困难的环境中，社会性昆虫能够解决复杂的问题，例如，搜索、构建、共识和任务分配等问题。 了解它们是如何做到这一点的，应该有助于计算研究人员为无线网络和机器人设计更好的算法。 因此，该项目将无线网络和机器人群算法的研究与昆虫群体行为的理论研究相结合。具体来说，该项目寻求新的算法，通过这些算法，无线网络、机器人群和昆虫群体可以解决通信、构建、达成共识、估计、数据处理、搜索、形状形成、任务分配等基本问题。 它还寻求相应的下限，特别是强调适应变化和不确定性的成本的界限。 它寻找在动态和嘈杂的环境中分布式计算的一般见解和原则，包括测量噪声和变化的容忍度的度量，设计算法的策略，不同模型和问题之间的关系，以及阐明适应变化和不确定性的固有成本的结果。 所研究的算法大多是概率和同步的. 他们往往是简单的，而不是使用大型地方政府或复杂的簿记。 理想情况下，它们应该是自稳定的，即能够从任意配置开始恢复。 它们可以广泛使用环境和系统特性的估计。 该项目使用了分布式计算理论和概率论的数学技术。该奖项反映了NSF的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

Byzantine-Resilient Multi-Agent Optimization

拜占庭弹性多代理优化

• DOI: 10.1109/tac.2020.3008139
• 发表时间: 2021
• 期刊: IEEE transactions on automatic control
• 影响因子: 6.8
• 作者: Vaidya, N.H.

Thalamocortical contribution to flexible learning in neural systems. Network Neuroscience

丘脑皮质对神经系统灵活学习的贡献。

• 发表时间: 2022
• 期刊: Network neuroscience
• 影响因子: 4.7
• 作者: Wang, Mien Brabeeba;Halassa, Michael M.
• 通讯作者: Halassa, Michael M.

SNOW Revisited: Understanding When Ideal READ Transactions Are Possible

重温 SNOW：了解何时可以实现理想的 READ 事务

• 发表时间: 2018
• 期刊: IEEE International Parallel and Distributed Processing Symposium
• 作者: K. Konwar;Wyatt Lloyd;Haonan Lu;N. Lynch
• 通讯作者: N. Lynch

Evidence for thalamic regulation of frontal interactions in human cognitive flexibility

丘脑调节人类认知灵活性额叶相互作用的证据

• 发表时间: 2022
• 期刊: PLOS computational biology
• 影响因子: 4.3
• 作者: Hummos, Ali;Wang, Bin;Drammis, Sabrina;Halassa, Michael M.;Pleger, Burkhard
• 通讯作者: Pleger, Burkhard

The Power of Social Information in Ant-Colony House-Hunting: A Computational Modeling Approach

蚁群找房中社会信息的力量：一种计算建模方法

• 发表时间: 2021
• 期刊: 8th Workshop on Biological Distributed Algorithms (BDA
• 作者: Zhao, J.;Lynch, N.;Pratt, S.C.
• 通讯作者: Pratt, S.C.