Sleeping is Efficient: MIS in O(1)-rounds Node-averaged Awake Complexity
Sleeping is Efficient: MIS in O(1)-rounds Node-averaged Awake Complexity
复制标题
睡眠是高效的：O(1) 轮中的 MIS 节点平均清醒复杂度
DOI：
10.1145/3382734.3405718
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Pandurangan, Gopal
中科院分区：
文献类型：
--
作者：
Chatterjee, Soumyottam;Gmyr, Robert;Pandurangan, Gopal
最大独立集问题是分布式计算的基本问题之一。分布式MIS的轮（时间）复杂度传统上集中在所有节点完成的最坏情况下的时间。最著名的（随机）MIS算法在一般图上的最坏情况轮次为O（logn）（其中是节点数）。突破O（logn）的最坏情况界一直是一个长期存在的开放问题，而目前最著名的下界是[EQUATION] round.Motivated的目标，以减少总能源消耗的能量受限的网络，如传感器和ad hoc无线网络，我们采取了另一种方法来测量性能。我们专注于最小化所有节点完成的总时间（或等效的平均时间）。目前还不清楚目前最著名的算法是否产生恒定轮（或eveno（logn））节点平均轮复杂度的MIS在一般的图。我们将传统模型的推广称为睡眠模型，它允许节点在任何一轮进入“睡眠”或“唤醒”状态。虽然唤醒状态对应于传统模型中的默认状态，但在睡眠状态下，节点是“离线”的，即，它不发送或接收消息（并且发送给它的消息也被丢弃），并且不引起任何时间、通信或本地计算成本。因此，在该模型中，仅对节点处于唤醒状态的轮次进行计数，并且除了传统的最坏情况轮次复杂度（即，我们的主要结果是，我们表明，MIS可以解决（预期）O（1）轮下的节点平均唤醒复杂度的措施，在睡眠模型。特别是，我们提出了一个随机分布式算法的MIS，预计O（1）轮节点平均唤醒复杂度，并以很高的概率1有O（logn）轮最坏情况下的唤醒复杂度和O（log3.41n）-舍入最坏情况的复杂度。我们的工作是朝着理解MIS在传统模型和睡眠模型中的节点平均复杂度迈出的一步，以及为能量受限的网络设计能量有效的分布式算法。
Maximal Independent Set (MIS) is one of the fundamental problems in distributed computing. The round (time) complexity of distributed MIS has traditionally focused on theworst-case timefor all nodes to finish. The best-known (randomized) MIS algorithms takeO(logn) worst-case rounds on general graphs (wherenis the number of nodes). Breaking theO(logn) worst-case bound has been a longstanding open problem, while currently the best-known lower bound is [EQUATION] rounds.Motivated by the goal to reducetotalenergy consumption in energy-constrained networks such as sensor and ad hoc wireless networks, we take an alternative approach to measuring performance. We focus on minimizing the total (or equivalently, theaverage)time for all nodes to finish. It is not clear whether the currently best-known algorithms yield constant-round (or eveno(logn)) node-averaged round complexity for MIS in general graphs. We posit thesleeping model, a generalization of the traditional model, that allows nodes to enter either "sleep" or "waking" states at any round. While waking state corresponds to the default state in the traditional model, in sleeping state a node is "offline", i.e., it does not send or receive messages (and messages sent to it are dropped as well) and does not incur any time, communication, or local computation cost. Hence, in this model, only rounds in which a node is awake are counted and we are interested in minimizing the average as well as the worst-case number of rounds a node spends in the awake state, besides the traditional worst-case round complexity (i.e., the rounds for all nodes to finish including both the awake and sleeping rounds).Our main result is that we show thatMIS can be solved in (expected) O(1)rounds under node-averaged awake complexity measurein the sleeping model. In particular, we present a randomized distributed algorithm for MIS that has expectedO(1)-rounds node-averaged awake complexityand, with high probability1hasO(logn)-rounds worst-case awake complexityandO(log3.41n)-rounds worst-case complexity.Our work is a step towards understanding the node-averaged complexity of MIS both in the traditional and sleeping models, as well as designing energy-efficient distributed algorithms for energy-constrained networks.
登录
查看更多内容
并行随机贪婪MIS的严格分析
DOI：
10.1145/3326165
发表时间：
2017
期刊：
ACM Transactions on Algorithms (TALG)
影响因子：
--
作者：
Manuela Fischer;A. Noever
通讯作者：
A. Noever
DOI：
10.1163/_afco_asc_2206
发表时间：
2021-06
期刊：
--
影响因子：
--
作者：
Cambridge University Press
通讯作者：
Cambridge University Press
DOI：
--
发表时间：
2019
期刊：
IEEE Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
Alkida Balliu;S. Brandt;J. Hirvonen;Dennis Olivetti;M. Rabie;J. Suomela
通讯作者：
J. Suomela
最优动态分布式MIS
DOI：
--
发表时间：
2015
期刊：
ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing
影响因子：
--
作者：
K. Censor;Elad Haramaty;Zohar S. Karnin
通讯作者：
Zohar S. Karnin
论普遍领导人选举的复杂性
DOI：
10.1145/2484239.2484274
发表时间：
2013
期刊：
ACM Trans. Program. Lang. Syst.
影响因子：
--
作者：
S. Kutten;Gopal Pandurangan;D. Peleg;Peter Robinson;Amitabh Trehan
通讯作者：
Amitabh Trehan