论文标题
分布式最小生成树的清醒复杂性
Awake Complexity of Distributed Minimum Spanning Tree
论文作者
论文摘要
我们研究分布式最小跨树（MST）问题，这是分布式计算中的基本问题。众所周知，分布式MST可以以$ \ tilde {o}（d+\ sqrt {n}）$ rounds（$ \ tilde {o}（d+\ sqrt {n}）$ roughs（其中$ n $是网络尺寸，$ d $是网络直径），这实质上是最佳的圆形复杂性（to to to logarithmic confactimic confactions）。但是，在资源受限的网络（例如临时无线和传感器网络）中，节点花费大量时间会导致能源等资源的大量支出。 在上述考虑因素上，我们研究了MST的分布式算法，在\ emph {睡眠模型} [Chatterjee等，PODC 2020]下，这是一种用于资源评估效率分布式算法的设计和分析的模型。在睡眠模型中，节点可以在任何回合中以两种模式之一 - \ emph {sheaph}或\ emph {awake}（与传统模型不同，该节点始终始终唤醒）。仅计数节点为\ emph {awake}的回合，而\ emph {sheaph}的圆圈被忽略。一个节点仅在清醒的回合中花费资源，因此，主要目标是最大程度地减少分布式算法的\ emph {醒目的复杂性}，这是最差的回合，任何节点都是清醒的。 我们提出确定性和随机分布式的MST算法，该算法具有\ emph {optimal}的$ o（\ log n）$时间，并具有匹配的下限。我们还表明，我们的随机清醒算法从本质上具有最佳的圆形复杂性，通过在任何分布式算法（包括随机）的醒目和圆形复杂性上呈现$ \tildeΩ（n）$的下限，以输出MST。为了补充我们的权衡下限，我们提出了一个参数化的分布式算法家族，从而在清醒的复杂性和圆形复杂性之间提供了基本最佳的权衡。
We study the distributed minimum spanning tree (MST) problem, a fundamental problem in distributed computing. It is well-known that distributed MST can be solved in $\tilde{O}(D+\sqrt{n})$ rounds in the standard CONGEST model (where $n$ is the network size and $D$ is the network diameter) and this is essentially the best possible round complexity (up to logarithmic factors). However, in resource-constrained networks such as ad hoc wireless and sensor networks, nodes spending so much time can lead to significant spending of resources such as energy. Motivated by the above consideration, we study distributed algorithms for MST under the \emph{sleeping model} [Chatterjee et al., PODC 2020], a model for design and analysis of resource-efficient distributed algorithms. In the sleeping model, a node can be in one of two modes in any round -- \emph{sleeping} or \emph{awake} (unlike the traditional model where nodes are always awake). Only the rounds in which a node is \emph{awake} are counted, while \emph{sleeping} rounds are ignored. A node spends resources only in the awake rounds and hence the main goal is to minimize the \emph{awake complexity} of a distributed algorithm, the worst-case number of rounds any node is awake. We present deterministic and randomized distributed MST algorithms that have an \emph{optimal} awake complexity of $O(\log n)$ time with a matching lower bound. We also show that our randomized awake-optimal algorithm has essentially the best possible round complexity by presenting a lower bound of $\tildeΩ(n)$ on the product of the awake and round complexity of any distributed algorithm (including randomized) that outputs an MST. To complement our trade-off lower bound, we present a parameterized family of distributed algorithms that gives an essentially optimal trade-off between the awake complexity and the round complexity.
