Sleeping is Efficient: MIS in <i>O</i> (1)-rounds Node-averaged Awake Complexity
Soumyottam Chatterjee, Robert Gmyr, Gopal Pandurangan
Abstract
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.
Topics & Concepts
Upper and lower boundsBinary logarithmNode (physics)Computer scienceTime complexityComputational complexity theorySet (abstract data type)Log-log plotCombinatoricsMathematicsDiscrete mathematicsTheoretical computer scienceAlgorithmPhysicsProgramming languageQuantum mechanicsMathematical analysisComplexity and Algorithms in GraphsCryptography and Data SecurityOptimization and Search Problems