Distributed MIS with Low Energy and Time Complexities
Mohsen Ghaffari, Julian Portmann · 2023
We present randomized distributed algorithms for the maximal independent set problem (MIS) that, while keeping the time complexity nearly matching the best known, reduce the energy complexity substantially. These algorithms work in the standard CONGEST model of distributed message passing with O(log n) bit messages. The time complexity measures the number of rounds in the algorithm. The energy complexity measures the number of rounds each node is awake; during other rounds, the node sleeps and cannot perform any computation or communications.