Distributed MIS in O(log log n) Awake Complexity
Distributed Computing · 2026-06 · 39 (2)
DOI: 10.1007/s00446-025-00498-4 ↗Kurz gefasst
Fachartikel in der Zeitschrift Distributed Computing, online erschienen am 19.03.2026. Verfasst von Fabien Dufoulon und 2 weiteren Autor:innen. Die Arbeit nennt 49 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: National Science Foundation, U.S.-Israel Binational Science Foundation.
Abstract (Originalsprache)
Maximal Independent Set (MIS) is one of the fundamental and most well-studied problems in distributed graph algorithms. Even after four decades of intensive research, the best known (randomized) MIS algorithms have $$O(\log {n})$$ round complexity on general graphs [Luby, STOC 1986] (where n is the number of nodes), while the best known lower bound is $$\Omega (\sqrt{\log {n}/\log \log {n}})$$ [Kuhn, Moscibroda, Wattenhofer, JACM 2016]. Breaking past the $$O(\log {n})$$ round complexity upper bound or showing stronger lower bounds have been longstanding open problems. Energy is a premium resource in various settings such as battery-powered wireless networks and sensor networks. The bulk of the energy is used by nodes when they are awake , i.e., when they are sending, receiving, and even just listening for messages. On the other hand, when a node is sleeping , it does not perform any communication and thus spends very little energy. Several recent works have addressed the problem of designing energy-efficient distributed algorithms for various fundamental problems. These algorithms operate by minimizing the number of rounds in which any node is awake , also called the (worst-case) awake complexity . An intriguing open question is whether one can design a distributed MIS algorithm that has significantly smaller awake complexity compared to existing algorithms. In particular, the question of obtaining a distributed MIS algorithm with $$o(\log n)$$ awake complexity was left open in [Chatterjee, Gmyr, Pandurangan, PODC 2020]. Our main contribution is to show that MIS can be computed in awake complexity that is exponentially better compared to the best known round complexity of $$O(\log n)$$ and also bypassing its fundamental $$\Omega (\sqrt{\log {n}/\log \log {n}})$$ round complexity lower bound exponentially. Specifically, we show that MIS can be computed by a randomized distributed (Monte Carlo) algorithm in $$O(\log \log {n} )$$ awake complexity with high probability (i.e., with probability at least $$1 - n^{-1}$$ ). This algorithm has a round complexity of $$O((\log ^7 n) \log \log n)$$ . We also show that we can improve the round complexity at the cost of a slight increase in awake complexity, by presenting a randomized distributed (Monte Carlo) algorithm for MIS that, with high probability, computes an MIS in $$O((\log \log {n})\log ^*n)$$ awake complexity and $$O((\log ^3 n) (\log \log n) \log ^*n)$$ round complexity. Our algorithms work in the $$\mathcal{CONGEST}$$ model where messages of size $$O(\log n)$$ bits can be sent per edge per round.
Förderung
- National Science Foundation
- U.S.-Israel Binational Science Foundation
Zitieren
APA
Dufoulon, F., Moses, W. K., & Pandurangan, G. (2026). Distributed MIS in O(log log n) Awake Complexity. Distributed Computing, 39(2). https://doi.org/10.1007/s00446-025-00498-4
Vancouver
Dufoulon F, Moses WK, Pandurangan G. Distributed MIS in O(log log n) Awake Complexity. Distributed Computing. 2026;39(2). doi:10.1007/s00446-025-00498-4
BibTeX
@article{Dufoulon2026,
author = {Dufoulon, Fabien and Moses, William K. and Pandurangan, Gopal},
title = {Distributed MIS in O(log log n) Awake Complexity},
journal = {Distributed Computing},
year = {2026},
volume = {39},
number = {2},
doi = {10.1007/s00446-025-00498-4}
}
EUVIMED