The distributed minimum spanning tree problem

作     者：Pandurangan, Gopal Robinson, Peter Scquizzato, Michele 

作者机构：Department of Computer Science University of Houston HoustonTX United States Department of Computing and Software McMaster University Hamilton Canada School of Electrical Engineering and Computer Science KTH Royal Institute of Technology Stockholm Sweden 

出 版 物：《Bulletin of the European Association for Theoretical Computer Science》 (Bull. Eur. Assoc. Theor. Comput. Sci.)

年 卷 期：2018年第2018卷第125期

核心收录：

学科分类：08[工学] 0835[工学-软件工程] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Coun-Supported  in part  by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme under grant agreement No 715672 

主　　题：Message passing 

摘      要：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. © 2018, European Association for Theoretical Computer Science. All rights reserved.