AF: Medium: Distributed Algorithms for Resource-Constrained and Dynamic Settings

AF：中：资源受限和动态设置的分布式算法

• 批准号: 1461559
• 负责人: Nancy Lynch
• 金额: $ 74.14万
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-09-01 至 2020-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1461559&HistoricalAwards=false
• 关键词: AF; Medium; Distributed; Algorithms; Resource

The field of Distributed Computing Theory studies algorithms for well-behaved platforms consisting of powerful agents communicating over powerful networks. These algorithms typically guarantee strong correctness and performance properties. But modern distributed platforms such as wireless networks are less well-behaved: They exhibit unpredictable behavior, including agent failures and mobility, and may have resource limitations, such as bounds on communication, memory, and precision. These complications make it hard to design algorithms that guarantee strong properties. Algorithms may also have new types of requirements: flexibility to run in different situations, robustness to failures, and adaptiveness to change.This project will attempt to understand the fundamental capabilities of such difficult distributed platforms, and to develop algorithms, lower bounds, and general techniques for such settings. It will focus on abstract graph-based networks, wireless networks, and biological insect colonies, while seeking unifying results. The project has the potential to produce a deeper understanding of ideas that underlie important types of distributed systems, to broaden the scope of Distributed Computing Theory, and to provide unification and fundamental principles for three disparate fields. Concretely, the project may enable design of more powerful and robust wireless networks, and contribute new methods for understanding the behavior of some biological systems.The PI has a long track record of mentoring women students and postdocs, some of whom have become leaders of the field. In recruiting new project participants, the PI will make every effort to include women, minorities, and undergraduates. The PI has taught an advanced graduate course on wireless network algorithms several times, and plans to update it based on this project.The project consists of three closely intertwined efforts to understand the fundamental capabilities of resource-constrained, dynamic distributed systems, and to develop algorithms, lower bounds, and general techniques for such systems. Specifically, the participants will focus on graph networks, wireless networks, and insect colonies, while seeking unifying results.Part 1 deals with distributed algorithms for abstract graph-based networks. It will begin with the traditional CONGEST model, which imposes a strict bound on the amount of information that can be sent on communication links, and will consider restrictions of this model to special classes of graphs such as planar graphs. It will also consider dynamic versions of the CONGEST model and versions with limited storage. It will emphasize problems of communication, computation, and building network structures. Part 2 deals with the more concrete setting of wireless networks, using physical platform models that incorporate communication contention. This will include Radio Network models, in which message collisions result in losses, Signal-to-Interference-and-Noise models, in which message receipt depends on signal propagation patterns, models based on rudimentary forms of communication, and models that support network coding. The project will also define network abstraction layers to help decompose the task of algorithm design. A key issue will be uncertainty in communication behavior. Part 3 deals with the concrete setting of social insect colonies (such as ants or bees); for this, the participants will collaborate with insect biologists. These platforms are extremely dynamic, and are subject to severe limitations on storage, precision, computation, and communication. Insects in colonies coordinate to solve colony problems such as obtaining food, establishing trails, feeding brood, and choosing new nests; such activities can be viewed as resource-limited and highly dynamic distributed algorithms. There are many connections among these three parts: Similar problems appear in all three settings, and similar randomized algorithmic strategies should emerge. Algorithms for graph networks may be adapted to wireless networks or may help to explain how insect colonies behave. Algorithms for wireless networks or insect colonies may be understood more abstractly, in terms of graph networks. Transformations may allow algorithms and lower bounds to be ``ported'' from one setting to another. Algorithmic ideas arising for insect colonies may inspire entirely new styles of algorithms for wireless networks or graph networks, satisfying new flexibility, robustness, and adaptiveness properties. New metrics will be needed to capture these properties. Throughout, the project participants will seek common definitions, results, and general principles that span these different kinds of platforms, thus explaining in a deep and general way the impact of resource constraints and dynamicity on the possibility and costs of solving distributed problems.

分布式计算理论领域研究由强大的代理在强大的网络上通信组成的行为良好的平台的算法。 这些算法通常保证强大的正确性和性能属性。 但现代分布式平台（如无线网络）的表现不太好：它们表现出不可预测的行为，包括代理失败和移动性，并且可能具有资源限制，如通信，内存和精度的限制。 这些复杂性使得很难设计出保证强属性的算法。 算法还可能有新类型的要求：在不同情况下运行的灵活性、对故障的鲁棒性以及对变化的适应性。该项目将尝试了解此类困难的分布式平台的基本功能，并开发算法、下限和通用技术用于此类设置。 它将专注于抽象的基于图形的网络，无线网络和生物昆虫群落，同时寻求统一的结果。 该项目有可能产生更深入的理解的想法，分布式系统的重要类型的基础，扩大分布式计算理论的范围，并提供统一和三个不同的领域的基本原则。 具体地说，该项目可能使设计更强大和强大的无线网络，并有助于了解一些生物系统的行为的新方法。PI有指导女学生和博士后的长期记录，其中一些人已经成为该领域的领导者。 在招募新的项目参与者时，PI将尽一切努力包括妇女，少数民族和大学生。 PI教授了一门关于无线网络算法的高级研究生课程，并计划在此项目的基础上对其进行更新。该项目包括三个紧密交织的努力，以了解资源受限的动态分布式系统的基本能力，并为此类系统开发算法，下限和通用技术。 具体来说，与会者将集中在图网络，无线网络和昆虫群落，同时寻求统一的结果。第1部分处理抽象的基于图的网络的分布式算法。 它将开始与传统的CONGEST模型，它强加了一个严格的限制的信息量，可以发送的通信链路，并将考虑这种模式的限制，特殊类别的图形，如平面图。 它还将考虑CONGEST模型的动态版本和具有有限存储的版本。 它将强调通信，计算和构建网络结构的问题。第2部分将使用包含通信争用的物理平台模型来处理更具体的无线网络设置。 这将包括无线电网络模型，其中消息冲突导致丢失，信号干扰和噪声模型，其中消息接收取决于信号传播模式，基于基本通信形式的模型以及支持网络编码的模型。 该项目还将定义网络抽象层，以帮助分解算法设计的任务。 一个关键的问题将是通信行为的不确定性。第3部分涉及社会性昆虫群体（如蚂蚁或蜜蜂）的具体设置;为此，参与者将与昆虫生物学家合作。 这些平台非常动态，并且在存储、精度、计算和通信方面受到严重限制。在殖民地的昆虫协调解决殖民地的问题，如获得食物，建立线索，喂养育雏，并选择新的巢，这些活动可以被视为资源有限的和高度动态的分布式算法。这三个部分之间有许多联系：在所有三个设置中出现了类似的问题，并且应该出现类似的随机算法策略。 图网络的算法可能适用于无线网络，也可能有助于解释昆虫群体的行为。 无线网络或昆虫群落的算法可以更抽象地理解为图网络。 转换可以允许算法和下限从一个设置“移植”到另一个设置。 昆虫群体的数学思想可能会激发无线网络或图形网络的全新风格的算法，满足新的灵活性，鲁棒性和适应性。 将需要新的指标来捕捉这些属性。在整个过程中，项目参与者将寻求跨越这些不同类型平台的共同定义，结果和一般原则，从而以深入和一般的方式解释资源约束和动态性对解决分布式问题的可能性和成本的影响。