Sleeping is Superefficient: MIS in Exponentially Better Awake Complexity
share
Maximal Independent Set (MIS) is one of the central and most well-studied problems in distributed computing. Even after four decades of intensive research, the best-known (randomized) MIS algorithms take O(logn) worst-case rounds on general graphs (where n is the number of nodes), while the best-known lower bound is Ω(√(logn/loglogn)) rounds. Breaking past the O(logn) worst-case bound or showing stronger lower bounds have been longstanding open problems. Our main contribution is that we show that MIS can be computed in (worst-case) awake complexity of O(loglog n) rounds that is (essentially) exponentially better compared to the (traditional) round complexity lower bound of Ω(√(logn/loglogn)). Specifically, we present the following results. (1) We present a randomized distributed (Monte Carlo) algorithm for MIS that with high probability computes an MIS and has O(loglogn)-rounds awake complexity. This algorithm has (traditional) round complexity that is O(poly(n)). Our bounds hold in the CONGEST(O(polylog n)) model where only O(polylog n) (specifically O(log^3 n)) bits are allowed to be sent per edge per round. (2) We also show that we can drastically reduce the round complexity at the cost of a slight increase in awake complexity by presenting a randomized MIS algorithm with O(loglog n log^* n ) awake complexity and O(log^3 n loglog n log^*n) round complexity in the CONGEST(O(polylog n)) model.
READ FULL TEXT