BSF:2014424:Time-Message Tradeoffs in Distributed Algorithms

BSF:2014424：分布式算法中的时间消息权衡

• 批准号: 1540512
• 负责人: Gopal Pandurangan
• 金额: $ 5万
• 依托单位: University of Houston
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-09-01 至 2021-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1540512&HistoricalAwards=false
• 关键词: BSF; 2014424; Time; Message; Tradeoffs

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.

分布式算法是大规模通信网络的有效操作，例如，分布式最短路径算法用于路由Internet。分布式算法的两个基本性能度量是该算法使用的运行时间和消息数。在过去的三十年中，研究在很大程度上集中在分别以两种措施中的一项优化，通常以另一个为代价。该项目研究了如何设计分布式算法在两种措施下都可以正常工作的。这可能在许多新兴应用程序中具有重要意义，尤其是在大规模分布式通信网络和大规模数据的分布式处理的背景下。项目研究分布式算法的时间密码折衷，以解决各种特定基本问题，例如领导者选举，最短路径，最小跨越树木的建设以及随机步行。这些是分布式计算中的基本原则，在该计算中，到目前为止，同时优化时间和消息是难以捉摸的。该项目的特定目标是：（1）设计分布式算法，这些算法在给定一个措施的特定值时相对于另一个措施是最佳的； （2）在固定另一个措施时，在一个度量的复杂性上获得下限； （3）获得表征一种措施对另一种措施的依赖性的权衡关系； （4）获得在大规模图上运行的有效分布式算法。这项研究将产生具有可证明性能保证的有效且可扩展的分布式算法。该项目可能会影响实际分布式网络中的算法设计，并通过大规模数据分布式计算。该项目训练学生和博士后研究员解决分布式算法中的研究问题。

项目成果

Fast and Efficient Distributed Computation of Hamiltonian Cycles in Random Graphs

随机图中哈密顿环的快速高效分布式计算

• DOI: 10.1109/icdcs.2018.00079
• 发表时间: 2018
• 期刊: 38th IEEE International Conference on Distributed Computing Systems (ICDCS
• 作者: Chatterjee, Soumyottam;Fathi, Reza;Pandurangan, Gopal;Pham, Nguyen Dinh
• 通讯作者: Pham, Nguyen Dinh

Singularly Near Optimal Leader Election in Asynchronous Networks

• DOI: 10.4230/lipics.disc.2021.27
• 发表时间: 2021-08
• 作者: S. Kutten;W. Moses;Gopal Pandurangan;D. Peleg