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.

现实世界的分布式通信网络，如互联网、对等网络、自组织无线和传感器网络以及用于大规模数据处理的数据中心网络，是当今数字社会不可或缺的一部分。分布式/分散式算法是这些网络的有效操作的基础，例如，分布式最短路径算法用于因特网中的路由选择，而分布式图算法用于在社交网络中寻找社区。因此，设计和分析高效的分布式算法是一个重要的研究任务，这将导致更快，更资源有效的性能在现实世界的网络。为了解决更现实的情况下，这个项目的目标是设计分布式算法，同时优化（1）运行时间和（2）消息的数量。这项研究将有助于设计有效的和可扩展的分布式算法与可证明的性能保证。它可以影响对等和ad hoc无线传感器网络中的算法设计，以及大规模数据的分布式处理。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

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.

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

The Complexity of Leader Election: A Chasm at Diameter Two

领导者选举的复杂性：直径二的鸿沟

• DOI: 10.1145/3154273.3154308
• 发表时间: 2018
• 期刊: ICDCN '18 Proceedings of the 19th International Conference on Distributed Computing and Networking
• 作者: Chatterjee, Soumyottam;Pandurangan, Gopal;Robinson, Peter
• 通讯作者: Robinson, Peter