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

点击翻译按钮获取中文摘要

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.