Robust Shattering ArgumentsResearch Paper
Many fast randomized distributed algorithms, for the Lovász Local Lemma, maximal independent set, matching and coloring, follow the shattering paradigm (Barenboim, Elkin, Pettie, Schneider, JACM 2016). A randomized pre-shattering phase solves the problem on most of the graph. It leaves a residual set of unresolved nodes, and the analysis has to show that…