The Distributed Minimum Spanning Tree Problem
The Distributed Minimum Spanning Tree Problem
复制标题
分布式最小生成树问题
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Michele Scquizzato
中科院分区：
文献类型：
--
作者：
Gopal Pandurangan;Peter Robinson;Michele Scquizzato
本文调查了分布式最小跨越树（MST）问题，这是分布式计算中研究的中央和研究最多的问题之一。在此问题中，我们给出了一个网络，表示为加权图G =（V; e），网络中的节点通过通过G边缘传递的消息传达，其目的是在分布式中构造G的MST g时尚，即每个节点都应识别事件的MST边缘。本文总结了在设计有效的分布式算法并显示分布式MST问题的下限时进行的一长串研究，包括最新的发展，这些发展集中在同时是圆形和消息最佳的算法上。
This article surveys the distributed minimum spanning tree (MST) problem, a central and one of the most studied problems in distributed computing. In this problem, we are given a network, represented as a weighted graph G = (V; E), and the nodes in the network communicate by message passing via the edges of G with the goal of constructing an MST of G in a distributed fashion, i.e., each node should identify the MST edges incident to itself. This article summarizes the long line of research in designing efficient distributed algorithms and showing lower bounds for the distributed MST problem, including the most recent developments which have focused on algorithms that are simultaneously round- and message-optimal.
轮次和消息最优分布式图算法
DOI：
10.1145/3212734.3212737
发表时间：
2018
期刊：
ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing
影响因子：
--
作者：
Haeupler, Bernhard;Hershkowitz, D. Ellis;Wajc, David
通讯作者：
Wajc, David
分布式算法中的时间与消息权衡
DOI：
10.4230/lipics.disc.2018.32
发表时间：
2018
期刊：
32nd International Symposium on Distributed Computing (DISC 2018
影响因子：
--
作者：
Gmyr, Robert;Pandurangan, Gopal
通讯作者：
Pandurangan, Gopal
无需嵌入的低拥塞快捷方式
影响因子：
1.3
作者：
Haeupler, Bernhard;Izumi, Taisuke;Zuzic, Goran
通讯作者：
Zuzic, Goran