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

Soumyottam Chatterjee, Robert Gmyr, Gopal Pandurangan

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 \emph{wor…