Sleeping is Efficient: MIS in O (1)-rounds Node-averaged Awake Complexity Article Swipe

PDF

Related Concepts

Upper and lower bounds Binary logarithm Node (physics) Computer science Time complexity Computational complexity theory Set (abstract data type) Log-log plot Combinatorics Mathematics Discrete mathematics Theoretical computer science Algorithm Physics Programming language Quantum mechanics Mathematical analysis

Soumyottam Chatterjee , Robert Gmyr , Gopal Pandurangan ·

YOU? · · 2020 · Open Access · · DOI: https://doi.org/10.1145/3382734.3405718 · OA: W3046807936

Maximal Independent Set (MIS) is one of the fundamental problems in distributed computing. The round (time) complexity of distributed MIS has traditionally focused on the worst-case time for all nodes to finish. The best-known (randomized) MIS algorithms take O(log n) worst-case rounds on general graphs (where n is the number of nodes). Breaking the O(log n) worst-case bound has been a longstanding open problem, while currently the best-known lower bound is [EQUATION] rounds.