在分布式算法的LOCAL模型中，图碎片化是一项核心技术，其分析通常依赖于通过局部性所证明的独立性假设，来界定远离节点的大集合保持未决状态的概率。
然而，我们发现这些假设在超常数轮次的预碎片化程序中失效，因为依赖性会随着时间的推移而累积。这导致文献中几种标准的碎片化论证不完整，包括最大独立集、$(\Delta + 1)$-着色以及分布式Lovász局部引理（LLL）的论证。
我们提供了这些分析的系统修复。我们的主要贡献是对Fischer-Ghaffari LLL算法的纠正碎片化分析。此外，我们开发了捕捉现代算法中常见模式的通用工具，这些工具在不依赖于独立性的情况下，提供了所需的衰减界限。
我们还展示了对常用碎片化引理的明确反例。总体而言，我们为在存在长距离依赖的情况下的碎片化论证建立了一个稳健且可重用的基础。
博主点评： 本文揭示了传统图碎片化论证中的潜在缺陷，并通过系统的修复方法为分布式算法提供了更为坚实的理论基础。研究者们在此基础上可以更有效地设计和分析分布式算法，尤其是在考虑长期依赖的情况下，提升了理论的适用性与准确性。