AF: Small: Super-Fast Distributed Algorithms

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

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.