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

DOI10.1145/3382734.3405718OpenAlexW3046807936MaRDI QIDQ5855212

Gopal Pandurangan, Soumyottam Chatterjee, Robert Gmyr

Publication date: 15 March 2021

Published in: Proceedings of the 39th Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2006.07449

zbMATH Keywords

maximal independent setenergy-efficiencyenergy-efficient algorithmMISawake complexitynode-averaged round complexityresource-efficient algorithmsleeping model

Mathematics Subject Classification ID

Distributed systems (68M14) Distributed algorithms (68W15)

Related Items (9)

Near-Optimal Time–Energy Tradeoffs for Deterministic Leader Election ⋮ Node and edge averaged complexities of local graph problems ⋮ Local problems on grids from the perspective of distributed algorithms, finitary factors, and descriptive combinatorics ⋮ Wake up and join me! An energy-efficient algorithm for maximal matching in radio networks ⋮ The energy complexity of diameter and minimum cut computation in bounded-genus networks ⋮ Energy-efficient distributed algorithms for synchronous networks ⋮ The energy complexity of diameter and minimum cut computation in bounded-genus networks ⋮ Distributed MIS in O(log log n) Awake Complexity ⋮ Distributed MIS with Low Energy and Time Complexities

This page was built for publication: Sleeping is Efficient: MIS in O (1)-rounds Node-averaged Awake Complexity