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{\Omega}(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.
翻译:我们研究分布最小的横贯树( MST) 问题, 这是分布式计算中的根本问题。 众所周知, 分布式的 MST 可以在标准 CONEST 模型( 美元是网络大小, 美元是网络直径) 中以美元解决 。 这基本上是最佳的圆形复杂度( 最高为对数因素 ) 。 然而, 在资源限制的网络中, 如临时的无线和传感器网络, 节点花费如此多的时间可以导致大量消耗能源等资源。 以上考虑的激励下, 我们研究在 标准 CONEST 模型( 美元是网络大小, $DODC 2020 ) 中为 MST 的分布式算法。 在睡眠模型中, 节点可以在任何回合中以两种模式之一( emph) 进行交易( 最接近的平淡化 ), 或 memphex 匹配 } (与传统模型一样, 我们总是清醒。