BSF:2014424:Time-Message Tradeoffs in Distributed Algorithms

分布式算法是大规模通信网络高效运行的基础，例如，分布式最短路径算法用于互联网中的路由。分布式算法的两个基本性能指标是算法的运行时间和使用的消息数量。过去30年的研究在很大程度上集中在单独优化这两种措施中的一种，通常是以牺牲另一种措施为代价。本项目研究如何将分布式算法设计为同时在这两种标准下良好工作。这在许多新兴应用中可能具有重要意义，特别是在大规模分布式通信网络和大规模数据分布式处理的背景下。该项目研究了分布式算法中各种特定基本问题的时间-消息权衡，如领导者选举、最短路径、最小生成树构造和随机行走。这些是分布式计算中的基本原语，在分布式计算中，同时优化时间和消息到目前为止是难以捉摸的。该项目的具体目标是：(1)设计分布式算法，当给定一个度量的特定值时，相对于另一个度量是最优的；(2)在固定另一个度量的同时，获得一个度量的复杂性的下界；(3)获得表征一个度量对另一个度量的依赖的权衡关系；以及(4)获得在大规模图上运行的高效分布式算法。这项研究将产生高效、可扩展的分布式算法，并提供可证明的性能保证。该项目可能会对现实世界分布式网络中的算法设计和大规模数据的分布式计算产生潜在的影响。该项目培训学生和博士后解决分布式算法中的研究问题。

Distributed algorithms underlie the efficient operation of large-scale communication networks, e.g., distributed shortest paths algorithms are used for routing in the Internet. Two fundamental performance measures of distributed algorithms are the running time and the number of messages used by the algorithm. Research in the last three decades has focused to a large extent on optimizing either one of the two measures separately, typically at the cost of the other. This project investigates how distributed algorithms can be designed to work well under both measures simultaneously. This may have significant implications in many emerging applications, especially in the context of large-scale distributed communication networks and distributed processing of large-scale data.The project studies time-message tradeoffs in distributed algorithms for various specific fundamental problems, such as leader election, shortest paths, minimum spanning tree construction, and random walks. These are fundamental primitives in distributed computing where optimizing both time and messages simultaneously has so far been elusive. Specific goals of the project are to: (1) design distributed algorithms that are optimal with respect to the other measure when given a particular value of one measure; (2) obtain lower bounds on the complexity of one measure while fixing the other measure; (3) obtain tradeoff relationships that characterizes the dependence of one measure on the other; and (4) obtain efficient distributed algorithms that operate on large-scale graphs. This research will yield efficient and scalable distributed algorithms with provable performance guarantees. This project could potentially impact algorithm design in real-world distributed networks and distributed computations over large-scale data. The project trains students and postdoctoral fellows to tackle research problems in distributed algorithms.