AF: Small: Super-Fast Distributed Algorithms

分布式算法是在允许成对通信的多个处理器上同时运行的算法。该项目的主要目标是设计“超快”的分布式算法，即在分布式环境下以亚对数时间运行的算法。在对数时间(甚至多对数时间)运行的分布式算法传统上被认为是快速的。快速分布式算法的一个众所周知的例子是已有25年历史的最大独立集(MIS)问题的算法，这是由于Luby需要对数个通信轮次。这个项目的主要前提是，对于分布式计算中的各种基本问题，有可能设计出超快的分布式算法。该项目旨在为这个目标开发算法技术，并将它们应用于经典的分布式计算问题，如管理信息系统、节点着色和许多其他分布式优化问题。随着网络规模的扩大，变得更加动态(例如，对等网络和移动网络)，以及变得不那么可靠(例如，在无线环境中)，对超快算法的需求越来越大。一个简单的动机是，如果一个算法是超快的，它可以简单地重新计算其输出，以响应底层网络中的变化或故障。这里提出的工作将促进分布式算法的技术水平。要研究的一些问题是老问题，最近的工作表明有可能取得进展。另一些则是现有技术似乎不够用的新技术。虽然这个项目的主要重点是基础研究，但超快算法在无线、对等和移动网络中的应用将是自然和预期的结果。

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.