Brief Announcement: Distributed MST Computation in the Sleeping Model: Awake-Optimal Algorithms and Lower Bounds
Brief Announcement: Distributed MST Computation in the Sleeping Model: Awake-Optimal Algorithms and Lower Bounds
复制标题
简短公告：睡眠模型中的分布式 MST 计算：清醒最优算法和下界
DOI：
10.1145/3519270.3538459
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Pandurangan, Gopal
中科院分区：
文献类型：
--
作者：
Augustine, John;Moses, William K.;Pandurangan, Gopal
本文研究了分布式计算中的一个基本问题--分布式最小生成树问题。众所周知，分布式MST可以在标准CONGEST模型（其中n是网络大小，D是网络直径）中以n（D+ n）轮求解，这基本上是最佳可能轮复杂度（达到对数因子）。然而，在资源受限的网络中，例如无线自组织和传感器网络，节点花费如此多的时间会导致显著的资源消耗，例如能量。出于上述考虑，我们研究了睡眠模型下的MST分布式算法[Chatterjee et al.，PODC 2020]，一个设计和分析资源高效分布式算法的模型。在睡眠模型中，节点可以在任何一轮中处于两种模式之一-睡眠或唤醒（与节点总是唤醒的传统模型不同）。只有节点处于唤醒状态的轮次才会被计数，而休眠轮次则会被忽略。一个节点只在唤醒轮花费资源，因此主要目标是最大限度地减少分布式算法的唤醒复杂度，最坏情况下的轮数任何节点是awake.We提出分布式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 Õ(D+√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 wireless ad hoc 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 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 --- sleeping or awake (unlike the traditional model where nodes are always awake). Only the rounds in which a node is awake are counted, while sleeping rounds are ignored. A node spends resources only in the awake rounds and hence the main goal is to minimize the awake complexity of a distributed algorithm, the worst-case number of rounds any node is awake.We present distributed MST algorithms that have optimal awake complexity with a matching lower bound. We also show that our awake-optimal algorithms have essentially the best possible round complexity by presenting a lower bound on the product of the awake and round complexity of any distributed algorithm (including randomized).
登录
查看更多内容
分布式睡眠模型中的确定性对数完整性
DOI：
--
发表时间：
2021
期刊：
International Symposium on Distributed Computing
影响因子：
--
作者：
Leonid Barenboim;Tzalik Maimon
通讯作者：
Tzalik Maimon
DOI：
--
发表时间：
2018
期刊：
Bull. EATCS
影响因子：
--
作者：
Gopal Pandurangan;Peter Robinson;Michele Scquizzato
通讯作者：
Michele Scquizzato
DOI：
10.1145/3406325.3451081
发表时间：
2021-04
期刊：
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
Bernhard Haeupler;David Wajc;Goran Zuzic
通讯作者：
Bernhard Haeupler;David Wajc;Goran Zuzic
小型 k 支配集的快速分布式构建及应用
DOI：
--
发表时间：
1998
期刊：
J. Algorithms
影响因子：
--
作者：
S. Kutten;D. Peleg
通讯作者：
D. Peleg
论普遍领导人选举的复杂性
DOI：
10.1145/2484239.2484274
发表时间：
2013
期刊：
ACM Trans. Program. Lang. Syst.
影响因子：
--
作者：
S. Kutten;Gopal Pandurangan;D. Peleg;Peter Robinson;Amitabh Trehan
通讯作者：
Amitabh Trehan