AF: Small: Super-Fast Distributed Algorithms

分布式算法是在允许成对通信的多个处理器上同时运行的算法。 该项目的主要目标是设计“超快速”分布式算法，即，在分布式环境中以亚对数时间运行的算法。在对数时间（甚至是多对数时间）内运行的分布式算法传统上被认为是快速的。快速分布式算法的一个众所周知的例子是由吕比提出的最大独立集（MIS）问题的25年算法，该算法需要对数数量的通信回合。该项目的主要前提是，对于分布式计算中的各种基本问题，可以设计超快速的分布式算法。该项目旨在开发算法技术，实现这一目标，并将其应用于经典的分布式计算问题，如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.