论文标题
一种几乎最佳的最佳异步分布式MST算法
An Almost Singularly Optimal Asynchronous Distributed MST Algorithm
论文作者
论文摘要
一种奇异的（接近）最佳分布式算法是\ emph {Twip {两个}标准（即其时间和消息复杂性）中（接近）最佳的算法。对于\ emph {同步}拥塞网络，这种算法以基本的分布计算问题而闻名，例如领导者选举[Kutten等，JACM 2015]和最小跨越树（MST）构建[Pandurangan等[Pandurangan等人，Stoc，Stoc，Stoc，Stoc 2017，Elkin，Elkin，PODC 2017]。但是，是否可以在一般\ emph {asynchronous}的拥塞网络中获得MST施工问题的单一（接近）最佳结合是开放的。 We present a randomized distributed MST algorithm that, with high probability, computes an MST in \emph{asynchronous} CONGEST networks and takes $\tilde{O}(D^{1+ε} + \sqrt{n})$ time and $\tilde{O}(m)$ messages, where $n$ is the number of nodes, $m$ the边缘数，$ d $是网络的直径，$ε> 0 $是任意的小常数（时间和消息范围都具有很高的概率）。我们的算法是消息最佳的消息（最多可达polygog $（n）$ factor），几乎是最佳时间（除了$ d^ε$ factor除外）。我们的结果回答了在Mashregi和King [Disc 2019]中提出的一个空旷的问题，它给出了具有sublerear时间的第一个已知的异步MST算法（用于所有$ d = o（n^{1-ε}）$），并使用$ \ tilde {o} {o}（o}（m）$消息。使用Mashregi和King [Disc 2019]的结果，这也产生了第一个异步MST算法，该算法在时间和$ KT_1 $ colesest模型中均为sublinear。 我们算法中的一个关键工具是在异步的杂物中构建一棵低直径扎根的树，其具有深度$ \ tilde {o} {o}（d^{1+ε}）$（用于任意的小常数$ punst $ε> 0 $），在$ \ tilde {o} $}（d^o} $} $} $} $} $ {消息。据我们所知，这是第一个在异步环境中几乎最佳的结构。
A singularly (near) optimal distributed algorithm is one that is (near) optimal in \emph{two} criteria, namely, its time and message complexities. For \emph{synchronous} CONGEST networks, such algorithms are known for fundamental distributed computing problems such as leader election [Kutten et al., JACM 2015] and Minimum Spanning Tree (MST) construction [Pandurangan et al., STOC 2017, Elkin, PODC 2017]. However, it is open whether a singularly (near) optimal bound can be obtained for the MST construction problem in general \emph{asynchronous} CONGEST networks. We present a randomized distributed MST algorithm that, with high probability, computes an MST in \emph{asynchronous} CONGEST networks and takes $\tilde{O}(D^{1+ε} + \sqrt{n})$ time and $\tilde{O}(m)$ messages, where $n$ is the number of nodes, $m$ the number of edges, $D$ is the diameter of the network, and $ε>0$ is an arbitrarily small constant (both time and message bounds hold with high probability). Our algorithm is message optimal (up to a polylog$(n)$ factor) and almost time optimal (except for a $D^ε$ factor). Our result answers an open question raised in Mashregi and King [DISC 2019] by giving the first known asynchronous MST algorithm that has sublinear time (for all $D = O(n^{1-ε})$) and uses $\tilde{O}(m)$ messages. Using a result of Mashregi and King [DISC 2019], this also yields the first asynchronous MST algorithm that is sublinear in both time and messages in the $KT_1$ CONGEST model. A key tool in our algorithm is the construction of a low diameter rooted spanning tree in asynchronous CONGEST that has depth $\tilde{O}(D^{1+ε})$ (for an arbitrarily small constant $ε> 0$) in $\tilde{O}(D^{1+ε})$ time and $\tilde{O}(m)$ messages. To the best of our knowledge, this is the first such construction that is almost singularly optimal in the asynchronous setting.
