CCF-BSF: AF:Small: Time-Message Tradeoffs in Distributed Algorithms

CCF-BSF：AF：小：分布式算法中的时间消息权衡

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

Real-world distributed communication networks such as the Internet, peer-to-peer networks, ad hoc wireless and sensor networks as well as data center networks used for large-scale data processing are an integral part of today's digital society. Distributed/decentralized algorithms underlie the efficient operation of these networks, e.g., distributed shortest paths algorithms are used for routing in the Internet, and distributed graph algorithms are used for finding communities in social networks. Hence, designing and analyzing efficient distributed algorithms is an important research task which will lead to faster and more resource-efficient performance in real-world networks. To address the more realistic situations, this project will aim to design distributed algorithms which simultaneously optimize the (1) running time and (2) number of messages. This research will help in the design of efficient and scalable distributed algorithms with provable performance guarantees. It can impact algorithm design in peer-to-peer and ad hoc wireless sensor networks, and distributed processing of large-scale data. The PI plans to develop a new course and a textbook on distributed network algorithms that is closely related to the research proposed above. University of Houston is a designated Hispanic serving public Tier 1 research institution and the PI will make efforts to involve minority and underrepresented students in research.Two fundamental performance measures of a distributed algorithm that determine its efficiency 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. However, in many real-world applications, it is important to design distributed algorithms that simultaneously optimize both the measures. This project will investigate how distributed algorithms can be designed that work well under both measures. Furthermore, it will study the precise relationship between the two measures, in particular, how one can trade off one measure with respect to the other measure. This project will study time-message tradeoffs in distributed algorithms for various fundamental problems, including leader election, minimum spanning tree, shortest paths, and random walks. Specific goals of the project are: (1) Given a bound on one measure, design distributed algorithms that are optimal with respect to the other measure; (2) Obtain lower bounds on the complexity of one measure while fixing the other measure; (3) Obtain tradeoff relationships that characterize the dependence of one measure on the other. (4) Obtain efficient distributed algorithms that operate on large-scale graphs.

真实世界分布式通信网络，例如Internet，Peer-Poer网络，临时无线和传感器网络以及用于大型数据处理的数据中心网络，是当今数字社会不可或缺的一部分。分布式/分散的算法是这些网络的有效操作，例如，分布式最短路径算法用于路由Internet，并且分布式图形算法用于在社交网络中查找社区。因此，设计和分析有效的分布式算法是一项重要的研究任务，它将在现实世界网络中提高更快，更高的资源效率性能。为了解决更现实的情况，该项目将旨在设计分布式算法，同时优化（1）运行时间和（2）消息数。这项研究将有助于设计具有可证明性能保证的高效且可扩展的分布式算法。它可以影响点对点和临时无线传感器网络中的算法设计，以及大规模数据的分布处理。 PI计划开发一门新课程和一本有关分布式网络算法的教科书，该课程与上述研究密切相关。休斯顿大学是一家指定的西班牙裔公共层研究机构，PI将努力使少数群体和代表性不足的学生参与研究。两项分布式算法的基本绩效指标确定其效率是运行时间和算法使用的信息数量。在过去的三十年中，研究在很大程度上集中在分别以两种措施中的一项优化，通常以另一个为代价。但是，在许多实际应用中，设计分布式算法同时优化这两种度量非常重要。该项目将调查如何设计分布式算法在这两种措施下都可以正常工作。此外，它将研究这两种措施之间的精确关系，一个人如何相对于另一种措施进行一项措施。该项目将研究各种基本问题的分布式算法中的时期权衡，包括领导者选举，最小跨越树，最短路径和随机步行。该项目的具体目标是：（1）给定一个度量的界限，设计分布式算法，这些算法相对于另一个措施； （2）在固定另一个措施时，在一个度量的复杂性上获得下限； （3）获得表征一项措施对另一种措施的依赖性的权衡关系。 （4）获取在大规模图上运行的有效分布式算法。

项目成果

Brief Announcement: Distributed MST Computation in the Sleeping Model: Awake-Optimal Algorithms and Lower Bounds

简短公告：睡眠模型中的分布式 MST 计算：清醒最优算法和下界

• DOI: 10.1145/3519270.3538459
• 发表时间: 2022
• 期刊: PODC'22: Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing
• 作者: Augustine, John;Moses, William K.;Pandurangan, Gopal
• 通讯作者: Pandurangan, Gopal

Sleeping is Efficient: MIS in O(1)-rounds Node-averaged Awake Complexity

睡眠是高效的：O(1) 轮中的 MIS 节点平均清醒复杂度

• DOI: 10.1145/3382734.3405718
• 发表时间: 2020
• 期刊: PODC '20: Proceedings of the 39th Symposium on Principles of Distributed Computing
• 作者: Chatterjee, Soumyottam;Gmyr, Robert;Pandurangan, Gopal
• 通讯作者: Pandurangan, Gopal

Time-Message Trade-Offs in Distributed Algorithms

分布式算法中的时间与消息权衡

• DOI: 10.4230/lipics.disc.2018.32
• 发表时间: 2018
• 期刊: 32nd International Symposium on Distributed Computing (DISC 2018
• 作者: Gmyr, Robert;Pandurangan, Gopal
• 通讯作者: Pandurangan, Gopal

Symmetry Breaking in the CONGEST Model: Time- and Message-Efficient Algorithms for Ruling Sets

CONGEST 模型中的对称性破缺：规则集的时间和消息高效算法

• 发表时间: 2017
• 作者: Pai, S;Pandurangan, G;Pemmaraju, S.;Riaz, T;Robinson, P.
• 通讯作者: Robinson, P.

Singularly Optimal Randomized Leader Election

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