BSF:2014424:Time-Message Tradeoffs in Distributed Algorithms
BSF:2014424:Time-Message Tradeoffs in Distributed Algorithms
批准号:
1540512
负责人:
Gopal Pandurangan
金额:
$5.0万
依托单位:
依托单位国家:
美国
项目类别:
Standard Grant
财政年份:
2015
资助国家:
美国
项目状态:
已结题
起止时间:
2015-09-01 至 2021-08-31
中文摘要
分布式算法是大规模通信网络的有效操作的基础,例如,分布式最短路径算法用于因特网中的路由选择。分布式算法的两个基本性能度量是运行时间和算法使用的消息数。过去三十年的研究在很大程度上集中在分别优化两种措施中的一种,通常是以另一种为代价。本项目研究如何设计分布式算法,使其同时在这两种措施下工作得很好。这可能会有重大影响,在许多新兴的应用程序,特别是在大规模的分布式通信网络和分布式处理的大规模data.The项目的背景下研究分布式算法的时间-消息权衡各种具体的基本问题,如领导选举,最短路径,最小生成树的建设,和随机游动。这些是分布式计算中的基本原语,在分布式计算中,同时优化时间和消息迄今为止还很难实现。该项目的具体目标是:(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.
期刊论文(2)
专著(0)
科研奖励(0)
会议论文
DOI:
10.4230/lipics.disc.2021.27
发表时间:
2021-08
期刊:
影响因子:
--
作者:
[S. Kutten;W. Moses;Gopal Pandurangan;D. Peleg]
通讯作者:
S. Kutten;W. Moses;Gopal Pandurangan;D. Peleg
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
Collaborative Research: AF: Medium: The Communication Cost of Distributed Computation
-
批准号:2402837
-
项目类别:Continuing Grant
-
资助金额:$33.26万
-
财政年份:2024
-
负责人:Gopal Pandurangan
-
依托单位:
CCF-BSF: AF:Small: Time-Message Tradeoffs in Distributed Algorithms
-
批准号:1717075
-
项目类别:Standard Grant
-
资助金额:$46.26万
-
财政年份:2017
-
负责人:Gopal Pandurangan
-
依托单位:
BIGDATA: Collaborative Research: F: Efficient Distributed Computation of Large-Scale Graph Problems in Epidemiology and Contagion Dynamics
-
批准号:1633720
-
项目类别:Standard Grant
-
资助金额:$54.99万
-
财政年份:2016
-
负责人:Gopal Pandurangan
-
依托单位:
AF: Small: Distributed Algorithmic Foundations of Dynamic Networks
-
批准号:1527867
-
项目类别:Standard Grant
-
资助金额:$40.0万
-
财政年份:2015
-
负责人:Gopal Pandurangan
-
依托单位:
AF:Small:Collaborative Research: Algorithmic Problems in Protein Structure Studies
-
批准号:0915916
-
项目类别:Standard Grant
-
资助金额:$22.5万
-
财政年份:2009
-
负责人:Gopal Pandurangan
-
依托单位:
Efficient Distributed Approximation Algorithms
-
批准号:0830476
-
项目类别:Standard Grant
-
资助金额:$10.0万
-
财政年份:2008
-
负责人:Gopal Pandurangan
-
依托单位: