Metraipolis › archive › dc_ca5ed499cd37

Local Distributed Computation under Crash Failures — arXiv:2611.04898

Source: arXiv (en)
Original: https://arxiv.org/abs/2611.04898
License (as archived): CC0-1.0
Archived: 2026-11-04T21:45:44.302Z
SHA-256 of the archived text: e3155d6612ca4232f0eb55b75ea9fe637ad81c390a35757cd4de9b09a15a2243
Stable URL of this page: https://metraipolis.com/documento/dc_ca5ed499cd37

How to cite

Local Distributed Computation under Crash Failures — arXiv:2611.04898 — arXiv (en), https://arxiv.org/abs/2611.04898 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_ca5ed499cd37 (Metraipolis archive dc_ca5ed499cd37, sha256 e3155d6612ca4232f0eb55b75ea9fe637ad81c390a35757cd4de9b09a15a2243)

BibTeX

@misc{dcca5ed499cd37,
  title = {Local Distributed Computation under Crash Failures — arXiv:2611.04898},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.04898},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_ca5ed499cd37; sha256 e3155d6612ca4232f0eb55b75ea9fe637ad81c390a35757cd4de9b09a15a2243},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.04898. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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\geq3$, we construct these views in $O(\min\{n,(\Delta-1)^R,R\Delta f\})$ rounds when a crash bound $f\geq1$ 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\geq3$ 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\geq4\lceil\log_{\Delta-1}f\rceil+4$ and $n\geq\Delta 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 $\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.

Tema degli esploratori: calcolo e infrastrutture (elenco arXiv cs.DC, nuovi lavori del giorno).
Categorie arXiv: Distributed, Parallel, and Cluster Computing (cs.DC) ; Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2611.04898 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-04T21:36:19.390Z dalla pagina https://arxiv.org/list/cs.DC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).