Graph shattering is a central technique underlying sublogarithmic-time distributed algorithms in the LOCAL model. Its analysis typically relies on bounding the probability that large sets of distant nodes remain unresolved, often via independence assumptions justified by locality.
However, we show that these assumptions fail for pre-shattering procedures that run for super-constant rounds, where dependencies accumulate over time. As a result, several standard shattering arguments in the literature are incomplete, including those for maximal independent set, $(\Delta + 1)$-coloring, and the distributed Lovász Local Lemma (LLL).
We provide a systematic repair of these analyses. Our main contribution is a corrected shattering analysis of the Fischer--Ghaffari LLL algorithm. Additionally, we develop general tools that capture common patterns in modern algorithms and yield the required decay bounds without relying on independence.
We also present explicit counterexamples to commonly used shattering lemmas. Overall, we establish a robust and reusable foundation for shattering arguments in the presence of long-range dependencies.
Blogger's Review: This paper uncovers potential flaws in traditional graph shattering arguments and provides systematic repair methods that offer a more solid theoretical foundation for distributed algorithms. Researchers can build on this to design and analyze distributed algorithms more effectively, especially in contexts considering long-range dependencies, enhancing the applicability and accuracy of the theory.