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. 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{\varOmega }(\text {Diameter}(G)+\sqrt{n})\) rounds for MST in the traditional CONGEST model, where nodes can be active for at least so many rounds.