Awake Complexity of Distributed Minimum Spanning Tree

Augustine, John; Moses Jr, William K.; Pandurangan, Gopal

Abstract

The \emph{awake complexity} of a distributed algorithm measures the number of rounds in which a node is awake. When a node is not awake, it is {\em sleeping} and does not do any computation or communication and spends very little resources.
Reducing the awake complexity of a distributed algorithm
can be relevant in resource-constrained networks such as sensor networks, where saving energy of nodes is crucial.
Awake complexity of many fundamental problems such as maximal independent set, maximal matching, coloring,
and spanning trees have been studied recently.

In this work, we study the awake complexity of the fundamental distributed minimum spanning tree (MST) problem and present the following results.
\item {\bf Lower Bounds.}
\begin{enumerate}
\item We show a lower bound of $\Omega(\log n)$ (where $n$ is the number of nodes in the network) on the awake complexity
for computing an MST that holds even for randomized algorithms.
\item To better understand the relationship between the awake complexity and the round complexity (which counts
both awake and sleeping rounds),
we also prove a \emph{trade-off} lower bound of
$\tilde{\Omega}(n)$\footnote{Throughout, the $\tilde{O}$
notation hides a $\text{polylog } n$ factor and $\tilde{\Omega}$ hides a $1/(\text{polylog } n)$ factor.}
on the
product of round complexity and awake complexity
for any distributed algorithm (even randomized) that outputs an MST. Our lower bound is shown for graphs having diameter ranging from $\tilde{\Omega}(\sqrt{n})$ to $\tilde{\Omega}(n)$.
\end{enumerate}
\item {\bf Awake-Optimal Algorithms.}
\begin{enumerate} \item We present a distributed randomized algorithm to find an MST that achieves the
optimal awake complexity of $O(\log n)$ (with high probability).
Its round complexity is $O(n \log n)$. We note that by our trade-off lower bound, in general (in terms of $n$), this
is the best round complexity (up to logarithmic factors) for an awake-optimal algorithm.
\item We also show that the $O(\log n)$ awake complexity bound can be achieved deterministically as well, by presenting
a distributed \emph{deterministic} algorithm that has $O(\log n)$ awake complexity and $O(n \log^5 n)$ round complexity. We also show how to reduce the round complexity to $O(n \log n \log^* n)$ at the expense of a slightly increased awake complexity of $O(\log n \log^* n)$.
\end{enumerate}
\item {\bf Trade-Off Algorithms.}
To complement our trade-off lower bound, we present a parameterized family of distributed algorithms
that gives an essentially optimal trade-off (up to $\text{polylog } n$ factors) between the awake complexity and the round complexity. Specifically we
show a family of distributed algorithms that find an MST of the given graph with high probability in $\tilde{O}(D + 2^k + n/2^k)$ round complexity and $\tilde{O}(n/2^k)$ awake complexity, where $D$ is the network diameter and
integer $k$ is an input parameter to the algorithm. When $k \in [\max \lbrace \lceil 0.5\log n \rceil, \lceil \log D \rceil \rbrace, \lceil \log n \rceil]$, we can obtain useful trade-offs.
\end{itemize}

Our work is a step towards understanding resource-efficient distributed algorithms for fundamental global
problems such as MST. It shows that MST can be computed with any node being awake (and hence spending resources) for only $O(\log n)$ rounds which is significantly better than the fundamental lower bound of $\tilde{\Omega}(\text{Diameter}(G)+\sqrt{n})$ rounds for MST in the traditional CONGEST model, where nodes can be active for at least so many rounds.

Citation

Augustine, J., Moses Jr, W. K., & Pandurangan, G. (2024, May). Awake Complexity of Distributed Minimum Spanning Tree. Presented at SIROCCO 2024: 31st International Colloquium On Structural Information and Communication Complexity, Vietri sul Mare, Salerno, Italy

• Presentation Conference Type: Conference Paper (published)
• Conference Name: SIROCCO 2024: 31st International Colloquium On Structural Information and Communication Complexity
• Start Date: May 27, 2024
• End Date: May 29, 2024
• Acceptance Date: Jan 28, 2024
• Deposit Date: Feb 24, 2024
• Print ISSN: 0302-9743
• Series Title: Lecture Notes in Computer Science
• Series ISSN: 0302-9743
• Public URL: https://durham-repository.worktribe.com/output/2276337
• Publisher URL: https://link.springer.com/conference/sirocco
• Related Public URLs: https://arxiv.org/abs/2204.08385