Distributed MIS in O(log log n) Awake Complexity

DOI10.1145/3583668.3594574arXiv2204.08359OpenAlexW4380873944MaRDI QIDQ6202235

Fabien Dufoulon, William K. jun. Moses, Gopal Pandurangan

Publication date: 26 March 2024

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

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

zbMATH Keywords

maximal independent setround complexityenergy-efficienttrade-offsawake complexitysleeping model

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Sleeping on the job: energy-efficient and robust broadcast for radio networks
• Distributed algorithms for random graphs
• Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition
• Parallel graph algorithms that are efficients on average
• Making evildoers pay
• MIS on trees
• Local Computation
• The Locality of Distributed Symmetry Breaking
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• Distributed Computing: A Locality-Sensitive Approach
• An Improved Distributed Algorithm for Maximal Independent Set
• Exponential Separations in the Energy Complexity of Leader Election
• Polylogarithmic-time deterministic network decomposition and distributed derandomization
• Efficient algorithms for leader election in radio networks
• The Energy Complexity of Broadcast
• Sleeping is Efficient: MIS in O (1)-rounds Node-averaged Awake Complexity
• The Energy Complexity of BFS in Radio Networks

This page was built for publication: Distributed MIS in O(log log n) Awake Complexity