Awake Complexity of Distributed Minimum Spanning Tree

The 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 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. Lower Bounds.We show a lower bound of Ω(logn) (where n is the number of nodes in the network) on the awake complexity for computing an MST that holds even for randomized algorithms.To better understand the relationship between the awake complexity and the round complexity (which counts both awake and sleeping rounds), we also prove a trade-off lower bound of Ω~(n) (throughout, the O~ notation hides a polylogn factor and Ω~ hides a 1/(polylogn) 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 Ω~(n) to Ω~(n).Awake-Optimal Algorithms.We present a distributed randomized algorithm to find an MST that achieves the optimal awake complexity of O(logn) (with high probability). Its round complexity is O(nlogn). 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.We also show that the O(logn) awake complexity bound can be achieved deterministically as well, by presenting a distributed deterministic algorithm that has O(logn) awake complexity and O(nlog5n) round complexity. We also show how to reduce the round complexity to O(nlognlog∗n) at the expense of a slightly increased awake complexity of O(lognlog∗n).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 polylogn 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 O~(D+2k+n/2k) round complexity and O~(n/2k) awake complexity, where D is the network diameter and integer k is an input parameter to the algorithm. When k∈[max{⌈0.5logn⌉,⌈logD⌉},⌈logn⌉], we can obtain useful trade-offs. Lower Bounds.We show a lower bound of Ω(logn) (where n is the number of nodes in the network) on the awake complexity for computing an MST that holds even for randomized algorithms.To better understand the relationship between the awake complexity and the round complexity (which counts both awake and sleeping rounds), we also prove a trade-off lower bound of Ω~(n) (throughout, the O~ notation hides a polylogn factor and Ω~ hides a 1/(polylogn) 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 Ω~(n) to Ω~(n). We show a lower bound of Ω(logn) (where n is the number of nodes in the network) on the awake complexity for computing an MST that holds even for randomized algorithms. To better understand the relationship between the awake complexity and the round complexity (which counts both awake and sleeping rounds), we also prove a trade-off lower bound of Ω~(n) (throughout, the O~ notation hides a polylogn factor and Ω~ hides a 1/(polylogn) 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 Ω~(n) to Ω~(n). Awake-Optimal Algorithms.We present a distributed randomized algorithm to find an MST that achieves the optimal awake complexity of O(logn) (with high probability). Its round complexity is O(nlogn). 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.We also show that the O(logn) awake complexity bound can be achieved deterministically as well, by presenting a distributed deterministic algorithm that has O(logn) awake complexity and O(nlog5n) round complexity. We also show how to reduce the round complexity to O(nlognlog∗n) at the expense of a slightly increased awake complexity of O(lognlog∗n). We present a distributed randomized algorithm to find an MST that achieves the optimal awake complexity of O(logn) (with high probability). Its round complexity is O(nlogn). 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. We also show that the O(logn) awake complexity bound can be achieved deterministically as well, by presenting a distributed deterministic algorithm that has O(logn) awake complexity and O(nlog5n) round complexity. We also show how to reduce the round complexity to O(nlognlog∗n) at the expense of a slightly increased awake complexity of O(lognlog∗n). 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 polylogn 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 O~(D+2k+n/2k) round complexity and O~(n/2k) awake complexity, where D is the network diameter and integer k is an input parameter to the algorithm. When k∈[max{⌈0.5logn⌉,⌈logD⌉},⌈logn⌉], we can obtain useful trade-offs. 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(logn) rounds which is significantly better than the fundamental lower bound of Ω~(Diameter(G)+n) rounds for MST in the traditional CONGEST model, where nodes can be active for at least so many rounds.