论文标题
睡眠效率很高：$ O（1）$ - 回合节点平均清醒复杂性
Sleeping is Efficient: MIS in $O(1)$-rounds Node-averaged Awake Complexity
论文作者
论文摘要
最大独立集（MIS）是分布式计算中的基本问题之一。传统上，分布式MIS的圆（时间）复杂性集中在\ emph {糟糕的时间}供所有节点完成。最著名的（随机）MIS算法将$ O（\ log {n}）$糟糕的回合（其中$ n $是节点的数量）。由减少\ emph {total}能源消耗的目标的动机，例如传感器和临时无线网络，我们采用另一种方法来衡量性能。我们专注于最大程度地减少所有节点完成的总（或等效地，等效地，\ emph {平均}）时间。目前尚不清楚当前最著名的算法是否会产生恒定回合（甚至$ o（\ log {n}）$）节点在一般图中的圆形复杂性。我们认为\ emph {睡眠模型}是传统模型的概括，该模型允许节点在任何一轮中输入``睡眠''或``唤醒''状态。虽然清醒状态对应于传统模型中的默认状态，但在睡眠状态下，节点是``离线''，即，它不会发送或接收消息（并且发送给它的消息也已删除），并且不会在任何时间，通信或本地计算成本中产生。因此，在此模型中，只计算出一个节点的回合，我们有兴趣最大程度地减少节点在清醒状态的节点花费的最差的回合。 我们的主要结果是，我们证明{\ em mis可以在（预期的）$ o（1）$ o（1）$（1）$ rounds在节点平均的清醒复杂度度量下}，在睡眠模型中。特别是，我们提出了一种随机分布式算法的MIS，该算法预期{\ em $ o（1）$ - 回合节点 - 散发醒目的复杂性}，并且，高概率具有{\ em $ o（\ log {n}）$（\ log {n}）$ - 圆形 - 圆形 - 圆形case awake awake complectity} and {\ em $ o（\ em $ o（\ em o o（\ em o o（\ em o o（\ em o o（\ em o））复杂性}。
Maximal Independent Set (MIS) is one of the fundamental problems in distributed computing. The round (time) complexity of distributed MIS has traditionally focused on the \emph{worst-case time} for all nodes to finish. The best-known (randomized) MIS algorithms take $O(\log{n})$ worst-case rounds on general graphs (where $n$ is the number of nodes). Motivated by the goal to reduce \emph{total} energy 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, the \emph{average}) time for all nodes to finish. It is not clear whether the currently best-known algorithms yield constant-round (or even $o(\log{n})$) node-averaged round complexity for MIS in general graphs. We posit the \emph{sleeping 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. Our main result is that we show that {\em MIS can be solved in (expected) $O(1)$ rounds under node-averaged awake complexity measure} in the sleeping model. In particular, we present a randomized distributed algorithm for MIS that has expected {\em $O(1)$-rounds node-averaged awake complexity} and, with high probability has {\em $O(\log{n})$-rounds worst-case awake complexity} and {\em $O(\log^{3.41}n)$-rounds worst-case complexity}.
