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

We study the distributed minimum spanning tree (MST) problem, a fundamentalproblem in distributed computing. It is well-known that distributed MST can besolved 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 isessentially the best possible round complexity (up to logarithmic factors).However, in resource-constrained networks such as ad hoc wireless and sensornetworks, nodes spending so much time can lead to significant spending ofresources such as energy.  Motivated by the above consideration, we study distributed algorithms for MSTunder the \emph{sleeping model} [Chatterjee et al., PODC 2020], a model fordesign and analysis of resource-efficient distributed algorithms. In thesleeping model, a node can be in one of two modes in any round --\emph{sleeping} or \emph{awake} (unlike the traditional model where nodes arealways 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 theawake 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 havean \emph{optimal} awake complexity of $O(\log n)$ time with a matching lowerbound. We also show that our randomized awake-optimal algorithm has essentiallythe best possible round complexity by presenting a lower bound of$\tilde{\Omega}(n)$ on the product of the awake and round complexity of anydistributed algorithm (including randomized) that outputs an MST. To complementour trade-off lower bound, we present a parameterized family of distributedalgorithms that gives an essentially optimal trade-off between the awakecomplexity and the round complexity.

Awake Complexity of Distributed Minimum Spanning Tree