Brief Announcement: Distributed MST Computation in the Sleeping Model: Awake-Optimal Algorithms and Lower Bounds
John E. Augustine, William K. Moses, Gopal Pandurangan · 2022
We study the distributed minimum spanning tree (MST) problem, a fundamental problem in distributed computing. It is well-known that distributed MST can be solved in Õ(D+√n) rounds in the standard CONGEST model (where n is the network size and D is the network diameter) and this is essentially the best possible round complexity (up to logarithmic factors). However, in resource-constrained networks such as wireless ad hoc and sensor networks, nodes spending so much time can lead to significant spending of resources such as energy.