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部分涉及分布式基于图形的网络的分布式算法。 它将从传统的交通拥堵模型开始，该模型严格限制了可以在通信链接上发送的信息量，并将考虑将此模型限制为特殊类别的图形（例如平面图）。 它还将考虑具有有限存储的通讯模型和版本的动态版本。 它将强调通信，计算和建立网络结构的问题。第2部分使用包含通信争夺的物理平台模型来处理更具体的无线网络设置。 这将包括无线电网络模型，其中消息碰撞会导致损失，信噪比和噪声模型，其中消息收据取决于信号传播模式，基于基本通信形式的模型以及支持网络编码的模型。 该项目还将定义网络抽象层，以帮助分解算法设计的任务。 关键问题将是沟通行为的不确定性。第3部分涉及社会昆虫菌落的具体设置（例如蚂蚁或蜜蜂）；为此，参与者将与昆虫生物学家合作。 这些平台极具动态性，并且会受到严重限制存储，精度，计算和通信。殖民地中的昆虫协调以解决殖民地问题，例如获得食物，建立小径，喂养育雏和选择新巢；这些活动可以看作是资源有限的和高度动态的分布式算法。这三个部分之间存在许多联系：在所有三个环境中都出现了类似的问题，并且应该出现类似的随机算法策略。 图形网络的算法可以适应无线网络，也可能有助于解释昆虫菌落的行为。 从图形网络方面，可以更抽象地理解无线网络或昆虫菌落的算法。 转换可能允许算法和下限从一个设置到另一种设置。 引起昆虫菌落的算法想法可能会激发无线网络或图形网络的全新算法样式，从而满足新的灵活性，鲁棒性和适应性特性。 将需要新的指标来捕获这些属性。在整个过程中，项目参与者将寻求跨越这些不同平台的共同定义，结果和一般原则，从而以深刻而笼统的方式解释资源限制和动态性对解决分布式问题的可能性和成本的影响。