No Truly Sublogarithmic-Round Algorithm for Distributed MIS in the LOCAL Model

Seri Khoury, Aaron Schild

We prove that $o(\frac{\log n}{\log \log n})$-round randomized LOCAL algorithms find a maximal independent set (MIS) with subconstant probability on some input. This shows that the…