Speaker: Fabien Dufoulon
Friday, 16 December 2022, 14:00, 1Z77
Abstract:
Maximal Independent Set (MIS) is one of the fundamental and most well-studied problems in distributed graph algorithms. Even after four decades of intensive research, the best-known (randomized) MIS algorithms have O(log n) round complexity on general graphs [Luby, STOC 1986] (where n is the number of nodes), while the best-known lower bound is Ω(√(log(n)/log(log n))) [Kuhn, Moscibroda, and Wattenhofer, JACM 2016]. Breaking past the O(log n) bound or showing stronger lower bounds have been longstanding open problems.
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. An intriguing question is whether one can design a distributed MIS algorithm that is significantly more energy-efficient (having very small awake complexity) compared to existing algorithms.
Our main contribution is to show that MIS can be computed in awake complexity that is exponentially better compared to the best known round complexity of O(log n) and also bypassing its fundamental Ω(√(log(n)/log(log n))) round complexity lower bound (almost) exponentially. Specifically, we show that MIS can be computed by a randomized distributed (Monte Carlo) algorithm in O(log log n) awake complexity with high probability. Since a node spends significant energy only in its awake rounds, our result shows that MIS can be computed in a highly energy-efficient way compared to the existing MIS algorithms.