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

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

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.