| Title | : | A Highly Energy-Efficient Distributed MIS Algorithm |
| Speaker | : | Gopal Pandurangan (Professor, University of Houston) |
| Details | : | Tue, 2 Jul, 2024 11:00 AM @ SSB 334 |
| Abstract: | : | Energy is a premium resource in battery-powered wireless and sensor networks, and the bulk of it is used by nodes when they are awake, i.e., when they are sending, receiving, and even just listening for messages. On the other hand, when a node is sleeping, it does not perform any communication and thus spends very little energy. Several recent works have addressed the problem of designing energy-efficient distributed algorithms for various fundamental problems. These algorithms operate by minimizing the number of rounds in which any node is awake, also called the awake complexity. In this talk, we present an energy-efficient distributed algorithm for the fundamental Maximal Independent Set (MIS) problem in distributed networks. We show that MIS can be solved in a small awake complexity, which is significantly better than the traditional round complexity (which counts both sleeping and awake rounds). We will present our main result, which shows that MIS can be computed in O(log log n) awake complexity that is exponentially better compared to the best-known round complexity of O(log n) and also bypassing its fundamental Omega(sqrt{log n/log log n}) round complexity lower bound exponentially. |
