English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Maximal Independent Set (MIS) is one of the fundamental problems indistributed computing. The round (time) complexity of distributed MIS hastraditionally focused on the \emph{worst-case time} for all nodes to finish.The best-known (randomized) MIS algorithms take $O(\log{n})$ worst-case roundson general graphs (where $n$ is the number of nodes). Motivated by the goal toreduce \emph{total} energy consumption in energy-constrained networks such assensor and ad hoc wireless networks, we take an alternative approach tomeasuring performance. We focus on minimizing the total (or equivalently, the\emph{average}) time for all nodes to finish. It is not clear whether thecurrently 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 allowsnodes to enter either ``sleep'' or ``waking'' states at any round. While wakingstate corresponds to the default state in the traditional model, in sleepingstate a node is ``offline'', i.e., it does not send or receive messages (andmessages sent to it are dropped as well) and does not incur any time,communication, or local computation cost. Hence, in this model, only rounds inwhich a node is awake are counted and we are interested in minimizing theaverage as well as the worst-case number of rounds a node spends in the awakestate.  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 sleepingmodel. In particular, we present a randomized distributed algorithm for MISthat has expected {\em $O(1)$-rounds node-averaged awake complexity} and, withhigh probability has {\em $O(\log{n})$-rounds worst-case awake complexity} and{\em $O(\log^{3.41}n)$-rounds worst-case complexity}.

Sleeping is Efficient: MIS in $O(1)$-rounds Node-averaged Awake Complexity