AF: Small: Super-Fast Distributed Algorithms

分布式算法是一种在多个处理器上同时运行的算法，在这些处理器上允许两两通信。该项目的主要目标是设计“超快”分布式算法，即在分布式设置中以次对数时间运行的算法。在对数时间（甚至多对数时间）内运行的分布式算法传统上被认为是快速的。快速分布式算法的一个著名例子是25年前的最大独立集（MIS）问题的算法，该算法需要对数级的通信轮数。这个项目的主要前提是，对于分布式计算中的各种基本问题，可以设计出超高速的分布式算法。该项目旨在开发实现这一目标的算法技术，并将其应用于经典的分布式计算问题，如MIS、节点着色和许多其他分布式优化问题。随着网络规模的扩大，变得更加动态（例如，点对点和移动网络），并且变得不那么可靠（例如，在无线设置中），对超高速算法的需求越来越大。一个简单的动机是，如果一个算法非常快，它可以简单地重新计算其输出，以响应底层网络中的变化或故障。这里提出的工作将推动分布式算法的发展。有些有待研究的问题是老问题，但最近的研究表明有可能取得进展。另一些则是现有技术似乎不足的新技术。虽然该项目的主要重点是基础研究，但超高速算法在无线、点对点和移动网络中的应用将是自然和预期的结果。

A distributed algorithm is one that runs simultaneously on multiple processors where pairwise communication is allowed.  The main goal of this project is to design "super-fast" distributed algorithms, i.e., algorithms that run in sub-logarithmic time in a distributed setting. Distributed algorithms that run in logarithmic time (or even poly-logarithmic time) have traditionally been considered fast. A well-known example of a fast distributed algorithm is the 25-year old algorithm for the maximal independent set (MIS) problem due to Luby that requires a logarithmic number of communication rounds. The main premise of this project is that for a variety of fundamental problems in distributed computing, it is possible to design super-fast distributed algorithms. The project aims to develop algorithmic techniques towards this goal and to apply them to classic distributed computing problems such as MIS, node coloring, and a host of other distributed optimization problems. As networks increase in size, become more dynamic (e.g., peer-to-peer and mobile networks), and become less reliable (e.g., in wireless settings), there is a greater need for super-fast algorithms. One simple motivation is that if an algorithm is super-fast, it can simply recompute its output in response to a change or a fault in the underlying network. The work proposed here will advance the state of the art in distributed algorithms. Some of the problems to be studied are old ones where recent work suggests the possibility of progress. Others are new ones where existing techniques seem inadequate. While the main focus of this project is basic research, applications of super-fast algorithms in wireless, peer-to-peer, and mobile networks will be natural and expected outcomes.