Local Distributed Computation under Crash Failures

Abstract

We study deterministic algorithms for locally checkable graph problems in the synchronous LOCAL model with crash failures, where a crashing node may send messages to only some neighbors. We introduce consistent neighborhoods: partial radius-$R$ views that agree locally across surviving edges and are complete without crashes. For $R=T+\ell +1$, these views allow local simulation of $T$-round fault-free algorithms that remain correct on subgraphs, satisfying constraints wherever the radius-$\ell$ checking neighborhood contains no crash. On graphs with at most $n$ nodes and maximum degree at most $\Delta \ge 3$, we construct these views in $O(\min \{n,(\Delta -1{)}^R,R\Delta f\})$ rounds when a crash bound $f\ge 1$ is globally known; the first two bounds require no knowledge of $f$. For $\Delta =2$ or girth greater than $2R$, including forests, $O(R)$ rounds suffice. Our upper bounds are essentially tight in suitable parameter regimes. One crash can force $\Omega (n)$ rounds even for $R=3$ on diameter-two graphs. For each fixed $\Delta \ge 3$ and sufficiently large $R$, we prove a $(\Delta -1{)}^{R-O(\sqrt{R})}$ lower bound even with crashes restricted to round beginnings. We also prove an $\Omega (\Delta Rf)$ lower bound when $R\ge 4\lceil {\log }_{\Delta -1}f\rceil +4$ and $n\ge \Delta Rf$. For locally checkable labeling (LCL) problems, we preserve $O({\log }^{\ast }n)$ complexity under any number of crashes whenever this bound holds without faults on all graphs with a fixed degree bound. In contrast, we construct an LCL on graphs of maximum degree at most five with fault-free complexity $\Theta (\log n)$ and crash-tolerant complexity $\Theta (n)$. Finally, any fault-free sinkless-orientation algorithm can be transformed to tolerate any number of crashes with only one additional round, guaranteeing correctness even at surviving nodes adjacent to crashes.

arXiv comment77 pages, 9 figures