Search papers, labs, and topics across Lattice.
This paper addresses the Minimum Dominating Set (MDS) problem within the sleeping CONGEST model, introducing an $O(\log \Delta)$-approximation algorithm that achieves an awake complexity of $\tilde{O}(\log \Delta)$ while running in $O(\log^2 \Delta)$ rounds. The significance lies in breaking the previously established $\Omega(\log^2 \Delta)$ awake complexity barrier for MDS approximations, thus optimizing resource usage in distributed networks. Furthermore, the authors provide a trade-off approach that allows for further reduction in awake complexity at the cost of approximation quality, enhancing flexibility in algorithm design.
Achieving an $O(\log \Delta)$-approximation for the Minimum Dominating Set with sub-logarithmic awake complexity could revolutionize resource-efficient algorithms in distributed systems.
We study the Minimum Dominating Set (MDS) problem in the sleeping CONGEST model (Chatterjee, Gmyr, and Pandurangan, PODC 2020), a generalization of the standard CONGEST model, in which a node may sleep in some rounds and can only compute, send messages, or receive messages when it is awake. The awake complexity of an algorithm in this model is the worst case number (over all inputs and all nodes) of rounds a node is awake for during the execution of the algorithm. While there are several $O(\log \Delta)$-approximation algorithms (in expectation) for MDS that run in $O(\log^2 \Delta)$ rounds, all of these have $\Omega(\log^2 \Delta)$ awake complexity. Whether this awake complexity can be improved is the question that drives our work. We present the first $O(\log \Delta)$-approximation algorithm for MDS with $o(\log^2 \Delta)$ awake complexity; our algorithm runs in $O(\log^2\Delta)$ rounds with $\tilde{O}(\log\Delta)$ awake complexity. We can reduce the awake complexity further, but at the cost of approximation: we present, for any $1<\alpha\le\Delta$, an algorithm in the sleeping CONGEST model that computes an $O(\alpha\log\Delta)$-approximate dominating set in expectation in $\tilde{O}(\log\Delta\cdot \log_{\alpha} \Delta)$ rounds with $\tilde{O}(\log_{\alpha} \Delta)$ awake complexity. Our results depend on a generalization of the CONGEST model SetCover algorithm of Grunau, Mitrovi'c, Rubinfeld, and Vakilian (SODA 2020) that we develop. This generalization computes an $O(p\cdot q\cdot\log_p\Delta)$-approximate dominating set in $O(\log_p\Delta\cdot\log_q\Delta)$ rounds for parameters $1<p,q\le\Delta$. Our sleeping CONGEST algorithms apply a variety of techniques including sampling-based estimation and scheduling using virtual binary trees to the aforementioned 2-parameter SetCover algorithm.
