Crash-tolerant local algorithms improve network stability under failures

Local Distributed Computation under Crash Failures

Distributed, Parallel, and Cluster ComputingData Structures and Algorithms

Summary

This paper looks at how to make local network computations reliable when some computers crash and stop working fully. The authors introduce a way to build consistent local views around each node that still work correctly even if some neighbors fail. They show how these local views allow existing fault-free algorithms to keep working with little extra delay in many cases. The paper also proves limits on how fast such fault-tolerant computations can be done and gives examples where crashes make tasks much slower.

What this means in practice

  • For network protocol engineers: Design distributed network protocols that maintain correctness despite some node crashes using locally consistent neighborhood views.
  • For distributed system operators: Understand fundamental speed limits of fault-tolerant local computations to better plan recovery strategies for networked systems.

A theory result. No direct application yet.

Authors

Diana Ghinea, Fabian Kuhn, Chen-Da Liu-Zhang, Zahra Parsaeian

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 $Δ\geq3$, we construct these views in $O(\min\{n,(Δ-1)^R,RΔf\})$ rounds when a crash bound $f\geq1$ is globally known; the first two bounds require no knowledge of $f$. For $Δ=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 $Ω(n)$ rounds even for $R=3$ on diameter-two graphs. For each fixed $Δ\geq3$ and sufficiently large $R$, we prove a $(Δ-1)^{R-O(\sqrt R)}$ lower bound even with crashes restricted to round beginnings. We also prove an $Ω(ΔRf)$ lower bound when $R\geq4\lceil\log_{Δ-1}f\rceil+4$ and $n\geqΔRf$. For locally checkable labeling (LCL) problems, we preserve $O(\log^* 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 $Θ(\log n)$ and crash-tolerant complexity $Θ(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.