• Calendar

August 23, Tuesday
12:00 – 13:30

A maximal independent set (MIS) on a graph is an inclusion-maximal set of mutually non-adjacent nodes. This basic symmetry breaking structure is vital for many distributed algorithms. There is a simple and elegant randomized algorithm that computes an MIS in O(log n) rounds. However, despite much effort, there has been no improvement in the general case for decades, leaving a large gap to the known lower bound of Omega(sqrt(log n)) rounds. We present a randomized algorithm that achieves a running time of O(sqrt(log n log log n)) on forests. In contrast to previous techniques achieving sublogarithmic running times, our approach does not rely on any bound on the number of independent neighbors (possibly with regard to an orientation of the edges). We therefore hope that it might ultimately contribute to improved algorithms for the general case.