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

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