Local Distributed Computation under Crash Failures

arXiv:2611.04898v1 [cs.DC] 3 Nov 2026

Local Distributed Computation under Crash Failures Diana Ghinea1

Fabian Kuhn2

diana.ghinea@hslu.ch

kuhn@cs.uni-freiburg.de

Chen-Da Liu-Zhang1

Zahra Parsaeian2

chen-da.liuzhang@hslu.ch zahra.parsaeian@cs.uni-freiburg.de 1 School of Computer Science and Information Technology Lucerne University of Applied Sciences and Arts, Switzerland 2

Department of Computer Science University of Freiburg, Germany

Abstract We study how crash failures affect the round complexity of deterministic algorithms for locally checkable graph problems in the synchronous LOCAL model. A node that crashes during a round may send messages to only some neighbors, leaving surviving nodes with incompatible local views and invalidating the usual local simulation of fault-free algorithms. Our main tool is the consistent neighborhoods problem ΠCN (R): surviving nodes construct partial radius-R views that satisfy local consistency across surviving edges and are complete without crashes. With R = T + ℓ + 1, where T is the fault-free running time and ℓ the checking radius, these views support local simulation of algorithms that remain correct on subgraphs. The outputs satisfy local constraints wherever the checking neighborhood contains no crashed node. On graphs with at most n nodes and maximum degree at most ∆ ≥ 3, we solve ΠCN (R) in O(min{n, (∆ − 1)R , R∆f }) rounds when a crash bound f ≥ 1 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. Conversely, one crash can force Ω(n) rounds even for R = 3 on diameter-two graphs. For each fixed √ ∆ ≥ 3 and sufficiently R−O( R) , even when crashes large R, we prove a worst-case lower bound of (∆ − 1) occur only at the beginning of rounds. We further prove an Ω(∆Rf ) lower bound when R ≥ 4⌈log∆−1 f ⌉ + 4 and n ≥ ∆Rf . Thus all our upper bounds for consistent neighborhoods are essentially tight in suitable parameter regimes. 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 satisfying 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, we transform any fault-free sinkless-orientation algorithm into one tolerating any number of crashes with only one additional round, guaranteeing correctness even at surviving nodes adjacent to crashes.

Contents 1 Introduction 1.1 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Organization of the Paper . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1 2 4 6

2 Technical Overview 2.1 The Consistent Neighborhoods Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 The Consistent Neighborhoods Upper Bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 The Consistent Neighborhoods Lower Bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4 Crash Tolerance for Locally Checkable Labelings . . . . . . . . . . . . . . . . . . . . . . . . . 2.5 Problem-Specific Transformation for Sinkless Orientation . . . . . . . . . . . . . . . . . . . .

6 6 7 9 11 13

3 Preliminaries 13 3.1 Graphs and Related Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.2 Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.3 Initial Knowledge . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 4 The Consistent Neighborhoods Problem 17 4.1 Consistent Neighborhoods without Crashes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 4.2 Local Simulation from Consistent Neighborhoods . . . . . . . . . . . . . . . . . . . . . . . . . 19 4.3 Limits of Local Simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 5 Algorithms for Consistent Neighborhoods 23 5.1 Full-Information Gathering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 5.2 Flooding on Fixed Subgraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 5.3 Consistent Neighborhoods in O(n) Rounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 5.4 Consistent Neighborhoods with Parameter-Dependent Bounds . . . . . . . . . . . . . . . . . . 27 5.5 Consistent Neighborhoods on Graphs of Large Girth . . . . . . . . . . . . . . . . . . . . . . . 31 5.6 Putting It All Together . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 6 Lower Bounds for Consistent Neighborhoods 32 6.1 Common Indistinguishability Framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 6.2 Linear Time with One or Two Crashes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 6.3 An Exponential Lower Bound in the Radius . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 6.4 Dependence on the Crash Bound and Radius . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 6.5 Putting It All Together . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 7 Crash Tolerance for Locally Checkable Labelings 49 7.1 Preserving Log-Star Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 7.2 An LCL with a Linear Crash-Fault Lower Bound . . . . . . . . . . . . . . . . . . . . . . . . . 52 8 Crash-Tolerant Algorithms for Locally Checkable Problems 62 8.1 Edge Grabbing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 8.2 Sinkless Orientation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 9 Conclusions

67

10 AI Methodology

68

References

69

1

Introduction

What can a distributed system of n processes achieve despite process failures? This is a central question in distributed computing [PSL80, FLP85, Lyn96, AW04]. For a given distributed task, the answer depends on the number and the nature of failures one tolerates and the communication assumptions. Even when a task remains solvable, tolerating failures can substantially increase the cost of doing so. One therefore seeks to characterize the limits and the cost of fault tolerance. Another major line of research in distributed computing studies the round complexity of distributed graph algorithms [Lin92, Pel00]. In the standard setting, the network is represented by a graph G = (V, E) with at most n nodes and maximum degree at most ∆. Nodes initially have only local information and exchange messages along the edges of G. Each node must compute its part of a global solution, such as its color in a node coloring, its incident edges in a minimum spanning tree, or its distance from a designated source. Our goal is to understand how crash failures affect the round complexity of the widely studied class of locally checkable graph problems [Lin92, NS95, CKP19, GKM17, CP17, BHK+ 18, Bra19, BBC+ 19, Cha20, BBOS20, RG20]. A graph problem is called locally checkable if it is specified by a checking radius ℓ and a rule by which each node accepts or rejects a proposed solution based only on its induced radius-ℓ neighborhood, including the input and proposed output labels. Both the radius and the rule may depend on n. A proposed solution is valid if and only if every node accepts. This notion of local verification has roots in work on self-stabilization, where violations of global correctness are detected through local checks [AKY91, APSV91]. An extensively studied subclass is that of locally checkable labeling (LCL) problems, defined on graphs of constant maximum degree ∆, with constant checking radius ℓ, with input and output labels drawn from fixed finite alphabets, and with a fixed validity rule independent of n and identifiers [NS95]. For example, proper node coloring and maximal independent set are both locally checkable with checking radius one. For coloring, each node checks that its color belongs to the prescribed palette and differs from all neighboring colors. For maximal independent set, each selected node checks that no neighbor is selected, and each unselected node checks that some neighbor is selected. Both are LCL problems when ∆ = O(1), provided that the palette also has size O(1) for coloring. We work in the LOCAL model, the standard model for studying locality in distributed graph algorithms [Lin92, Pel00]. Nodes have unique identifiers. We assume that each node initially knows its own identifier, its input label (if any), the identifiers of its neighbors, and the bounds n and ∆. Computation proceeds in synchronous communication rounds. In each round, a node can send a separate message to each neighbor based on its current state. It then receives the messages sent to it in this round and updates its state. Message sizes and internal computation at the nodes are unrestricted. Time complexity is the number of rounds until all nodes output. We study the LOCAL model with crash failures. We use the standard crash model for synchronous systems [LF82, Lyn96]: a node follows its algorithm until it crashes, after which it performs no further computation and sends no further messages. In its crash round, an arbitrary subset of its prescribed outgoing messages may be delivered. In the fault-free setting, every deterministic T -round LOCAL algorithm can be put into a canonical form: each node first spends T rounds collecting the initial states of all nodes within distance T , and then simulates the algorithm locally to determine its own output, without further communication. The collected states include the nodes’ identifiers, input labels, and neighbor lists. Partial delivery complicates this approach: adjacent surviving nodes may obtain views that disagree on the same part of the graph. Independently simulating a fault-free algorithm on these views can therefore produce outputs that violate the local constraints. A node is called surviving if it does not crash during the execution. We extend the notion of local checkability to the setting with crashes as follows. For a locally checkable problem with checking radius 1

ℓ, a surviving node v is locally satisfied if and only if either some node in its radius-ℓ neighborhood in the original graph G crashes or the local constraint at v specified by the fault-free definition of the problem is satisfied. A crash-tolerant algorithm must ensure that every surviving node is locally satisfied. We study general methods for transforming fault-free LOCAL algorithms into crash-tolerant ones. We focus on deterministic algorithms. The formal model appears in Section 3.

1.1

Contributions

We introduce the consistent neighborhoods problem ΠCN (R) as a replacement for the neighborhoodcollection phase of fault-free algorithms.1 For an integer R ≥ 1, each surviving node v must output a view Hv : a labeled subgraph of its radius-R neighborhood in G, containing v and retaining the original identifiers and input labels. The views of adjacent surviving nodes must contain their common edge and agree on the subgraphs induced by the nodes within distance R − 1 of either endpoint, with distances measured within each view. These requirements ensure that each view contains every node reachable from its center by a path of at most R edges through surviving nodes. Information involving crashed nodes may be omitted, subject to consistency. Without crashes, every view must be the complete radius-R neighborhood. The formal definition appears in Definition 3. We show that consistent neighborhoods allow surviving nodes to simulate fault-free local algorithms for locally checkable problems without further communication. Each surviving node simulates the algorithm on its own view and adopts the output assigned to it. For sufficiently large R, the outputs ensure local satisfaction. This requires the fault-free algorithm to remain correct on every subgraph of G, since the views used for simulation may omit nodes or edges. The simulations, checking radius, and validity rule all use the original global bounds n and ∆. The next theorem gives this guarantee and the optimal fault-free round complexity of ΠCN (R). Theorem 1 (Consistent neighborhoods and fault-free algorithms). The following statements hold in the deterministic LOCAL model. (i) For every integer R ≥ 1, ΠCN (R) can be solved in R rounds in the fault-free setting. This bound is optimal in the worst case even for ∆ = 2. (ii) Let Π be a locally checkable problem with checking radius ℓ ≥ 1, and let A be a deterministic algorithm that solves Π within T rounds on every subgraph of G in the fault-free setting, with inherited labels and the original bounds n, ∆, where T ≥ 0. Given a solution to ΠCN (R) on G with R ≥ T + ℓ + 1, each surviving node can compute its output without communication so that every surviving node is locally satisfied for Π. This transformation makes the round complexity of ΠCN (R) the central question. Can consistent neighborhoods still be constructed in O(R) rounds under crashes, or in a number of rounds depending only on R and the crash bound f ? More generally, we study their complexity as a function of R, f , ∆, and n, obtaining upper and lower bounds that match in several parameter regimes. The bound f is assumed known to the nodes only when explicitly stated. Our upper bounds hold in the standard crash model described above. Several lower bounds hold even in the more restrictive atomic crash-fault model, in which a node crashes at the beginning of a round, before sending any messages. The following theorem rules out bounds depending only on R and f on general graphs: even when R = 3 and f = 1, every deterministic algorithm for ΠCN (R) requires Ω(n) rounds in the worst 1

Related neighborhood-view consistency specifications for wireless sensor networks were studied in [JM09, JM16]; see Section 1.2.

2

case. This construction has maximum degree Θ(n), so we also establish lower bounds for smaller degrees, with explicit dependence on ∆, R, and f . Theorem 2 (Lower bounds for ΠCN (R)). Let R ≥ 1 and f ≥ 1 be integers. The following worst-case lower bounds hold for deterministic algorithms solving ΠCN (R) in the synchronous LOCAL model with standard crash failures, even when the bounds n, ∆, and f are globally known. (i) Ω(n) rounds on general graphs with at most n nodes for R ≥ 3, even when f = 1.
(ii) On graphs with at most n nodes and maximum degree at most ∆, Ω (∆ − 1)⌊(R−1)/2⌋ rounds are necessary, provided ∆ ≥ 3, R ≥ 4, n ≥ 4(∆ − 1)⌊(R−1)/2⌋ , and f ≥ (∆ − 1)⌊(R−1)/2⌋−1 . Further, for every ∆ ≥ 3, there exists an integer R0 (∆) ≥ 4 such that, for every R ≥ R0 (∆), √ R−3⌈ R⌉ the stronger lower bound (∆ − 1) holds, provided n ≥ (∆ − 1)R and f ≥ ⌈(∆ − 1)R /∆⌉.
(iii) On graphs with at most n nodes and maximum degree at most ∆, Ω (R − 2 log∆−1 f ) · f · ∆ rounds are necessary, provided ∆ ≥ 3, R ≥ 2⌈log∆−1 f ⌉ + 4, and n ≥ R · f · ∆. In the atomic crash-fault model, (ii) and (iii) hold with the additional assumption f ≥ 2, and the Ω(n) lower bound in (i) holds for R ≥ 4, even when f = 2. We complement these lower bounds with an O(n)-round algorithm and two bounds independent of n: O((∆ − 1)R ) for ∆ ≥ 3, and O(∆ · R · f ) when a bound f ≥ 1 on the number of crashes is known. Moreover, O(R) rounds suffice under any number of crashes when ∆ = 2 or the graph has girth greater than 2R, including forests. On these graph classes, Theorem 1 transforms T -round LOCAL algorithms for locally checkable problems with checking radius ℓ into crash-tolerant algorithms running in O(T + ℓ) rounds, provided they remain correct on all subgraphs of the input graph. We state the following upper bounds for ∆ ≥ 2. The case ∆ ≤ 1 is immediate: every connected component has at most two nodes, and ΠCN (R) can be solved in at most one round. Theorem 3 (Upper bounds for ΠCN (R)). Let R ≥ 1 be an integer. In the synchronous LOCAL model with crash failures and the globally known bounds n and ∆ ≥ 2, ΠCN (R) can be solved on any graph G with at most n nodes and maximum degree at most ∆ deterministically in (i) O(n) rounds, for any number of crashes; (ii) O((∆ − 1)R ) rounds if ∆ ≥ 3, for any number of crashes; (iii) O(∆ · R · f ) rounds, if a bound f ≥ 1 on the number of crashes is globally known; (iv) O(R) rounds if ∆ = 2 or the graph has girth greater than 2R, for any number of crashes. In particular, this applies to forests. These bounds also let us relate crash tolerance to the complexity theory of LCL problems. On general graphs of constant maximum degree, the deterministic fault-free LOCAL complexity of an LCL problem is either O(log∗ n) or Ω(log n) [CKP19]. We show that every LCL problem in the former regime retains an O(log∗ n)-round algorithm in the presence of crashes. At the logarithmic threshold, however, tolerating crashes can already increase the complexity to Θ(n). Theorem 4 (Crash tolerance and the LCL complexity gap). The following statements hold in the synchronous LOCAL model with O(log n)-bit identifiers. (i) For every fixed ∆ ≥ 2 and every LCL problem Π, if Π admits a deterministic O(log∗ n)-round algorithm on all graphs of maximum degree at most ∆ in the fault-free setting, then Π admits a deterministic O(log∗ n)-round algorithm tolerating any number of crash failures. 3

(ii) There is an explicit input-labeled LCL problem Π with checking radius two, defined on all graphs of maximum degree at most five, whose deterministic fault-free complexity is Θ(log n) and whose deterministic crash-tolerant complexity is Θ(n). The lower bound holds already with Θ(n) atomic crashes, and the upper bound holds in the standard crash-fault model. To prove Theorem 4(i), we use the normal form of deterministic O(log∗ n)-round LCL algorithms: a coloring phase followed by constant-round computation [CKP19, BCHM+ 21]. The coloring can be made crash tolerant, and our consistent neighborhoods algorithms handle the remaining computation in O(1) rounds. For part (ii), we encode agreement on a root’s input bit as a fixed LCL and apply a similarity-chain argument to obtain the linear lower bound. Subsection 2.4 gives the main ideas. The separation in Theorem 4(ii) also holds without problem-specific input labels, with possibly larger constant degree and checking radius; see Subsection 7.2.4. Theorem 4(ii) shows that no general transformation can preserve the asymptotic round complexity of every deterministic fault-free LCL algorithm. Problem-specific transformations can nevertheless preserve this complexity. Sinkless orientation requires every node of degree at least three to have an outgoing edge. Under crashes, adjacent surviving nodes must agree on their common edge’s orientation, and every surviving node of input degree at least three must have an outgoing edge, possibly towards a crashed neighbor. Our transformation adds only one round and tolerates any number of crashes. These guarantees are stronger than local satisfaction: they also apply to surviving nodes with crashed neighbors, i.e., crashed nodes within the checking radius. Theorem 5 (Sinkless orientation under crash faults). On graphs of arbitrary maximum degree, any deterministic T -round LOCAL algorithm for sinkless orientation in the fault-free setting can be transformed into a deterministic (T + 1)-round LOCAL algorithm satisfying the crash-tolerant requirements above for any number of crash failures. For fixed ∆ ≥ 3, sinkless orientation has deterministic fault-free complexity Θ(log n) [BFH+ 16, CKP19, GS17]. Thus, this LCL in the Θ(log n) class retains its complexity under crashes.

1.2

Related Work

Our work lies at the intersection of distributed graph algorithms [Lin92, NS95] and fault-tolerant distributed computing [Lyn96]. Although fault-free complexity is well studied, less is known about how failures affect round complexity. Several lines of work address related questions in graph algorithms and networks with arbitrary topologies. We review the most relevant ones below. Agreement in general networks. The classical literature on agreement problems is especially relevant to our work. In consensus, each of n parties holds an input and up to f parties may fail. All non-faulty parties must terminate and agree on an output satisfying a validity condition. For crash failures, the usual validity condition requires the output to be an input of some party. Deterministic consensus is impossible in asynchronous networks even with one possible crash [FLP85]. Randomized protocols circumvent this impossibility under suitable resilience assumptions [Ben83, Rab83]. In complete synchronous networks, deterministic crash consensus has tight worst-case round complexity min{f + 1, n − 1} for every f < n [LF82, Lyn96, AW04].2 Global consensus in general networks also requires connectivity [Dol82, Had87, WW20, TV15]. In undirected networks, no permitted crash set may separate surviving nodes [Had87]. For a known 2

Under validity requiring that a unanimous input of the non-faulty parties be preserved, Byzantine consensus in complete synchronous networks requires n > 3f without digital signatures or n > 2f with signatures, and f + 1 rounds suffice in either case [PSL80, DS83, Fis83].

4

graph G and a known crash bound f below its node connectivity, [CFP+ 23] study global synchronous crash consensus. Their round bound is a radius accounting for crash patterns. Our consistent neighborhoods problem does not require global agreement and therefore remains solvable even when crashes disconnect the network. Related relaxations of global agreement have also been studied. For example, [CKOO23] study disconnected agreement in synchronous networks with non-faulty nodes and omission-prone links. They require agreement within components formed by links that have not omitted messages. Fraigniaud, Nguyen, and Paz [FNP25] study local consensus under crash failures: each surviving component agrees on some node’s initial proposal, possibly from outside that component. Their n − 1-round flooding algorithm provides the componentwise agreement argument underlying our O(n)-round ΠCN algorithm in Theorem 3(i). All our crash-tolerant lower bounds use constructions requiring consistency among a global set of nodes in fault-free executions. This lets us adapt classical indistinguishability-chain arguments [FL82, LF82, Lyn96]. Related arguments for general networks appear in [FNP25]. Topology and neighborhood discovery. Nesterenko and Tixeuil [NT06] study topology discovery in asynchronous networks with Byzantine faults. Dolev, Liba, and Schiller [DLS13] give self-stabilizing solutions and consider constant-radius neighborhood discovery. These results require enough connectivity for reliable communication despite faults. Jhumka and Mottola [JM09, JM16] study neighborhood-view consistency in wireless sensor networks as a service for higher-level protocols. Their specifications concern maintaining consistent one-hop neighbor information under crashes, communication omissions, and transient state faults. We study terminating algorithms for partial radius-R graph views with consistency across surviving edges under permanent crashes, and use these views to simulate fault-free local algorithms. Fault-tolerant graph algorithms in fully connected networks. Byzantine graph computation has also been studied in the congested clique, where every pair of processors can communicate directly, regardless of the input graph. Augustine, Molla, Pandurangan, and Vasudev [AMPV22] study connectivity testing, while Cifuentes-Núñez, Montealegre, and Rapaport [CNnMR26] study acyclicity and bipartiteness. Faulty processors can hide or misreport parts of the graph, so either answer is permitted on some inputs. Deterministic transformations make fault-free congested-clique algorithms tolerate a constant fraction of node crashes [CHS26, CHFGS25, FG26]. They either protect inputs during initial failure-free rounds or assume inputs are already encoded and stored redundantly across the network. Complete communication lets surviving processors take over the computations of crashed ones. Wait-free locally checkable problems. Closely related to our work are wait-free algorithms for locally checkable problems, where processes are asynchronous and any number may crash. Wait-freedom requires every surviving process to terminate regardless of others’ progress or failures. Wait-free 3-coloring of rings was first obtained in the DECOUPLED model, whose communication remains synchronous and reliable: routers keep forwarding messages after their processes crash [CDGF+ 19]. The abstract ABST-DECOUPLED model additionally provides snapshots of the local topology. This enables generic transformations from deterministic LOCAL algorithms for input-free LCL problems to wait-free algorithms [DGFFR25]. In the ASYNC LOCAL model, processes communicate through shared registers: each process writes to its own register and reads its neighbors’ registers. A crashed process’s last written state remains readable. Wait-free algorithms color cycles [FLMR22] and general graphs [BFLM+ 24]. Yet deterministic wait-free MIS is impossible on cycles of at least seven nodes even when correctness is required only in fault-free executions [BFLM+ 24], ruling out generic wait-free transformations. Our synchronous LOCAL model admits a generic transformation ensuring local satisfaction under Theorem 1(ii), although substantial asymptotic slowdown can be unavoidable (Theorem 4(ii)). 5

Repairing configurations. Other work repairs or maintains valid configurations after state corruptions or network changes. A classical approach is self-stabilization [Dij74, APSV91, APSVD94, LSW09, BEG18, Tur19], which handles arbitrary transient state corruptions. After the last fault, the system must reach a valid configuration in finite time and remain valid thereafter; this recovery time is the stabilization time. Strict stabilization [NA02, DTZ12, CPS21] also tolerates permanent Byzantine faults, eventually guaranteeing correctness at nodes sufficiently far from faulty ones. Generic transformations convert deterministic T -round LOCAL algorithms with T ≥ 1 into synchronous self-stabilizing algorithms with stabilization time O(T ) [AV91, LSW09]. Recent work gives asynchronous self-stabilizing compilers for terminating synchronous algorithms [DIJM24] and, under additional assumptions on the input algorithm, randomized synchronous LCL compilers whose recovery time depends on the number of affected nodes [BEIK24]. These guarantees concern recovery after transient faults cease, whereas our algorithms terminate despite crashes during execution. Fault-local recovery seeks repair times governed by the number of affected nodes rather than network size. Kutten and Peleg [KP95] give such transformations for MIS after transient state corruptions. Dynamic distributed algorithms [KW13, CHHK16, PPS16] update an existing solution after node or edge insertions and deletions. Highly dynamic networks [BKM19, CHDK+ 21] allow changes throughout the computation. Mayer, Naor, and Stockmeyer [MNS95] already studied robust local computation under continually failing and reappearing links. Mendability [BHM+ 22, MSV23] concerns extending locally correct partial LCL labelings. The task is to label another node while preserving local correctness, possibly changing existing labels. The cost measures how far changes extend from that node or how many nodes are relabeled. Preprocessing for future failures. Another line of work constructs fault-tolerant subgraphs in a failure-free preprocessing phase. Fault-tolerant spanners preserve approximate distances after failures [CLPR09, DK11, Par22]; fault-tolerant tree structures and tree augmentation preserve shortest-path, spanning-tree, or connectivity guarantees [GP16, Par20, CHD18]. For local graph problems, [CDPR20] study which graphs admit an MIS that remains valid under edge deletions preserving connectivity; [DFPR25] extend this to bounded deletions, domination, and matching.

1.3

Organization of the Paper

We give a technical overview in Section 2 and introduce the model and notation in Section 3. Section 4 defines consistent neighborhoods and applies them to local simulation. Sections 5 and 6 give upper and lower bounds. Section 7 studies how crashes affect LCL complexity, and Section 8 gives transformations for edge grabbing and sinkless orientation. We conclude in Section 9.

2

Technical Overview

This section outlines the main technical ideas behind our results. We revisit the consistent neighborhoods problem in Subsection 2.1 and discuss its upper and lower bounds in Subsections 2.2 and 2.3. We then turn to crash tolerance for LCL problems in Subsection 2.4 and the sinkless-orientation transformation in Subsection 2.5.

2.1

The Consistent Neighborhoods Problem

Every deterministic T -round algorithm in the fault-free LOCAL model can be put into the following canonical form. First, each node collects the initial states of all nodes within distance T in T rounds. It then simulates the algorithm locally to determine its output, without further communication. This directly solves the consistent neighborhoods problem in the fault-free setting: the collected views 6

describe T -hop neighborhoods of the same labeled graph G and therefore agree on their overlaps. The precise relation between the view radius R and the collection time T depends on the initial knowledge and consistency requirements. For our model and definition of ΠCN (R), Theorem 1(i) establishes that the optimal worst-case fault-free complexity is exactly R rounds. In the presence of crashes, however, information may spread unevenly, so neighboring nodes may collect views of overlapping parts of different labeled graphs. When locally simulating an algorithm for a locally checkable problem, such views may not yield consistent, valid outputs. To solve ΠCN (R), we must therefore ensure that neighboring views agree on their overlaps. Consistency is required only between neighboring views, but it propagates along surviving paths, with the agreement radius decreasing by one at each hop. For a locally checkable problem with checking radius ℓ, taking R ≥ T + ℓ + 1 ensures that every node in a crash-free checking neighborhood computes from its own view the output assigned to it by the T -round simulation on the center’s view. The local check thus sees the same neighborhood and outputs as in this single fault-free simulation. If the algorithm is correct on every subgraph of G, these outputs satisfy the local constraints, as stated in Theorem 1(ii).

2.2

The Consistent Neighborhoods Upper Bounds

A warm-up: obtaining an O(n)-round algorithm. Consider a graph with at most n nodes and assume for now that the surviving nodes remain connected after all crashes. Each node initially knows its labeled star: its own identifier and input label (if any), together with its neighbors’ identifiers. Flooding these stars for n − 1 rounds gives every surviving node the stars of all surviving nodes, since any two are joined by a surviving path of length at most n − 1. Each node can therefore reconstruct a graph containing the surviving graph, possibly with additional information from crashed nodes. This suggests a simple strategy: gather information and then use the reconstructed graphs as proposals in a standard consensus algorithm (see [CFP+ 23] for earlier work on arbitrary graphs). Each node forwards its smallest known proposal, under a fixed total order, for another n − 1 rounds and then outputs its current minimum; cf., e.g., [FNP25, full version, Lemma 24]. Crashes may, however, disconnect the surviving graph. In this case, agreement is needed only within each surviving component. This is the goal of the local consensus problem studied by Fraigniaud, Nguyen, and Paz [FNP25]. Their elementary algorithm floods identifier–proposal pairs for n − 1 rounds, after which the nodes in each surviving component have the same collection and can select the same proposal. Applying this flooding principle to labeled stars combines gathering and agreement in a single phase of n − 1 rounds, proving Theorem 3(i). Why shorter flooding does not ensure agreement. The linear-time algorithm solves ΠCN (R) for every R, but for smaller R we would like to have faster algorithms with bounds ideally depending only on R, ∆, and, when known, f . Simply stopping flooding after R rounds does not suffice. Consider a cycle of length R + 2, for R ≥ 2, with consecutive nodes w, u, v. Suppose that only w crashes, in round 1, sending its star only to its other neighbor. The star travels around the cycle and reaches v in round R, but has not yet reached u. If nodes output the graphs induced by their collected star sources, v includes w as a neighbor of u, whereas u omits it, violating consistency across {u, v}. Simply discarding this late-arriving star at v also fails if its other neighbor retains it: that neighbor received the star one round earlier and includes w within distance R − 1, so the disagreement moves to their common edge. Thus, whether to include or omit information propagated in only one direction is itself an agreement problem.3 3 As we show later, on cycles, this issue can be resolved in O(R) rounds (Theorem 3(iv)). Such a bound however does not extend to general graphs.

7

Flooding the gathered information. After gathering, surviving nodes must coordinate which nodes and edges to include so that adjacent outputs agree on their required overlaps. A natural next step is to freeze and flood each node’s collection for a prescribed number of rounds. Crashes may destroy short routes and force long detours, so a short flooding phase may miss nodes that must agree on whether to include a source. Flooding longer does not resolve this: unrestricted flooding may bring an additional collection to one endpoint of a surviving edge only in the final round. If its source belongs to the required overlap, the other endpoint must make a compatible inclusion decision without having received the collection. We therefore restrict each source’s information to a fixed propagation graph that stays within distance R of its source while retaining every edge across which agreement about that source is required. Propagation graphs. Each node floods its initial labeled star for R rounds. For each node v that completes gathering, define v’s propagation graph Γv as the subgraph of G induced by v and all nodes that received v’s star during this phase, including nodes that later crash. Thus, Γv records where information about v has spread. Flooding for R rounds keeps Γv within distance R of v. After gathering, each node v initiates a fresh token containing only its identifier and broadcasts it within Γv . Only v initially holds this token, and only members of Γv retain and forward it. The identifier suffices because these nodes already know v’s labeled star. All sources broadcast in parallel, without enlarging the propagation graphs. We run this phase long enough that, in every connected component of the surviving part of Γv , either all nodes store v’s token or none does. This also holds if v crashes during the second phase. Section 5.4 formalizes this for every R ≥ 1. Why propagation graphs help. Each surviving node outputs the labeled graph induced by itself and the sources whose tokens it receives in the second phase. The collected stars supply the edges and labels. Surviving neighbors store each other’s tokens, so their common edge is included. Crucially, every node that is a source of the second phase completed the first phase. Thus every path in an output was available throughout the first phase, even if some of its nodes crashed later. Consider a surviving edge {u, v} and a path in u’s output of length at most R − 1 from x to either endpoint of {u, v}. During gathering, x’s star reaches that endpoint along this path by round R − 1 and the other endpoint across {u, v} by round R. Thus, {u, v} is an edge of Γx . Since x belongs to u’s output, u stores x’s token. Agreement within the surviving components of Γx ensures that v also stores it and includes x in its output. Applying this argument to every node on the path transfers the entire path to v’s output. Applying it in both directions makes the outputs agree on the required overlap, including edges and labels. Without crashes, Γx contains exactly the nodes within distance R of x, so the outputs are complete radius-R neighborhoods. Bounding the number of rounds. Tracing successive first receptions of a token backwards gives a simple path, with one edge per round. For ∆ ≥ 3, each propagation graph has O((∆ − 1)R ) nodes, so no first reception occurs later than this many rounds. Each surviving component therefore receives the token everywhere or nowhere by then, proving Theorem 3(ii). For ∆ = 2, the same argument gives O(R) rounds, as in Theorem 3(iv). Alternatively, every node of a propagation graph has a path of length at most R to its source, so its diameter before crashes is at most 2R. Crashes can destroy these shortcuts, but there are at most ∆f surviving neighbors of crashed nodes. If a crash occurs in the propagation graph, assign every surviving node to one such neighbor by following a shortest path toward a crashed node and stopping just before the first crash. The surviving prefix has length O(R), so nodes assigned to the same neighbor are connected by surviving routes of length O(R). Once a node receives the token, the token reaches every other node in its group within O(R) further rounds. Consecutive nodes on a first-reception path receive it one round apart, so the path contains at most O(R) nodes from each group. Adding at most f 8

C

F a

S: the surviving path

b

closing edge {a, b}, present only in G+

Figure 1: The common lower-bound framework. Only the red nodes F may crash. The green nodes S form a path in G− and a cycle in G+ , differing only in the dashed closing edge. Shortcuts through C ∪ F put the entire graph within distance R − 1 of every node of S; crashing F removes them. crashed nodes on this simple path and accounting for the crash-free case gives O(R·∆·f ) rounds when f ≥ 1 is known, proving Theorem 3(iii). Both bounds include gathering and are independent of n. Graphs of large girth. Finally, on graphs of girth greater than 2R, including forests, flooding stars for R rounds suffices. Each node outputs the graph induced by the sources of its received stars. Between any two nodes, there is at most one simple path of length at most R. Consider a source x within distance R − 1 of either endpoint of a surviving edge {u, v} in u’s view. By uniqueness, its first-reception path to u either has length at most R − 1, leaving time to forward the star to v, or passes through v. Thus both endpoints receive the star by round R. Applying this to every node in the required overlap proves consistency, yielding the R-round bound in Theorem 3(iv).

2.3

The Consistent Neighborhoods Lower Bounds

The lower bounds for ΠCN (R) in Theorem 2 show how crashes can force coordination over distances much larger than R. Their proofs combine consistency with indistinguishability: even when crashes destroy short communication routes, a witness that cannot detect the change forces the relevant outputs to remain unchanged. We first explain this pattern, then describe the three constructions. The common framework. We compare two graphs G− and G+ with the same node set, identifiers, labels, and known global bounds. Their nodes are partitioned into C, F , and S as in Figure 1. The nodes of S, which always survive, form a path from a to b in G− ; adding the closing edge {a, b} gives G+ . Only nodes in F may crash. Shortcuts through C ∪ F place every node of G+ within distance R − 1 of each node of S. Without crashes, completeness requires each node to output its full radius-R neighborhood (Definition 3), which is all of G+ for nodes in S. Every path from S to C passes through F . Once all nodes of F have crashed, communication between nodes of S must therefore follow the long path or cycle. A large distance after crashes does not by itself prove a lower bound, since ΠCN (R) permits incomplete views. Consistency makes the complete output G+ an all-or-nothing choice on S (Lemma 21). If one node p ∈ S outputs G+ , every node of its view is within distance R − 1 of p. Consistency forces each neighbor in S to include this graph and hence output G+ . Applying this along S forces every node of S to output G+ , even if some nodes have crashed. Once F stops sending messages, a difference between two executions can spread along S by at most one hop per round (Lemma 22), so reaching nodes Θ(|S|) hops away requires Ω(|S|) rounds. The similarity chain below shows why choosing incomplete views cannot avoid this coordination.

9

Similarity chains. We use the similarity chain technique from consensus lower bounds [LF82, Lyn96]. For a deterministic T -round algorithm, a similarity chain is a sequence of executions E1 , . . . , EK in which each consecutive pair is indistinguishable through round T at a witness node v surviving both: its initial state and received messages are identical. The witness may change between pairs. For binary consensus, validity requires output 0 in a fault-free all-zero execution and output 1 in a fault-free all-one execution. Along a chain between them, indistinguishability fixes each witness’s output across the pair, and agreement forces the same output at all surviving nodes in each execution. Thus, the common decision cannot change along the chain, contradicting validity. For a hypothetical T -round algorithm for ΠCN (R), the all-or-nothing property plays the role of agreement. We start with the fault-free execution on G+ , where completeness forces output G+ throughout S, and move the crashes of F before round 1. At each step, a witness in S retains output G+ , so consistency forces all of S to retain it. We then switch to G− . Only a and b initially know whether the closing edge exists. With F silent, this difference travels along S at most one hop per round (Lemma 22). A node farther than T from both endpoints along the cycle therefore still outputs G+ , including the nonexistent closing edge. It remains to give a witness for each step. Linear bounds via similarity chains (Theorem 2(i)). With no degree restriction, let F = {z}, |S| = n − 1, and connect z to all nodes of S (Figure 4). Both have diameter 2, so R ≥ 3 suffices. Starting from the fault-free execution, we first let z crash in round T after sending all its messages. No surviving node can notice this change through round T . We then keep the crash round fixed and, in each successive execution, withhold one additional round-T message of z, leaving all earlier rounds unchanged. Once none is delivered, this looks to the surviving nodes exactly like a crash in round T − 1 after sending all its messages. We repeat for rounds T − 1, T − 2, and so on, until z sends nothing in round 1. Removing a round-r message affects only its recipient initially. Since z sends nothing afterwards, any effect spreads along S for at most T − r further rounds. For T < |S|/2, a node on the opposite side of the cycle cannot distinguish the two consecutive executions and thus serves as a witness (Lemma 23). The final switch to G− has a witness for T < |S|/2 − 1, giving Ω(n) rounds with one standard crash. In the atomic model, a crash suppresses all messages of a node at once. A witness must therefore be far along the cycle from all neighbors in S of the node whose crash moved. A single node adjacent to all of S does not work. We instead use two adjacent nodes in F , each attached to one half of the n − 2 nodes of S. The diameter becomes three, requiring R ≥ 4. We move both crashes to rounds T, T − 1, . . . , 1, one at a time. In each step, neither node sends further messages in the remaining rounds, so the effect again spreads only along S. For T < |S|/4, a node in the middle of the opposite half of S cannot distinguish the two consecutive executions and is a witness (Lemma 25). This gives the Ω(n) bound with two atomic crashes. The remaining bounds use the same chains, moving all crashes one round earlier, one node at a time in the atomic model. Keeping each crashing node attached within a short consecutive block of S leaves a distant witness at each step. This gives an Ω(|S|) lower bound, so we seek the longest S while keeping every node within distance R − 1 of each node in S and respecting n, ∆, and f . Exponential bounds in the radius (Theorem 2(ii)). For ∆ ≥ 3, only O((∆ − 1)R ) nodes fit within distance R − 1, limiting the size of S. To obtain an exponentially long cycle for R ≥ 5, we use a complete (∆ − 1)-ary tree of height h = ⌊(R − 1)/2⌋. Its leaves, connected in left-to-right order, form the path S; their parents form F (Figure 5). Tree paths have length at most 2h ≤ R − 1, while each crashing node attaches to consecutive leaves. Hence, |S| = (∆ − 1)h gives the first exponential lower bound. The factor two in the exponent comes from paths going up and down the tree. To improve the exponent, we use a ∆-regular core H of diameter at most D with N = Ω∆ ((∆ − 1)D /D) nodes, obtained from random regular graphs [BFdlV82]. Its nodes have no spare degree, so we 10

subdivide selected edges, placing a node of F on each and connecting it to a new node of S (Figure 6). Subdividing every edge would double distances. Instead, we greedily select a maximal set of edges at pairwise distance at least ℓ. A shortest core path then crosses only O(1 + D/ℓ) selected edges, while maximality guarantees Ω(N/(∆ − 1)ℓ ) selected edges in total. Thus, greater √ separation limits the increase in the core’s diameter but allows fewer nodes in√S. Choosing ℓ = ⌈ R⌉ balances these losses, √ allowing D = R − O( R) and giving |S| = (∆ − 1)R−O( R) for every fixed ∆ and all sufficiently large R. Each crashing node has one neighbor in S, preserving distant witnesses for the similarity chain. Dependence on the crash bound (Theorem 2(iii)). With at most f crashes, at most f ∆ nodes of S can be adjacent to F . To gain a factor depending on R, we extend S by spacing these attachment nodes apart along the path (Figure 7). For f ≥ 2, the f crashing nodes form the leaves of a tree with at most ∆ − 1 children per node and height at most h = ⌈log∆−1 f ⌉. The set S consists of a set SF of f (∆ − 1) nodes and paths of length L between any two consecutive nodes in SF (so |S| = Θ(f ∆L)). We attach each leaf of the tree (i.e., each node in F ) to a disjoint block of ∆ − 1 consecutive nodes of SF . Every node of S is within L/2 hops of an attachment node, so reaching such a node at each end and passing through the tree takes at most L + 2h + 2 hops. Choosing L = R − 2h − 3 keeps this within R − 1 and yields |S| = Θ((R − 2 log∆−1 f )f ∆) under the theorem’s assumptions. These consecutive groups provide distant witnesses for atomic crashes. For f = 1, a single hub with ∆ spaced-out attachment nodes gives Ω(R∆) under standard crashes.

2.4

Crash Tolerance for Locally Checkable Labelings

The gap theorem of Chang, Kopelowitz, and Pettie [CKP19] states that, on graphs of fixed maximum degree, the deterministic fault-free complexity of an LCL problem is either O(log∗ n) or Ω(log n). Theorem 4 relates these regimes to crash tolerance: every LCL with a deterministic O(log∗ n)-round algorithm on all such graphs admits such an algorithm tolerating any number of crashes. In contrast, a problem of fault-free complexity Θ(log n) can require Θ(n) rounds under crashes. Isolating the symmetry-breaking step (Theorem 4(i)). We use the normal form of deterministic O(log∗ n)-round LCL algorithms on bounded-degree graphs [CKP19, BCHM+ 21]. For a constant t depending only on the problem and the degree bound, such an algorithm first computes a coloring with a constant number of colors in which any two distinct nodes at distance at most t have different colors. It then uses this coloring to solve the LCL in at most t rounds. Thus, only the coloring has a round complexity dependent on n. We make this step crash tolerant directly and use consistent neighborhoods only for the constant-round second step. We use Linial’s color reduction [Lin92], starting with identifiers as colors. Each old color determines a candidate set of new colors. After exchanging colors for t rounds, a node chooses from its own set while avoiding those of received colors other than its own. Missing messages only leave more candidates available. Let A be the set of nodes that complete the coloring phase. Nodes within distance t in G[A] receive each other’s colors at every step, so mutual exclusion preserves distinct colors. This gives the required coloring on G[A] in O(log∗ n) rounds (Lemma 32). Finishing on consistent neighborhoods. We keep the colors fixed and run Algorithm 5 with fresh labeled stars that include them. Every view is a subgraph of G[A], so the coloring is inherited by all nodes in a view even if some of its nodes crash during the construction. Two distinct nodes within distance t in a view are also within distance t in G[A], so their inherited colors differ. The constant-round algorithm can thus be simulated on every view. Taking R = t + ℓ + 1, where ℓ is the checking radius, ensures local satisfaction for the original LCL by the simulation argument of Theorem 1(ii). For constant degree bound and R, Theorem 3 constructs these views in O(1) rounds. Together with coloring, this takes O(log∗ n) rounds. 11

A linear lower bound for an LCL problem (Theorem 4(ii)). We first define a locally checkable task on a graph family where the similarity-chain argument from Subsection 2.3 yields a linear crash lower bound, although the task is solvable in logarithmic time without crashes. We then extend the task to arbitrary input-labeled graphs of maximum degree five. Following earlier LCL constructions [BBOS18, BBOS20, BCHM+ 21, BGK+ 25, HN25], we encode the intended structure by finite input labels and verify it locally. Nodes that fail a structural check form the defect set. On malformed components, nodes can use locally verifiable error outputs that certify defects or point toward them. To preserve the separation, these outputs must be impossible on correctly labeled components without crashes, yet computable in O(log n) rounds on malformed components. This preserves the fault-free upper bound and the required outputs at both ends of the chain. We use complete binary trees whose levels are joined into horizontal paths. Each node must output the root’s input bit. This is enforced locally by requiring neighbors to agree and the root to match its input. The fault-free complexity is Θ(log n): the diameter is logarithmic, as is the distance from the root to the leaves. After a level near the leaves crashes, however, the surviving bottom levels form a long strip without the tree’s short communication paths. Structural input labels specify parents, children, and horizontal neighbors, with radius-two checks characterizing the intended family. The extended LCL Πbit requires adjacent nodes either to output the same bit or both to use error outputs. An error output certifies a structural defect at its node or points along a mutually consistent parent–child edge to another error output; two adjacent nodes may not point to each other. On a correctly labeled component without crashes, error outputs are impossible: there are no defects, and the parent–child tree admits no pointer cycle without two nodes pointing to each other. In a malformed component, every node is within O(log n) hops of the defect set along mutually consistent parent–child edges (Lemma 33). The structural checks force successive internal levels to double in size; if no nearby defect exists, they instead force a complete, correctly labeled component. Nodes at defects certify failed checks, and other nodes point along shortest parent–child paths to the defect set, giving the O(log n) fault-free upper bound. For the crash lower bound, only nodes in the level F three edges above the leaves may crash; let S be the bottom three levels (Figure 8). The set F has Θ(n) nodes. Each leaf’s radius-two checking neighborhood survives, so its local constraints must still hold. Adjacent leaves must either output the same bit or both use error outputs. The leaf path thus forces a common bit or error outputs at every leaf. For a contradiction, consider a deterministic algorithm that always terminates within T := |F | rounds. Starting from the fault-free execution with root bit 0, move the atomic crashes of F to rounds r = T, T − 1, . . . , 1, one node at a time. Once all of F crashes before round 1, S is cut off from the root, so we switch the root bit to 1 and traverse the crash schedules in reverse order (Figure 9). For a step moving a crash into round r, no node of F sends in rounds r + 1, . . . , T ; differences can then propagate from the changed node’s children only through G[S], for at most T − r < |F | hops. For each node of F , one of the two extreme leaves is at distance at least |F | from that node’s children in G[S] (Observation 2 and Lemma 36), providing a witness for the corresponding crash-time changes through round T . Initially all leaves output 0. Each witness retains 0, forcing all leaves to retain 0 throughout the chain. The fault-free endpoint with root bit 1 yields a contradiction. Since |F | = Θ(n), this proves an Ω(n) lower bound already for atomic crashes. The general simulation using Theorem 3(i) and Theorem 1(ii) gives the matching O(n) upper bound.

12

2.5

Problem-Specific Transformation for Sinkless Orientation

By Theorem 4(ii), no general transformation can preserve the asymptotic round complexity of every deterministic fault-free LCL algorithm. For particular problems, however, the asymptotic round complexity can sometimes be maintained by exploiting the problem’s structure directly. We illustrate this for sinkless orientation, which requires nodes to orient their edges so that every node of input degree ≥ 3 (i.e., in the input graph G) has at least one outgoing edge. We use edge grabbing as an intermediate problem: every node of input degree ≥ 3 grabs exactly one incident edge so that no edge is grabbed by both endpoints. Any T -round fault-free sinkless orientation algorithm yields a T -round edge grabbing algorithm: each such node grabs an outgoing edge. We run it while tracking failures. On first detecting a missing message or receiving a failure notification, a node records that edge, grabbing it if its input degree is at least three, and notifies its neighbors in subsequent rounds. Nodes that detect no failure within T rounds keep their fault-free views and outputs. Surviving endpoints cannot grab the same edge: either both follow the fault-free algorithm, or the first to detect a failure does so at a different neighbor, since the other endpoint survives and has not yet sent a notification. In one additional round, nodes announce their grabbed edges. Each such edge is oriented away from the node that grabbed it, and other edges are pointed towards the smaller identifier. Surviving neighbors agree on the orientation of their common edge, and every surviving node of input degree ≥ 3 has an outgoing edge, possibly towards a crashed neighbor, proving Theorem 5. For both edge grabbing and sinkless orientation, the correctness guarantees also hold at surviving nodes whose checking neighborhoods contain a crash.

3

Preliminaries

In this section, we introduce the graph notation and the communication and crash-fault models used throughout the paper. Moreover, we discuss the initial knowledge available to each node and we formally define the notion of local satisfaction under crashes.

3.1

Graphs and Related Notations

Throughout the paper, we consider finite, simple, undirected graphs G = (V, E) with at most n nodes and maximum degree at most ∆. We assume ∆ ≥ 2 without loss of generality: since ∆ is only an upper bound, graphs of maximum degree at most one are covered by taking ∆ = 2. Each node has a unique identifier and, if required by the problem, an input label. Subgraphs retain these identifiers and input labels. We say that two labeled graphs are equal if they have the same node set and edge set, and the identifiers and input labels agree at every node. For a node v ∈ V , its open and closed neighborhoods are NG (v) := {u ∈ V : {u, v} ∈ E} and NG [v] := NG (v) ∪ {v} respectively, and its degree is degG (v) := |NG (v)|. These notations extend naturally to a set of nodes X ⊆ V : its open and closed neighborhoods are [  NG (X) := NG (v) \ X, NG [X] := NG (X) ∪ X, v∈X

respectively. The induced subgraph of G on X is denoted by G[X]. We omit graph subscripts when they are clear from the context. We write distG for the shortest-path distance in G, with distance infinity between nodes in different components. For v ∈ V and X ⊆ V , the distance from v to X is distG (v, X) := minx∈X distG (v, x),

13

with min ∅ = ∞. For an integer r ≥ 0, the radius-r balls around v ∈ V and X ⊆ V are defined as follows: [ BG (v, r) := {u : distG (u, v) ≤ r} and BG (X, r) := BG (v, r). v∈X

The eccentricity of v is maxu∈V distG (v, u), and the diameter diam(G) of a nonempty connected graph is the maximum eccentricity of its nodes. The girth of G is the length of a shortest cycle, and acyclic graphs have infinite girth.

3.2

Model

Communication and parameters. We work in the synchronous LOCAL model [Lin92]. Computation proceeds in rounds: in each round, every node that has not yet crashed may send a separate message to each neighbor. Nodes that complete the round receive the messages delivered to them and update their local states. Message size and local computation are unrestricted, and the running time is measured by the number of communication rounds. All algorithms considered in this paper are deterministic. All nodes know upper bounds n and ∆ on the number of nodes and the maximum degree of G, respectively. These bounds do not need to be tight and remain unchanged when an algorithm is run on a subgraph. When solving ΠCN (R), all nodes also know the radius R. We state explicitly whenever we additionally assume that nodes know an upper bound f on the number of crashes. Identifiers are distinct integers in {1, . . . , max{2, n}cID }, where cID ≥ 1 is a fixed known integer. Crash faults. An adversary may crash up to f < n nodes over the entire execution. Crashes may occur in any round or before the initial local computation. Once a node crashes, it performs no further computation and sends no further messages. We call an execution with at most f crashes admissible. If f = 0, the execution is fault-free, and Theorem 1(i) gives the complexity of ΠCN (R). Unless stated otherwise, we assume f ≥ 1; correctness is still required in executions without crashes. In the standard crash-fault model, if a node crashes in round t, an arbitrary subset of its prescribed round-t messages may be delivered. In the atomic crash-fault model, a node crashes at the beginning of a round, before sending any messages in that round. Atomic crashes are therefore a special case of standard crashes. Apart from crashes, communication is reliable: a message sent in a round is delivered in that round whenever both its sender and its recipient complete the round. Unless stated otherwise, we use the standard model throughout the paper. A node is called surviving if it does not crash during the execution. Let F be the set of nodes that crash and S := V \ F the set of surviving nodes. The surviving graph is the induced subgraph G[S] [Lyn96]. Correctness. An algorithm solves a problem in T rounds if, in every admissible execution, all surviving nodes output by the end of round T and their outputs satisfy the problem’s correctness conditions. Nodes that crash have no output requirement. When we refer to the fault-free setting, these requirements apply only to executions without crashes. Locally checkable problems. A locally checkable problem is specified by a checking radius ℓ and local validity conditions: the local constraint at each node depends only on its induced radius-ℓ neighborhood, including the input and output labels. The radius, label domains, and validity conditions may depend on the known bounds n and ∆. The conditions are independent of identifiers unless these are explicitly part of the problem’s inputs; algorithms may use identifiers freely. We retain the original bounds throughout the execution and in every subgraph simulation, so the checking radius and rule remain unchanged. An LCL is specified by a fixed degree bound, fixed finite input and

14

output alphabets, a constant checking radius, and a fixed set of allowed rooted input/output-labeled neighborhoods (including local ports when used), independent of n and identifiers [NS95]. Definition 1 (Local satisfaction under crashes). Let Π be a locally checkable problem with checking radius ℓ. In an execution on the original graph G with crash set F, a surviving node v is locally satisfied if BG (v, ℓ) ∩ F ̸= ∅; otherwise, it is locally satisfied if and only if the input and output labels on G[BG (v, ℓ)] satisfy Π’s local constraint at v. The surviving outputs are valid if and only if every surviving node is locally satisfied. Distinct locally specified problems may have the same valid global fault-free solutions but different requirements under this definition.

3.3

Initial Knowledge

We now discuss the information available to each node at the start of an execution. In addition to the global parameters of Section 3.2, each node v initially knows its identifier, its input label (if any), and the identifiers of its neighbors in G. We denote its initial topological information by the star σv = (v, NG [v]) with root v, consisting of v, its neighbors, and all edges incident to v. This does not include edges between neighbors of v or their input labels. The root’s input label, if present, is included when the star is communicated but omitted from the notation. If required by the problem definition, we additionally assume that each node knows distinct local port numbers for its incident edges. Its star records these numbers at the root. They are included when comparing labeled graphs and are preserved without renumbering in subgraphs. For ΠCN (R) and locally checkable problems under Definition 1, the assumption that stars are initially known can be relaxed at the cost of one additional round. We may instead assume that each node initially knows only its own identifier, its input label (if any), the globally known parameters, and any port numbers required by the problem. A node can send messages to each neighbor and associate received messages with their incident edges even before knowing the neighbors’ identifiers. In a fault-free execution, one round of exchanging identifiers reveals every star. The following transformation shows that one additional round also suffices with crashes: it simulates an execution with initially known stars on a spanning subgraph whose omitted edges all have crashed endpoints. Transformation. Let A be an algorithm that assumes initially known stars. In one preliminary round, each node sends its identifier to every neighbor. Each node v that completes this round constructs the star σ bv = (v, Lv ∪ {v}), where Lv is the set of neighbors whose identifiers it received, retaining any associated local port numbers. It then starts A with this star, its original input label, and the unchanged global parameters, and adopts its output. The round counter is reset: round r of A is executed in physical round r + 1. Throughout this simulation, A treats Lv as the neighbor set of v: it uses degree |Lv | and sends messages only to neighbors in Lv . Let C be the set of nodes that crash before completing the preliminary round. These crashes count toward the overall bound f . A node of C may fail to send its identifier to some neighbors, so the constructed stars can omit edges incident to C. The following lemma shows that, after the preliminary round, the transformed algorithm simulates A on a spanning subgraph of G that retains every edge with both endpoints outside C. Lemma 1 (One-round star initialization). For every deterministic algorithm A with initially known stars and every execution on G, the transformation simulates an execution of A on a labeled spanning subgraph G′ ⊆ G with G′ [V \ C] = G[V \ C], in the same crash model and with the same crashed nodes. Thus, if A tolerates up to f crashes and terminates within T rounds on every labeled spanning subgraph of G, the transformation inherits its output guarantees on G′ within T + 1 rounds, with at most f crashes and unchanged global parameters. 15

Proof. Let A := V \ C, and let G′ be the labeled graph on the full node set V , with the original identifiers and input labels, whose edges are those reported in the constructed stars: [ G′ = (V, E ′ ), E ′ := {{u, v} : u ∈ Lv }. v∈A

Every reported edge belongs to G, and both endpoints of an edge in G[A] receive each other’s identifiers. Hence G′ ⊆ G and G′ [A] = G[A]. Consider the execution of A on G′ in which all nodes of C crash before initialization and, for each r ≥ 1, the crashes and crash-round delivery choices of physical round r + 1 are copied to round r. This execution has the same crashed nodes as the transformation and respects the same crash model. We show by induction on r ≥ 0 that, after r simulated rounds, every node that has not yet crashed has the same A-state in both executions, including any output already produced. For the base case r = 0, the nodes that have not crashed are exactly those of A. Fix v ∈ A. Every u ∈ Lv contributes the edge {u, v} to E ′ , so Lv ⊆ NG′ (v). Conversely, an edge {u, v} ∈ E ′ is reported either by v, in which case u ∈ Lv , or by u ∈ A. In the latter case, both endpoints complete the preliminary round and exchange their identifiers, so again u ∈ Lv . Hence, NG′ (v) = Lv , and the constructed star of v is exactly its initial star in G′ . The identifiers, input labels, and global parameters also agree, so v starts A in the same state in both executions. For the induction step, let r ≥ 1 and assume that the claim holds after r − 1 simulated rounds. Every node v that has not crashed before round r, including one that crashes during the round, starts the round in the same A-state in both executions. Since A is deterministic and v uses the same neighbor set Lv in both executions, it prescribes the same messages for round r. Nodes that crashed earlier send nothing. The copied crash-round delivery choices give the same partial deliveries in the standard model, while nodes crashing atomically in that round send nothing in either execution. Thus, every node completing the round receives the same messages and makes the same state update. Consequently, surviving nodes produce identical outputs. If A terminates within T rounds, the transformation produces these outputs within T + 1 physical rounds. Correctness on the original graph. By Lemma 1, the transformation produces the same surviving outputs as A on G′ . Assuming that A is correct on G′ , it remains to show that these outputs also satisfy the requirements on G. We therefore verify that restoring the omitted edges incident to C preserves correctness for ΠCN (R) and for locally checkable problems under Definition 1. For ΠCN (R), a view in G′ is still a labeled subgraph of G, and its radius remains valid because distG ≤ distG′ . Every edge between surviving nodes is retained, and consistency depends only on the unchanged views. If no node crashes, then C = ∅ and G′ = G, so fault-free completeness is preserved. For a locally checkable problem with checking radius ℓ, fix a surviving node v with BG (v, ℓ)∩F = ∅. Every node in this ball belongs to A, and G′ [A] = G[A]. Thus, every edge within the ball and every shortest path from v to a node in the ball is retained in G′ . Since deleting edges cannot shorten distances, we obtain that G′ [BG′ (v, ℓ)] = G[BG (v, ℓ)] as labeled graphs. This common checking neighborhood contains no crashed node, so correctness on G′ implies that its input and output labels satisfy the original local constraint at v. The same constraint therefore holds in G. All other surviving nodes are locally satisfied by definition. In the following sections, exact round complexities are computed under the assumption that the stars are initially known to nodes. For ΠCN (R) and locally checkable problems under Definition 1, this convention changes the complexity by at most one round, provided that the algorithm’s guarantees hold on every labeled spanning subgraph of the input graph. 16

4

The Consistent Neighborhoods Problem

This section formally defines the consistent neighborhoods problem ΠCN (R) and proves Theorem 1. Section 4.1 shows that, without crashes, ΠCN (R) can be solved in R rounds and that this is optimal, proving part (i). Afterwards, Section 4.2 focuses on part (ii) and shows that ΠCN (R) with R ≥ T + ℓ + 1 enables surviving nodes to simulate a deterministic fault-free T -round algorithm for a locally checkable problem with checking radius ℓ without further communication. Finally, in Section 4.3, we show that views of radius T + ℓ do not suffice in general, even for T = ℓ = 1, and we note that the simulation only guarantees the original local constraints of the problem at surviving nodes whose checking neighborhoods contain no crash. Without crashes, every node can learn its complete radius-R neighborhood within R rounds by forwarding labeled stars. Crashes disrupt this approach: (a) the views may omit nodes or edges of the complete radius-R neighborhoods, and (b) two adjacent surviving nodes may end up with conflicting views. Before presenting the formal definition of ΠCN (R), we discuss the properties it requires in order to address these issues. To address issue (a), ΠCN (R) permits incomplete views when crashes occur but specifies what each view may and must contain. On the one hand, views stay local: ΠCN (R) provides surviving nodes with radius-R views, where a radius-R view centered at v is a labeled subgraph H of G such that v ∈ V (H) and V (H) ⊆ BG (v, R). Here, distances are measured in the communication graph G, not in the view H. This keeps views local with respect to G, while allowing a view to include a node w even if crashes cut the shortest paths from v to w. On the other hand, ΠCN (R) limits how incomplete views can be: adjacent surviving nodes must include their common edge in their views (Edge Validity), and, when no node crashes, every view must be the complete radius-R neighborhood (Fault-Free Completeness). To address issue (b), ΠCN (R) requires the views of adjacent surviving nodes to induce identical labeled subgraphs on their respective comparison sets (Consistency). The comparison sets are defined for an edge {u, v} at the fixed view radius R. Definition 2 (Comparison sets for {u, v}). Let Hu and Hv be labeled graphs that both contain the edge {u, v}. For the fixed integer radius R ≥ 1, define Su (v) := BHu (u, R − 1) ∪ BHu (v, R − 1), Sv (u) := BHv (u, R − 1) ∪ BHv (v, R − 1). Thus, Su (v) and Sv (u) contain the nodes within distance R − 1 of either endpoint, measured in Hu and Hv , respectively. The dependence on the fixed radius R is suppressed in the notation. Putting these requirements together, we formally define ΠCN (R) as follows. Definition 3 (Consistent Neighborhoods Problem). For a communication graph G = (V, E), an integer R ≥ 1, and a crash bound f , an algorithm solves ΠCN (R) on G if every execution on G with at most f crashes satisfies the following properties. • Termination and radius. Every surviving node v outputs a radius-R view Hv centered at v, with the center labeled by v’s own identifier. • Edge validity. If u and v are adjacent surviving nodes, then both Hu and Hv contain the edge {u, v}. • Consistency. If u and v are adjacent surviving nodes, then, using the comparison sets from Definition 2, Hu [Su (v)] = Hv [Sv (u)] as labeled graphs. 17

• Fault-free completeness. If no node crashes, then every node v outputs its complete radius-R neighborhood Hv = G[BG (v, R)]. An algorithm solves ΠCN (R) on a graph class if it satisfies these requirements on every graph in the class. We highlight that the consistency property of Definition 3 is deliberately local to a surviving edge. We do not require all surviving nodes to output the same graph, and we do not require nodes in distinct connected components of the final surviving graph to agree. As we show in Section 4.2, this local agreement already suffices for simulating algorithms for locally checkable problems. We will show in Lemma 5 that the first three properties imply that, for every surviving node v and integer 0 ≤ ℓ < R, the labeled induced radius-ℓ neighborhood of v in its view coincides with that in G whenever no node in BG (v, ℓ) crashes during the execution, i.e., BG (v, ℓ) ∩ F = ∅. We also note that, in fault-free executions, the first three properties of Definition 3 already come close to fault-free completeness: they force each view Hv to contain all nodes of BG (v, R) and every edge with an endpoint at distance less than R from v (this follows from Lemma 4). However, they do not force the presence of edges between two nodes at distance exactly R from v. For example, on a triangle with R = 1, every node can output just its own star. These views satisfy radius, edge validity, and consistency, but each omits the edge between its two neighbors and is therefore not complete. Fault-free completeness rules out such omissions when no node crashes, ensuring that the primitive recovers ordinary collection of complete induced radius-R neighborhoods.

4.1

Consistent Neighborhoods without Crashes

We verify that Definition 3 matches the fault-free approach described at the beginning of this section: without crashes, flooding labeled stars for R rounds solves ΠCN (R). This is also optimal in general. Fault-free completeness requires each view to contain the edges between nodes at distance exactly R. Since information travels only one hop per round, learning these edges requires R rounds in the worst case. The following lemma establishes both bounds and proves part (i) of Theorem 1. Lemma 2 (Fault-free consistent neighborhoods). For every integer R ≥ 1, ΠCN (R) can be solved deterministically in R rounds without crashes. In the worst case, R rounds are necessary even on graphs with 2R + 1 nodes and maximum degree at most two. Proof. For the upper bound, every node starts with its star, together with its input label (if any), and, in each of R rounds, sends to its neighbors all stars it knows, each with the input label of its source. Afterwards, the roots of the stars collected by a node v, including its own initial star, form exactly BG (v, R). These stars reveal every edge between their roots, including edges whose two endpoints are at distance exactly R from v. Node v retains only these roots and the reported edges between them, discarding any nodes at distance R + 1 mentioned in stars rooted at distance R. Node v then outputs Hv = G[BG (v, R)]. These views satisfy all properties of Definition 3. Termination and radius, edge validity, and fault-free completeness hold by construction. For consistency, consider two adjacent nodes u and v. Every path of length at most R − 1 from u or v stays within distance R of both endpoints, and hence lies in both Hu and Hv . Therefore, both comparison sets equal S := BG (u, R − 1) ∪ BG (v, R − 1), and since both views are induced subgraphs of G, we obtain Hu [S] = G[S] = Hv [S]. For the lower bound, let P be a path on 2R + 1 nodes with middle node v and endpoints a and b, and let C be the cycle obtained from P by adding the edge {a, b}. We assign the same identifiers and input labels to the nodes of both graphs and, if used, the same local port numbers to their common edges. Fix a deterministic algorithm for ΠCN (R) that terminates within T < R rounds without 18

crashes, and let EP and EC denote its fault-free executions on P and on C, respectively, both with global bounds n = 2R + 1 and ∆ = 2. In these executions, only a and b have different initial states, and both are at distance R from v in both graphs. Since information about an initially different state can traverse at most one edge per round, induction on the number of rounds shows that the state of v is identical in EP and EC through round R − 1, and hence v obtains the same output in both. However, by fault-free completeness, v must output Hv = P in EP and Hv = C in EC , and these outputs differ in the edge {a, b}. Hence, no deterministic algorithm can always solve ΠCN (R) in fewer than R fault-free rounds.

4.2

Local Simulation from Consistent Neighborhoods

Consider a locally checkable problem Π, and let A be a deterministic T -round algorithm for Π in the fault-free setting. We now describe how a solution to ΠCN (R) enables us to transform A into a crashtolerant algorithm for Π. Here, a solution to ΠCN (R) on G consists of views Hv of the surviving nodes of an execution on G that satisfy the properties of Definition 3. The transformation is as follows: every surviving node v simulates the algorithm on its view Hv (treating its view as the entire graph) and adopts its simulated output. We present the pseudocode in Algorithm 1. Afterwards, Lemma 3 shows that, for sufficiently large R, the resulting outputs make every surviving node locally satisfied. Algorithm 1 Crash-Tolerant Transformation of A at Node v Parameters: problem Π with checking radius ℓ, deterministic algorithm A, round bound T , global bounds n, ∆, and view radius R. Preconditions: A solves Π within T rounds on every subgraph of G; R ≥ T + ℓ + 1. Input: labeled view Hv of v in a solution to ΠCN (R) on G. Output: output label of v for Π. 1: Initialize each node of Hv with its identifier, its input label (if any), and its neighbor identifiers in Hv . If ports are used, preserve their inherited names without renumbering. 2: Simulate T rounds of A on Hv with these initial states and the global bounds n and ∆. 3: Return the output assigned to v in the simulated execution of A. Lemma 3 (Local simulation from consistent neighborhoods). Let Π be a locally checkable problem with checking radius ℓ ≥ 1, and let A be a deterministic algorithm that solves Π within T rounds on every subgraph of G in the fault-free setting, where T ≥ 0. Given a solution to ΠCN (R) on G with R ≥ T + ℓ + 1, each surviving node can compute its output with no further communication so that every surviving node is locally satisfied for Π. We require A to remain correct within T rounds on every subgraph of G because the views may omit nodes and edges of G. This assumption holds, for example, if A solves Π within T rounds on every graph with at most n nodes and maximum degree at most ∆. Every subgraph of G satisfies these bounds. In each simulation, we retain the inherited node labels and use the original bounds n and ∆, as specified in Section 3. The checking radius ℓ and the local checking rule are also kept unchanged. In contrast, algorithms that rely on properties lost under taking subgraphs, such as connectivity, need not satisfy this assumption. The proof of Lemma 3 builds on the following fact: since A is correct on every subgraph of G, simulating it on a view Hv produces a valid solution on Hv . A surviving node whose checking neighborhood contains a crashed node is locally satisfied by definition (Definition 1). It therefore remains to verify the original constraints at surviving nodes whose checking neighborhoods do not contain any crashed nodes. To establish local satisfaction at such a node, it suffices to show that 19

its actual checking neighborhood, including the output labels, coincides with the corresponding neighborhood in the simulation on Hv . We establish this correspondence in two steps. First, we show that the checking neighborhood of v in Hv coincides with its checking neighborhood in G. Second, we show that each node u in this neighborhood computes from its own view Hu the same output that the simulation on Hv assigns to u. Both steps use the propagation of consistency along surviving paths (Lemma 4); the second also uses the locality of T -round algorithms. We first formalize how consistency propagates along surviving paths. Consistency only constrains neighboring views, but together with edge validity it extends along surviving paths: if v and w are joined by a surviving path of length d ≤ R, then w ∈ V (Hv ), and Hv agrees with Hw within radius R − d of w. We prove this in Lemma 4, using the following observation about induced subgraphs. Observation 1 (Matching neighborhoods in equal induced subgraphs). Let H and H ′ be labeled graphs with H[X] = H ′ [X ′ ] for some node sets X and X ′ . Let r ≥ 0, and consider a node v ∈ X. If BH (v, r) ⊆ X and BH ′ (v, r) ⊆ X ′ , then H[BH (v, r)] = H ′ [BH ′ (v, r)]. Lemma 4 (Propagation of consistent views). Let p0 , p1 , . . . , pd be a path of surviving nodes of length d ≤ R. Suppose that the views Hv of the surviving nodes v satisfy the termination   and radius, edge validity, and consistency requirements of ΠCN (R). Then, pd ∈ V (Hp0 ) and Hp0 BHp0 (pd , R − d) =   Hpd BHpd (pd , R − d) as labeled graphs, with distances measured in the respective views. Proof. We argue by induction on d. For d = 0, the claim follows because Hp0 contains its center p0 and the two sides of the claimed equality coincide. Let 1 ≤ d ≤ R and assume that the claim holds for paths of length d − 1. Set X := BHp0 (pd−1 , R − d + 1) and X ′ := BHpd−1 (pd−1 , R − d + 1). By the induction hypothesis, we know that pd−1 ∈ V (Hp0 ) and Hp0 [X] = Hpd−1 [X ′ ]. Edge validity places the edge {pd−1 , pd } in Hpd−1 . Since R − d + 1 ≥ 1, both endpoints belong to X ′ , so the edge belongs to Hpd−1 [X ′ ] and, by the induction hypothesis, also to Hp0 [X]. In particular, pd ∈ V (Hp0 ). Since both views contain this edge, pd−1 is at distance at most 1 from pd in both of these views. The triangle inequality implies that BHp0 (pd , R − d) ⊆ X and BHpd−1 (pd , R − d) ⊆ X ′ . Applying Observation 1, we obtain the following: Hp0 [BHp0 (pd , R − d)] = Hpd−1 [BHpd−1 (pd , R − d)]. Next, consider the comparison sets Y := Spd−1 (pd ) and Y ′ := Spd (pd−1 ). Edge validity ensures that both endpoint views contain {pd−1 , pd }, so these sets are defined, and consistency gives Hpd−1 [Y ] = Hpd [Y ′ ]. Since R − d ≤ R − 1, the radius-(R − d) balls around pd in these two views lie in Y and Y ′ , respectively. Applying Observation 1 again yields: Hpd−1 [BHpd−1 (pd , R − d)] = Hpd [BHpd (pd , R − d)]. Combining the two neighborhood equalities completes the induction. We now show that, for every surviving node v and integer 0 ≤ ℓ < R, the labeled induced radius-ℓ neighborhoods of v in Hv and G coincide if no node in BG (v, ℓ) crashes. Lemma 5 (Exact checking neighborhoods). Let v be a surviving node, and suppose that the views Hu of all surviving nodes u satisfy the termination and radius, edge validity, and consistency requirements of ΠCN (R). Let 0 ≤ ℓ < R be an integer. If BG (v, ℓ) ∩ F = ∅, then Hv [BHv (v, ℓ)] = G[BG (v, ℓ)] as labeled graphs. 20

Proof. We show that each of the two graphs is a labeled subgraph of the other. We first show that Hv [BHv (v, ℓ)] is a labeled subgraph of G[BG (v, ℓ)]. By termination and radius, Hv is a labeled subgraph of G, which implies that every edge of Hv is an edge of G, and distances in Hv are at least those in G. Hence BHv (v, ℓ) ⊆ BG (v, ℓ) and Hv [BHv (v, ℓ)] is a labeled subgraph of G[BG (v, ℓ)]. For the reverse inclusion, fix a ∈ BG (v, ℓ) and choose a shortest v–a path of length d = distG (v, a) ≤ ℓ. This path lies entirely in BG (v, ℓ), so all its nodes survive. By Lemma 4, a ∈ V (Hv ), and the labeled induced radius-(R − d) neighborhoods of a in Hv and Ha coincide. For every edge {a, b} of G[BG (v, ℓ)], both endpoints survive, so edge validity places it in Ha . Since R−d ≥ R−ℓ ≥ 1, this edge also belongs to Hv . Thus Hv contains every node and every edge of G[BG (v, ℓ)]. It remains to verify that these nodes lie within distance ℓ of v in Hv . The shortest paths considered above lie entirely in G[BG (v, ℓ)] and are therefore retained in Hv . Hence every a ∈ BG (v, ℓ) satisfies distHv (v, a) ≤ distG (v, a) ≤ ℓ. Together with the edge inclusion and the inherited labels, this proves that G[BG (v, ℓ)] is a labeled subgraph of Hv [BHv (v, ℓ)]. Having established equality of the checking neighborhoods, it remains to compare their output labels. For every surviving node v whose checking neighborhood contains no crashed node, we show that each u ∈ BG (v, ℓ) computes from its own view Hu the same output that the simulation of A on Hv assigns to u. We use the following locality property: if two labeled graphs have identical induced radius-(T + 1) neighborhoods around a node u, then the fault-free T -round executions of A on these graphs, with the same global parameters, assign the same output to u. Indeed, these neighborhoods determine the initial states of all nodes within distance T of u, and information propagates by at most one edge per round. We will apply this fact to Hv and Hu , centered at u, after using propagation of consistency to establish the required neighborhood equality. This is where the condition R ≥ T + ℓ + 1 comes from: a node u in the checking neighborhood of v is at most ℓ hops away, so Hv and Hu agree within distance R − ℓ ≥ T + 1 of u, which suffices to determine its output. Section 4.3 shows that this bound cannot be improved in general. Lemma 6 (Matching simulated outputs). Let A be a deterministic T -round algorithm, and suppose that all simulations use the same global bounds n and ∆. Suppose that the views Hv of the surviving nodes v satisfy the termination and radius, edge validity, and consistency requirements of ΠCN (R). Consider two surviving nodes u and v that are joined by a path of surviving nodes of length d ≤ R − (T + 1). Then, the output of u in the simulation of A on Hv equals the output of u in the simulation of A on Hu . Proof. By Lemma 4, applied to the path from v to u, we have u ∈ V (Hv ) and Hv [BHv (u, R − d)] = Hu [BHu (u, R − d)]. Since T + 1 ≤ R − d, the balls of radius T + 1 around u are contained in the balls of radius R − d around u, in both views. Applying Observation 1 with these balls of radius R − d as X and X ′ gives Hv [BHv (u, T + 1)] = Hu [BHu (u, T + 1)]. Finally, by the locality property above, both simulations assign u the same output. We now combine these lemmas to prove Lemma 3, and afterwards we prove Theorem 1. Proof of Lemma 3. We verify that Algorithm 1, applied to the given solution to ΠCN (R), has the claimed properties. By termination and radius, every surviving node v obtains a view Hv that is a labeled subgraph of G. Since A solves Π within T rounds on every subgraph of G, its fault-free simulation on Hv produces an output for v. This simulation is performed locally and requires no communication. It remains to argue that every surviving node is locally satisfied. This holds by definition for surviving nodes with a crashed node in their checking neighborhood, so fix a surviving node v with 21

BG (v, ℓ) ∩ F = ∅. Since A is correct on Hv , the simulated outputs satisfy the local constraints of Π at v in Hv , with the same checking rule and radius ℓ as in G. It therefore suffices to show that the checking neighborhood Hv [BHv (v, ℓ)], together with the simulated outputs, coincides with the checking neighborhood G[BG (v, ℓ)], together with the actual outputs. Since ℓ < T +ℓ+1 ≤ R, Lemma 5 gives Hv [BHv (v, ℓ)] = G[BG (v, ℓ)] as labeled graphs. Moreover, every u ∈ BG (v, ℓ) is joined to v by a shortest path of length d ≤ ℓ ≤ R − (T + 1) whose nodes all survive, so by Lemma 6, the output that u computes from Hu equals its output in the simulation on Hv . Consequently, v is locally satisfied. Proof of Theorem 1. Part (i) follows from Lemma 2, and part (ii) from Lemma 3. Both results use the initial-knowledge and global-bound conventions of Section 3.

4.3

Limits of Local Simulation

We conclude the section by discussing two limits of simulating algorithms on consistent neighborhoods as in Lemma 3. First, the following lemma shows that the additional hop in the radius requirement R ≥ T + ℓ + 1 is necessary in general: views of radius T + ℓ need not suffice, even when T = ℓ = 1. Lemma 7 (Radius-two views do not suffice). There exists a locally checkable problem with checking radius ℓ = 1 that is solvable in one fault-free round on every graph. Consider a deterministic rule that computes each surviving node’s output using only its view and initial local information. For this problem, no such rule guarantees local satisfaction at every surviving node for every family of views satisfying ΠCN (2). Proof. We define a locally checkable problem, construct views satisfying ΠCN (2) in an execution with crashes, and show that every rule that is correct without crashes violates the check at a node with no nearby crash. For this auxiliary problem, we explicitly treat node identifiers as problem inputs, retaining the initial-knowledge convention of Section 3.3. Consider the locally checkable problem in which each node u outputs a table indexed by NG [u], consisting of u and its direct neighbors, where the entry for a node w is its labeled star σw . The radius-one check at u requires that its table be indexed by exactly NG [u], that its entry for itself is its actual star, and that all tables output by nodes in NG [u] agree on every entry they share. In particular, this check compares the tables of two distinct neighbors of u, even when their common entry describes a node outside NG [u]. Without crashes, one round solves this problem on any graph: each node sends its star to its neighbors and builds its table from its own star and the received ones. Conversely, in every valid fault-free solution, an entry describing a neighbor w must agree with w’s own entry, which is checked against w’s actual star. Hence, every entry must be the actual star of the node it names. We now construct the counterexample. Let G+ be the four-cycle v–a–x–b–v with an additional node y joined only to x, and let G− be obtained from G+ by deleting the edge {x, y} while retaining y as an isolated node. Suppose that x and y crash in G+ , leaving v, a, b as the surviving nodes, and consider the views Ha = G+ and Hv = Hb = G+ [{v, a, b, x}]. These views satisfy ΠCN (2). Every included node is within two hops of its view’s center, and both surviving edges, {v, a} and {v, b}, appear in their endpoint views. Consistency uses radius one around the endpoints of each surviving edge. For either edge, both comparison graphs are the four-cycle on {v, a, b, x}, and the node y lies outside the comparison sets. Thus, a’s view may include y and {x, y} while b’s view omits them. However, no deterministic rule can produce valid outputs from these views. The view Ha = G+ is exactly a’s complete radius-two neighborhood in a fault-free execution on G+ , and the four-cycle Hb is 22

exactly b’s complete radius-two neighborhood in a fault-free execution on G− . The initial neighbor list is {v, x} at both nodes, all retained nodes have the same identifiers and input labels, and both graphs can use the same global bounds n = 5 and ∆ = 3. Hence, a rule that is correct without crashes must give a and b their respective fault-free outputs: a’s entry for x lists the neighbors {a, b, y}, whereas b’s lists {a, b}. Since a and b are both neighbors of v, the check at v compares these entries and rejects, although BG+ (v, 1) = {v, a, b} contains no crashed node. Thus, v is not locally satisfied. Second, Lemma 3 only guarantees the local constraints at surviving nodes whose radius-ℓ checking neighborhood contains no crash. For particular problems, useful correctness conditions may also be achievable at surviving nodes whose checking neighborhoods contain crashes. Such stronger guarantees rely on arguments that use the constraints of the particular problem, and we give examples of such algorithms in Section 8.2.

5

Algorithms for Consistent Neighborhoods

We now turn to solving ΠCN (R) in the presence of crashes, proving all four bounds in Theorem 3. Without crashes, ΠCN (R) can be solved in R rounds by forwarding labeled stars, as shown in Lemma 2. With crashes, however, the main difficulty is issue (b) from Section 4: a node that crashes may deliver messages to some neighbors but not to others, so adjacent surviving nodes may end up with conflicting views. We address this difficulty by using two standard information-propagation primitives: fullinformation gathering, which collects the local topology (Section 5.1), and flooding on fixed subgraphs, which ensures that, within each surviving component, either all nodes receive a message or none does (Section 5.2). We then use these primitives to solve ΠCN (R) in three settings. In Section 5.3, every node gathers information for n − 1 rounds, so that all nodes in a surviving component reconstruct the same graph; this proves part (i) of Theorem 3. In Section 5.4, we restrict the propagation of information to local regions, which yields bounds independent of n and proves parts (ii) and (iii), together with the case ∆ = 2 of part (iv). In Section 5.5, we show that R rounds of gathering suffice on graphs of girth greater than 2R, which proves the remaining case of part (iv). Finally, Section 5.6 combines these results and presents the proof of Theorem 3. We assume the standard crash-fault model described in Section 3. Our algorithms execute the primitives in consecutive phases, with round numbers measured from the beginning of each phase. Nodes that crashed in earlier phases remain inactive and count toward the overall crash bound f .

5.1

Full-Information Gathering

Fix an integer t ≥ 0. In the full-information gathering primitive, each node starts with its labeled star σv = (v, NG [v]), including its own input label (if any), and sends all stars it knows to all neighbors for t rounds. The pseudocode is presented in Algorithm 2. To analyze the information collected in Algorithm 2, we denote by A the set of nodes that complete the primitive without crashing: these nodes may crash in later phases. In addition, for every node v ∈ A, we define the set Qv := {x ∈ V : σx ∈ Kv }, which records the sources of the collected stars. The next lemma describes both the extent of Qv and the paths along which its stars reach v. Lemma 8 (Full-information gathering). Let t ≥ 0 be an integer, and consider an execution of Algorithm 2 for t rounds in the standard crash-fault model, with any number of nodes crashing before or during its execution. For every node v ∈ A, the following properties hold. 1. Coverage and locality. BG[A] (v, t) ⊆ Qv ⊆ BG (v, t). 23

Algorithm 2 Full-Information Gathering at Node v Input: labeled star σv and number of rounds t. Output: collection Kv of labeled stars. 1: Kv ← {σv } 2: for r = 1, . . . , t do 3: Send Kv to every neighbor in G. 4: Add all stars received in this round to Kv . 5: end for 6: return Kv . 2. Propagation paths. If v first learns σx in round r, where 0 ≤ r ≤ t, then there is a simple path x = p0 , p1 , . . . , pr = v such that pi first receives σx from pi−1 in round i for every 1 ≤ i ≤ r. Moreover, v collects the star σpi of every node on this path, so the entire path lies in G[Qv ]. In particular, distG[Qv ] (v, x) ≤ t for every x ∈ Qv . The first-reception path in item 2 also exists for every node that learns σx before crashing, even if it does not complete the primitive. Moreover, every v ∈ A can reconstruct G[Qv ] from its collected stars. In a fault-free execution, Qv = BG (v, t). Proof. We first prove the coverage and locality bounds. Let v ∈ A. Every node on a path in G[A] does not crash during the t rounds. Thus, for every x ∈ BG[A] (v, t), the star σx reaches v along such a path in at most t rounds. Therefore, BG[A] (v, t) ⊆ Qv . In addition, every node that first learns σx in round r is at distance at most r ≤ t from x in G, so Qv ⊆ BG (v, t). We now prove the propagation-path property. Let v be any node that first receives σx in round r ≥ 1, whether or not it completes the primitive. If a node first receives this star in round j > 1, its sender must have first received it in round j − 1. Otherwise, the sender would have sent the star earlier, before either node had crashed. In round 1, the star can only be sent by x. Following these senders backwards gives a path x = p0 , p1 , . . . , pr = v, where pi first receives σx in round i for every 1 ≤ i ≤ r. No node is repeated, since each node first learns the star only once. For v ∈ A, we next show that every node on this path belongs to Qv . For each i < r, node pi sends its own star together with σx . The star σpi then follows the remaining path and reaches v by round r. Since v also knows its own star, all nodes on the path belong to Qv . Therefore, distG[Qv ] (v, x) ≤ r ≤ t. The nodes on this path may crash after forwarding their stars. For x = v, the claim holds with r = 0 and the path consisting only of v. Finally, we show that v can reconstruct G[Qv ]. This follows because each collected star gives its source’s label and complete neighbor list. In a fault-free execution, A = V , and coverage and locality imply that Qv = BG (v, t).

5.2

Flooding on Fixed Subgraphs

We now describe the second information-propagation primitive, namely flooding on a fixed subgraph. While full-information gathering lets each node learn its surroundings, flooding on a fixed subgraph controls who receives a message: if a message spreads within a fixed subgraph H for sufficiently many rounds, then, in each surviving component of H, either all nodes receive it or none does. Fix a subgraph H ⊆ G and a set X ⊆ V (H) of nodes that initially hold a message m. Each node v ∈ V (H) stores a value mv , initially equal to m if v ∈ X and to ⊥ otherwise, where ⊥ denotes the absence of a message. We say that a node is informed once mv = m. In each round, every node that has not yet crashed and holds m at the start of the round sends it to all of its neighbors in 24

H. A node that first receives m in round r stores it and starts forwarding it in round r + 1 if it has not crashed. Nodes outside X learn m only through these transmissions. A finite flooding phase of T rounds consists of the first T rounds of this process. The pseudocode is given in Algorithm 3. Algorithm 3 Flooding a Message at Node v ∈ V (H) Input: neighbor set NH (v) and initial value mv ∈ {m, ⊥}. 1: for round r = 1, 2, . . . do 2: if mv ̸= ⊥ then 3: Send mv to every node in NH (v). 4: end if 5: if at least one copy of m is received in round r then 6: mv ← m. 7: end if 8: end for For the next two lemmas, we consider an execution in which flooding continues indefinitely. Let S be the set of nodes that survive the entire execution. We call each connected component of H[V (H) ∩ S] a surviving component. Since no node of such a component crashes, if one of them learns m, all of them eventually learn m. The next lemma bounds the number of rounds after which each surviving component is either entirely informed or entirely uninformed, using the lengths of simple paths in H starting at a node of X. Lemma 9 (Flooding and simple paths). Let L ≥ 0 be an integer such that every simple path in H starting at a node of X has length at most L. Then no node becomes informed about m after round L. Moreover, each surviving component is either entirely informed about m by the end of round L or remains entirely uninformed throughout the execution. In particular, if H is nonempty, flooding for |V (H)|−1 rounds guarantees that all nodes of each surviving component agree on whether they hold m. Proof. We first prove that no node becomes informed about m after round L. Every node in X is informed in round 0. Suppose v ∈ / X first learns m in round r > 0. By the same argument used in the proof of Lemma 8, its sender first learned m in round r − 1. Otherwise, the sender would already have sent m to v in round r − 1. Tracing first receptions backwards therefore gives a path of length r in H starting in X. The rounds in which its nodes first become informed strictly increase along the path, so it is simple and r ≤ L. We next prove the claim for surviving components. Let C be such a component. If no node of C ever holds m, then C remains entirely uninformed. Otherwise, flooding along paths in C, whose nodes never crash, eventually informs every node of C. The preceding bound shows that all of them are informed by the end of round L. Every simple path in a nonempty graph H has length at most |V (H)| − 1. Taking L = |V (H)| − 1 gives the claimed agreement within each surviving component. Lemma 9 guarantees agreement within every surviving component after |V (H)| − 1 rounds when H is nonempty. This bound can be large, but when a bound on the number of crashes is known, we obtain another bound. We next prove a bound for the same flooding process in terms of the maximum degree of H, the diameters of its connected components, and the number of crashes. These diameters are measured in H, before removing any crashed nodes. A small diameter D before crashes does not by itself bound the flooding time by D, since crashes may remove the paths witnessing that diameter. The proof below uses the at most ∆ · f surviving neighbors of crashed nodes to bound the resulting delay. 25

Lemma 10 (Flooding with few crashes). Let f ≥ 1. Suppose H has maximum degree at most ∆, every connected component of H has diameter at most D ≥ 1, and at most f nodes crash before or during the execution of Algorithm 3. Every surviving node v ∈ / X that ever learns m does so within O(D · ∆ · f ) rounds. Within the same bound, each surviving component is either entirely informed about m or remains entirely uninformed throughout the execution. Proof. Fix a surviving node v ∈ / X that first learns m in round r > 0. By the proof of Lemma 9, there is a simple path P = (p0 , . . . , pr = v) in H, where p0 ∈ X and pi first holds m in round i for 0 ≤ i ≤ r. Let C be the connected component of H containing P . If no node of C crashes, flooding along a shortest path from p0 to v gives r ≤ D. We now consider the case where C contains a crashed node. Let B be the set of surviving nodes of C adjacent to a crashed node. Since at most f nodes crash and each has degree at most ∆, we have |B| ≤ ∆f . For each surviving node x of C, choose a shortest path in C from x to a crashed node; its length is at most D. Let b be the node immediately before the first crashed node on this path. Then b ∈ B, and the path from x to b contains only surviving nodes and has length at most D. Assign x to one such b. We next bound the number of nodes of P assigned to each b ∈ B. If pi and pj , with i < j, are assigned to the same b, their assigned paths give a surviving walk of length at most 2D between them. Once pi holds m in round i, flooding along this walk informs pj by round i+2D. Thus j −i ≤ 2D. For any fixed b, the indices assigned to b therefore lie in an interval of length at most 2D, which contains at most 2D + 1 integers. Since P is simple, it also contains at most f crashed nodes. Consequently, r + 1 ≤ (2D + 1)|B| + f ≤ (2D + 1)∆f + f. Together with the case where no node of C crashes, and using f ≥ 1, this gives r = O(D · ∆ · f ). Finally, we prove the claim for surviving components. If no node of a surviving component ever holds m, then that component remains entirely uninformed. Otherwise, flooding along paths in the component eventually informs all of its nodes, since none of them crashes. Nodes in X are informed initially, and every other node is informed within the bound just proved. Hence the entire component is informed within O(D · ∆ · f ) rounds.

5.3

Consistent Neighborhoods in O(n) Rounds

We now prove part (i) of Theorem 3: we describe an O(n)-round algorithm for ΠCN (R) for every integer R ≥ 1. Each node runs full-information gathering (Algorithm 2) for n−1 rounds, reconstructs the labeled graph induced by the sources of its collected stars, and outputs its radius-R neighborhood in that graph. The algorithm uses only the initial labeled star and the known parameters n and R, and does not require a bound on the number of crashes. The pseudocode is given in Algorithm 4. Algorithm 4 Consistent Neighborhoods in n − 1 Rounds at Node v Input: labeled star σv , upper bound n ≥ |V |, and radius R ≥ 1. Output: radius-R view Hv centered at v. 1: Run Algorithm 2 for n − 1 rounds to obtain Kv . 2: Qv ← {x : σx ∈ Kv }. 3: Construct the labeled graph Jv ← G[Qv ] from Kv . 4: Hv ← Jv [BJv (v, R)]. 5: return Hv . Although step 3 of Algorithm 4 is phrased in terms of G, node v can carry it out locally: for each x ∈ Qv , the collected star σx gives the label of x and its complete neighbor list in G. Hence v knows all edges of G between nodes of Qv , and thus Jv = G[Qv ]. The computation of Hv is then local as well. 26

The main property of Algorithm 4 is that all nodes in the same connected component of the surviving graph reconstruct the same graph, which contains their entire component. Intuitively, gathering (Algorithm 2) floods every star on G for n − 1 rounds, which is long enough for each star to reach either all or none of the nodes of a surviving component. Consequently, adjacent surviving nodes compute their views in the same graph, which makes consistency straightforward. We make this argument formal in the lemma below, which states the guarantees of Algorithm 4. Lemma 11 (Linear-round consistent neighborhoods). Let G = (V, E) be a graph with at most n nodes, and let R ≥ 1 be an integer. Algorithm 4 deterministically solves ΠCN (R) in n − 1 rounds in the synchronous LOCAL model under standard crash faults, with any number of nodes crashing before or during its execution. Each node uses only its initial labeled star and the globally known parameters n and R; no bound on the number of crashes is required. Proof. Let A be the set of nodes that complete Algorithm 2 with t = n − 1, and fix a connected component C of G[A]. For the analysis, extend gathering indefinitely without further crashes; then A is exactly the set of surviving nodes in this extension. For each initial star σx , apply Lemma 9 with H = G, X = {x}, and L = n − 1. Either every node of C knows that star by the end of round n − 1, or none does. Thus all nodes of C finish with the same collection K, source set Q, and reconstructed graph J = G[Q]. By Lemma 8, C ⊆ Q, so G[C] ⊆ J ⊆ G. For v ∈ C, the output Hv = J[BJ (v, R)] contains its root and all incident surviving edges. As J ⊆ G, it is a radius-R view in G. For adjacent nodes u, v ∈ C, the edge {u, v} belongs to J, so every path in J of length at most R − 1 from either endpoint lies in both radius-R balls. Consequently, their comparison sets satisfy: Su (v) = Sv (u) = BJ (u, R − 1) ∪ BJ (v, R − 1). Both outputs induce J on this set, proving consistency. If no node crashes, Lemma 8 gives Qv = BG (v, n − 1). Since G has at most n nodes, this ball contains exactly the nodes of the connected component of G containing v. Hence Jv is that component’s complete labeled graph, and each output is G[BG (v, R)]. Finally, gathering runs for n − 1 rounds and is followed only by local computation, establishing termination and the claimed round complexity. Remark 1 (Relation to local consensus). Our (n − 1)-round algorithm uses the same flooding principle as the elementary local-consensus algorithm of Fraigniaud, Nguyen, and Paz [FNP25, full version, Lemma 24]. Local consensus requires the nodes in each surviving component to agree on an initial proposal. Their algorithm floods identifier–proposal pairs for n − 1 rounds, so nodes in the same surviving component obtain the same collection and select the same proposal. Our algorithm floods labeled stars and uses the common collection to reconstruct a graph, from which each node extracts its radius-R view.

5.4

Consistent Neighborhoods with Parameter-Dependent Bounds

We now prove parts (ii) and (iii) of Theorem 3, together with the ∆ = 2 case of part (iv). The linear-round algorithm behind part (i) makes all nodes in each surviving component reconstruct the same graph. To obtain bounds independent of n, we instead restrict the propagation of each source’s information to a local region, while preserving the agreement required between adjacent output views. For every R ≥ 1, our algorithm has two phases. In Phase I (full-information gathering), each node runs Algorithm 2 for R rounds. As in Section 5.1, let A denote the nodes that complete this phase. Each v ∈ A obtains a collection of stars Kv with source set Qv . These collections and source sets remain fixed throughout Phase II. 27

In Phase II (restricted flooding), each node v ∈ A maintains a set of tokens Wv , initially Wv = {v}. In each of T rounds, it sends Wv to every neighbor and retains a received token x only if x ∈ Qv , meaning that it collected σx in Phase I. Stored tokens are kept and forwarded in subsequent rounds. We choose T later using Lemmas 9 and 10. Even if v collected σx in Phase I, it does not start Phase II with token x unless x = v. It must receive that token during Phase II before adding it to Wv . Since only nodes that complete Phase I start with their own tokens, every identifier in Wv belongs to A. At the end of Phase II, node v outputs Hv := G[Wv ]. Since Wv ⊆ Qv , the stars collected in Phase I give the label and complete neighbor list of every node in Wv , so v can reconstruct this labeled induced subgraph locally. Phase II therefore needs to transmit only identifiers. The pseudocode is given in Algorithm 5. Algorithm 5 Consistent Neighborhoods with Restricted Propagation at Node v Input: labeled star σv , radius R ≥ 1, and number of propagation rounds T ≥ 1. Output: radius-R view Hv centered at v. 1: Phase I: full-information gathering 2: Run Algorithm 2 for R rounds to obtain Kv . 3: Qv ← {x : σx ∈ Kv }; Wv ← {v}. 4: Phase II: restricted propagation 5: for r = 1, . . . , T do 6: Send Wv to every neighbor in G. 7: Add to Wv all identifiers received in this round that belong to Qv . 8: end for 9: Construct the labeled graph Hv ← G[Wv ] from the stars in Kv . 10: return Hv . Propagation graphs. We now turn to the analysis of Phase II. Recall that A is the set of nodes that complete Phase I. Only these nodes start Phase II with their own tokens, so Wv ⊆ A for every node that completes Phase II. For each x ∈ A, let Vx consist of x and all nodes that receive σx during Phase I. Note that Vx may include nodes that crash before Phase I ends or during Phase II. By the coverage and locality properties proven in Lemma 8, we obtain BG[A] (x, R) ⊆ Vx ⊆ BG (x, R).

(1)

The right inclusion implies that every node that stores token x is within distance R of x, since it stores the token only if it collected σx in Phase I. The left inclusion will be used to establish the consistency requirement of Definition 3. More precisely, if an edge of G[A] has an endpoint within distance R − 1 of x in G[A], then both endpoints belong to Vx . We now define the fixed subgraph along which token x spreads.4 For each x ∈ A, the propagation graph Γx = (Vx , Ex ) has node set Vx as defined above and edge set Ex := {{a, b} ∈ E : a, b ∈ Vx }. Equivalently, Γx = G[Vx ]. This graph remains unchanged throughout Phase II; nodes are retained even if they crash before or during this phase. For every v ∈ A, we have v ∈ Vx if and only if x ∈ Qv , so a node can determine locally whether to retain token x. Thus every copy of token x received along an edge of Γx is stored, while copies received outside Vx are discarded. Token x therefore spreads by flooding on Γx , with x as its only initial holder. We will show that, if Phase II runs for sufficiently many rounds, the surviving endpoints of every edge of Γx either both store token x or neither does. 4

The use of propagation graphs in these upper bounds was suggested by LLMs; see Section 10.

28

The next lemma shows that token x spreads in Phase II exactly as it would under flooding on Γx . It also bounds the size and diameter of each propagation graph. Lemma 12 (Flooding on propagation graphs). Fix an execution of Algorithm 5 with R ≥ 1, and let x ∈ A. The following properties hold. (i) Consider Algorithm 3 on Γx for T rounds, with token x initially held only by x. Nodes that crashed before Phase II remain inactive, and every other node has the same crash round, if any, as in Phase II. In a crash round, a flooding message is delivered to precisely those neighbors in Γx that receive the sender’s Phase II transmission. At the end of each round, every node in Vx that has not crashed stores token x in Phase II if and only if it is informed in this flooding execution. Only nodes in Vx can store token x during Phase II. (ii) The graph Γx , including nodes that crash before or during Phase II, is a connected subgraph of G, has maximum ∆, and satisfies diam(Γx ) ≤ 2R. Moreover, Vx ⊆ BG (x, R) P degree at most i for ∆ ≥ 3, while for ∆ = 2, we have |V | ≤ 2R + 1. and |Vx | ≤ 1 + ∆ R−1 (∆ − 1) x i=0 Proof. Initially only x holds token x, and x ∈ Vx . During Phase II, every node v that has not yet crashed stores a received copy of token x exactly when x ∈ Qv , or equivalently, when v ∈ Vx . Every subsequent holder is therefore in Vx . Each node holding the token at the start of a round sends it to every neighbor in Γx , and every copy received along these edges is stored. Copies received at nodes u∈ / Vx are discarded since x ∈ / Qu . The initial holders, forwarding rule, crash rounds, and delivery choices along Γx thus agree with the flooding execution in (i). Induction on the rounds of Phase II gives the same holders among nodes that have not crashed by the end of each round. Nodes that crashed before Phase II remain inactive and count toward any crash bound. This concludes the proof of (i). We next prove (ii). Since Γx ⊆ G, its maximum degree P is at mosti ∆. By (1), Vx ⊆ BG (x, R). Counting nodes by distance from x gives |Vx | ≤ 1 + ∆ R−1 i=0 (∆ − 1) for ∆ ≥ 3, while for ∆ = 2 the same count gives |Vx | ≤ 2R + 1. For every w ∈ Vx , Lemma 8 gives a first-reception path of length at most R from x to w, even if w crashes before Phase I ends. Every node on this path held σx during Phase I and hence belongs to Vx . Since Γx is induced, the entire path lies in Γx . Thus distΓx (x, w) ≤ R for every w ∈ Vx , so Γx is connected and diam(Γx ) ≤ 2R. For R ≥ 1, we set the number T of propagation rounds for parts (ii), (iii), and the ∆ = 2 case of part (iv) of Theorem 3 to the following values, respectively:  R−1 X   ∆ (∆ − 1)i ∆ ≥ 3, any number of crashes,   i=0 T = (2)  c · ∆ · R · f a globally known upper bound f ≥ 1 on crashes,     2R ∆ = 2, any number of crashes. Here c is a sufficiently large positive integer constant. When a crash bound f is assumed known, it bounds the total number of crashes, including those before Phase II. The following lemma shows that, for every x ∈ A, these choices suffice for all nodes in each surviving component of Γx to agree on whether they store token x at the end of Phase II. Lemma 13 (Agreement on stored tokens). Let R ≥ 1, choose T as in (2), and let S ⊆ A be the set of nodes that complete Algorithm 5. For every x ∈ A and every connected component of Γx [S ∩ Vx ], either all its nodes store token x at the end of Phase II, or none of them does. In particular, the endpoints of every surviving edge of Γx agree on whether they store token x. 29

Proof. Fix x ∈ A. By Lemma 12(i), the nodes storing token x in Phase II are exactly those informed by flooding on Γx , with x as the only initial holder and the same crashes and message deliveries. For the analysis, continue this flooding execution beyond round T without further crashes. This leaves the first T rounds unchanged, and its surviving nodes are precisely S ∩ Vx . For the two choices of T that do not require a crash bound, Lemma 12(ii) gives |Vx | − 1 ≤ T . By Lemma 9, for each connected component of Γx [S ∩ Vx ], either all its nodes store token x at the end of round T , or none of them does. For the choice of T using the known crash bound f , Lemma 12(ii) shows that Γx is connected, has maximum degree at most ∆, and has diameter at most 2R. The upper bound f also counts nodes that crashed before Phase II. Applying Lemma 10 with D = 2R shows that, for each connected component of Γx [S ∩ Vx ], either all its nodes store token x within O(∆ · R · f ) rounds, or none of them ever holds it. Choosing c sufficiently large makes this number of rounds at most T . In every case, the endpoints of a surviving edge of Γx lie in the same connected component of Γx [S ∩ Vx ] and therefore agree on whether they store token x. We next verify the radius and edge-validity requirements of Definition 3 for the graphs reconstructed from the stored tokens and collected stars. Lemma 14 (Radius and edge validity). Let R ≥ 1, and consider an execution of Algorithm 5. If a node v outputs Hv , then Hv is a labeled induced subgraph of G and a radius-R view centered at v. If two adjacent nodes u and v both output, then both Hu and Hv contain the edge {u, v}. Proof. The output is Hv = G[Wv ], and v ∈ Wv because v stores its own token. Since Wv ⊆ Qv , the labels, including the root’s identifier, are inherited from the stars collected in Phase I. For every x ∈ Wv , Lemma 12 gives v ∈ Vx ⊆ BG (x, R), so x ∈ BG (v, R). Thus v ∈ V (Hv ) ⊆ BG (v, R), as required for a radius-R view centered at v. Let u and v be adjacent nodes that both output. In the first round of Phase I, they exchange their own stars, so u ∈ Qv and v ∈ Qu . Each endpoint therefore stores the other endpoint’s token in the first round of Phase II. Both output views contain u and v. Since they are induced subgraphs of G, they also contain the edge {u, v}. We now use Lemma 13 to prove that the output views agree on the comparison subgraphs around every surviving edge. Lemma 15 (Consistency). Let R ≥ 1, choose T as in (2), and consider an execution of Algorithm 5. If two adjacent nodes u and v both output, then Hu [Su (v)] = Hv [Sv (u)] as labeled graphs, where Su (v) and Sv (u) are the comparison sets from Definition 2, computed in Hu and Hv , respectively. Proof. Fix adjacent nodes u and v that both output. By Lemma 14, this edge belongs to both Hu and Hv . Let P be a path in Hu of length at most R − 1 starting at an endpoint a ∈ {u, v}. Since Wu ⊆ A, we have Hu ⊆ G[A]. Thus every node x of P satisfies distG[A] (x, a) ≤ R − 1. The other endpoint of {u, v} also belongs to A and is at distance at most R from x in G[A]. By (1), both u and v belong to Vx , so their edge belongs to the induced graph Γx . Since u stores token x, Lemma 13 implies that v also stores token x. Hence every node of P belongs to Wv . Since Hv = G[Wv ], the entire path P occurs in Hv . Every path defining membership in Su (v) therefore also occurs in Hv , which proves Su (v) ⊆ Sv (u). Interchanging u and v gives equality. Both comparison graphs are the labeled subgraph of G induced by this common set, so Hu [Su (v)] = Hv [Sv (u)]. When no node crashes, the exact gathering sets from Lemma 8 yield fault-free completeness. 30

Lemma 16 (Fault-free completeness). For R ≥ 1 and T chosen as in (2), if no node crashes in Algorithm 5, then every node v outputs Hv = G[BG (v, R)]. Proof. If no node crashes, Lemma 8 gives Qv = BG (v, R) for every v ∈ V . Hence Vx = BG (x, R) for every x ∈ V . By Lemma 12(ii), Γx is connected. Since x stores its own token, Lemma 13 implies that every node of Γx stores token x by the end of Phase II. By Lemma 12(i), no node outside Vx can store token x. Thus v stores token x exactly when v ∈ BG (x, R), equivalently when x ∈ BG (v, R). Therefore Wv = BG (v, R) and Hv = G[BG (v, R)]. We finish checking the requirements of Definition 3 by verifying termination. Lemma 17 (Termination). For every R ≥ 1 and T ≥ 1, every surviving node in Algorithm 5 produces its output at the end of round R + T . Proof. Phase I executes Algorithm 2 for R rounds, and Phase II consists of exactly T rounds. Constructing Hv from the stored tokens and collected stars requires only local computation. Every surviving node therefore outputs Hv at the end of round R + T . Substituting the three choices of T from (2) into Lemma 17 gives the following round complexities. Lemma 18 (Round complexity). For R ≥ 1 and T chosen as in (2), the round complexity of Algorithm 5 is O((∆ − 1)R ), O(∆ · R · f ), or 3R = O(R) for the three choices of T , respectively. Proof. By Lemma 17, the algorithm uses R + T rounds. For the choice with ∆ ≥ 3 and no assumed crash bound, we have T = ∆((∆ − 1)R − 1)/(∆ − 2) ≤ 3(∆ − 1)R . Since R ≤ 2R−1 ≤ (∆ − 1)R , the algorithm uses O((∆ − 1)R ) rounds in total. For the choice using the known crash bound f , R + T = R + c · ∆ · R · f = O(∆ · R · f ). For the choice with ∆ = 2 and no assumed crash bound, R + T = 3R = O(R).

5.5

Consistent Neighborhoods on Graphs of Large Girth

We now prove the large-girth case of Theorem 3(iv). Here a simple gathering algorithm suffices. On graphs of girth greater than 2R, run Algorithm 2 for R rounds. Using Qv as defined in Section 5.1, each surviving node v reconstructs and outputs Hv := G[Qv ]. This is well-defined because v knows the labeled star of every included node. Lemma 19 (Consistent neighborhoods on graphs of large girth). Let R ≥ 1 be an integer, and let G have girth greater than 2R. Run Algorithm 2 for R rounds, and let every surviving node v output Hv = G[Qv ], where Qv is the set of sources of its collected stars. This algorithm solves ΠCN (R) deterministically in R rounds in the synchronous LOCAL model under standard crash faults, for any number of crashes. Proof. The algorithm runs for R rounds and then reconstructs Hv locally. By Lemma 8 with t = R, we have v ∈ Qv ⊆ BG (v, R), so each output is a labeled radius-R view centered at v. Adjacent surviving nodes exchange their own stars in the first round, so both views contain their common edge. Without crashes, Qv = BG (v, R) and hence Hv = G[BG (v, R)]. It remains to prove consistency. The girth condition implies that there is at most one simple path of length at most R between any two nodes: two distinct such paths would contain a cycle of length at most 2R. Fix a surviving edge {u, v} and x ∈ Su (v). Choose a simple path P in Hu from x to one of u, v, of length at most R − 1. Since x ∈ Qu , Lemma 8 gives a simple first-reception path of length at 31

most R along which σx reached u in successive rounds. If u lies on P , then σx reaches u along the x–u subpath of P , by uniqueness. Thus u knows σx by round R − 1 and sends it to v by round R. Otherwise, P ends at v, and appending {u, v} gives a simple x–u path of length at most R. By uniqueness, this is the first-reception path, so v knows σx by round R − 1. In both cases, x ∈ Qv . The preceding argument shows that Su (v) ⊆ Qv . Thus every node of P belongs to Qv . Since Hv = G[Qv ], the same path occurs in Hv , giving x ∈ Sv (u). Thus Su (v) ⊆ Sv (u), and symmetry gives equality. Both views induce the same labeled subgraph of G on this set, proving consistency. Remark 2 (The strict girth condition). For R ≥ 2, the R-round gathering algorithm of Lemma 19 can fail on a graph of girth 2R, even when ∆ = 2. The following example establishes this limitation of the gathering algorithm; it does not establish a lower bound for arbitrary algorithms for ΠCN (R). Let G be the cycle with nodes p0 , . . . , p2R−1 in cyclic order. Let x = p0 crash in round 1, sending σx only to p1 , while every other node survives. The star σx first reaches u = pR in round R, whereas v = pR+1 has not received it by that round. All other stars reach both nodes by round R, so the outputs are Hu = G and Hv = G[V \{x}]. Since distHu (v, x) = R −1 and x ∈ / V (Hv ), we have x ∈ Su (v)\Sv (u), violating the consistency requirement of Definition 3 across the surviving edge {u, v}.

5.6

Putting It All Together

We now combine the results of this section to prove Theorem 3. Proof of Theorem 3. Part (i) follows from Lemma 11, which establishes that Algorithm 4 solves ΠCN (R) in n − 1 = O(n) rounds for every R ≥ 1 and any number of crashes. For every R ≥ 1, choose T from (2) under the degree and crash assumptions of the chosen case. By Lemmas 14 to 17, Algorithm 5 satisfies all requirements of Definition 3. Applying Lemma 18 for the three choices of T in (2) gives part (ii), part (iii), and the ∆ = 2 case of part (iv), respectively. The large-girth case of part (iv) follows from Lemma 19, which solves ΠCN (R) in R rounds for every R ≥ 1 on graphs of girth greater than 2R, under any number of crashes. Forests have infinite girth and are therefore included.

6

Lower Bounds for Consistent Neighborhoods

In this section, we prove the lower bounds of Theorem 2. All lower bounds use one common construction principle, which builds on the path-versus-cycle argument behind the fault-free lower bound in Lemma 2. We describe this principle in Section 6.1. We then instantiate it to obtain the linear lower bound with one or two crashes in Section 6.2, the exponential lower bound in the radius in Section 6.3, and the lower bound depending on the crash bound and the radius in Section 6.4. Finally, we combine these lower bounds into a proof of Theorem 2 in Section 6.5.

6.1

Common Indistinguishability Framework

We assume that a deterministic algorithm A solves ΠCN (R) within T rounds on two graphs G− and G+ , which we define below, with the same globally known bounds n, ∆, and f . The structure of the two graphs will enable us to reach a contradiction. We may assume that every surviving node outputs at the end of round T : a node that computes its output earlier can retain it and report it at the end of round T , while preserving its original communication behavior.

32

Common structure of G− and G+ . Each of our lower bounds uses its own pair of graphs G− and G+ . As in the lower-bound proof of Lemma 2, the two graphs differ only in the edge joining the endpoints of a path: this edge is present in G+ and absent in G− . Both graphs have the same node set V , partitioned into three sets C, F , and S, with no edges between C and S, as illustrated in Figure 1. More generally, we say that a labeled graph respects a partition (C, F, S) of its node set if it has no edges between C and S; in particular, G+ and G− respect (C, F, S). We formulate some of the definitions and lemmas below in this more general setting so that they can also be used in Section 7.2. The induced graph G− [S] is a path with endpoints a and b, and G+ is obtained from G− by adding the edge {a, b}. Both graphs use the same identifiers and input labels on V . If port numbers are used, each common edge has the same local port number at each endpoint in both graphs, and the closing edge is assigned unused port numbers at a and b. Hence, the nodes’ initial states in the two graphs differ only at a and b, whose initial stars reveal the extra edge. The nodes of F are the only nodes that may crash. The nodes of C and S always survive. The actual crash set F(E) ⊆ F depends on the execution. In the original graph, C ∪ F provides short routes between distant nodes of S, so that every node of S is within distance R − 1 of every node of the graph. Once all nodes of F crash, these shortcuts disappear. For each lower bound, we specify the structure of C ∪ F and how the nodes of F attach to S in Sections 6.2 to 6.4. There, we make the path G− [S] as long as possible under each setting’s constraints, as its length determines how large a round complexity T we can rule out. Proof plan. We note that, in a fault-free execution of A on G+ , fault-free completeness forces every node of S to output the whole graph, since every node of S is within distance R − 1 of every node of the graph. In particular, these outputs include the closing edge {a, b}. In contrast, by the termination and radius requirement, every surviving node’s output in an execution on G− must be a labeled subgraph of G− , which cannot contain {a, b}. We also make the following observation: if all nodes of F crash before sending any message, S is cut off from the rest of the graph and forms a long path or cycle. Then, nodes of S that are far from a and b cannot tell within T rounds whether they are in G+ or in G− . Together, these observations allow us to show that some node of S outputs G+ even in an execution on G− , which contradicts that A solves ΠCN (R). To this end, we define a chain of similar executions, in which each pair of consecutive executions is indistinguishable at some node of S. We gradually move the crashes of the nodes of F earlier, until they crash before sending any message, and use consistency to show that every node of S keeps outputting G+ . Finally, we switch from G+ to G− : a node of S far from a and b still outputs G+ , although G+ is not a subgraph of G− . Indistinguishable executions and similarity chains. To make this plan precise, we first formally define when a node cannot tell two executions apart. For t ∈ {0, . . . , T }, the view of a node v at the end of round t consists of the initial state of v and, for every round t′ ∈ {1, . . . , t} and every neighbor u of v, the message that v receives from u in round t′ , or ⊥ if no message is received. Here, a view records the local history of a node: it is distinct from the output graph Hv required by ΠCN (R). We say that two executions are indistinguishable at v up to round t if v has the same view at the end of round t in both. Since A is deterministic, a node that survives in both executions and has the same view through round T produces the same output in both. If A is correct, every node of S produces different outputs in the fault-free execution on G+ and in the final execution on G− , so these executions cannot be indistinguishable up to round T at any node of S. We therefore connect them through a chain in which consecutive executions are indistinguishable at some node of S. Such chains are a standard tool for crash-fault lower bounds, most prominently for consensus [LF82, Lyn96]. We formalize them for our setting as follows. 33

Definition 4 (Similarity chain). A similarity chain for a T -round algorithm A is a finite sequence E0 , . . . , EK of executions of A, each on a labeled graph respecting (C, F, S), satisfying the following: • (Admissibility) in every Ei , at most f nodes crash, and all of them lie in F , so every node of C ∪ S survives; • (Indistinguishability) for every i < K, there is a node wi ∈ S at which Ei and Ei+1 are indistinguishable up to round T . Such a node is called a witness of the step from Ei to Ei+1 . Returning to our plan, our similarity chain starts with the fault-free execution E0 on G+ and ends with an execution EK on G− , with all intermediate executions on G+ . The following lemma shows that such a chain forces A to violate the requirements of ΠCN (R) in at least one execution, provided that every node of S has sufficiently small eccentricity. Lemma 20 (From similarity chains to lower bounds). Assume that every node of S has eccentricity at most R − 1 in G+ . In addition, let E0 , . . . , EK be a similarity chain for A such that E0 is the fault-free execution on G+ , the executions E1 , . . . , EK−1 run on G+ , and EK runs on G− . Then, A does not satisfy the requirements of ΠCN (R) in at least one execution of this chain. To prove Lemma 20, we carry the complete output G+ from E0 along the assumed similarity chain, using the result below. Lemma 21 (Propagation of a complete view). Let G be a graph, and let S ⊆ V (G) be a set of nodes such that G[S] is connected and every node of S has eccentricity at most R − 1 in G. Suppose that the outputs Hv of the surviving nodes v, including all nodes of S, satisfy the termination and radius, edge validity, and consistency requirements of ΠCN (R). If some node p ∈ S outputs Hp = G, then every node of S outputs G. Proof. If S = {p}, there is nothing to prove. Otherwise, since G[S] is connected, node p has at least one neighbor in S. We show that every neighbor q ∈ S of p also outputs Hq = G. As p and q are adjacent surviving nodes, edge validity ensures that both Hp and Hq contain the edge {p, q}. Consistency therefore gives Hp [Sp (q)] = Hq [Sq (p)]. Since Hp = G and p has eccentricity at most R − 1 in G, we have BHp (p, R − 1) = V (G), and hence Sp (q) = V (G) and Hp [Sp (q)] = G. Thus, Hq [Sq (p)] = G, so Hq contains every node and edge of G. By termination and radius, Hq is a labeled subgraph of G, so Hq = G. Thus, every neighbor in S of a node that outputs G also outputs G. Since G[S] is connected, applying this argument along paths from p shows that every node of S outputs G. We may now present the proof of Lemma 20. Proof of Lemma 20. Suppose, for a contradiction, that A satisfies the requirements of ΠCN (R) in every execution of the chain. We first note how Lemma 21 applies to the executions on G+ . Every node of S survives, G+ [S] is connected, and every node of S has eccentricity at most R − 1 in G+ . Thus, if one node of S outputs G+ in such an execution, then every node of S outputs G+ . We now show by induction that every node of S outputs G+ in each execution E0 , . . . , EK−1 . In E0 , fault-free completeness requires each node of S to output its complete radius-R neighborhood. By the eccentricity assumption, this neighborhood is all of G+ . For the induction step, suppose that every node of S outputs G+ in Ei , where i < K − 1. The witness wi cannot distinguish Ei from Ei+1 , so it also outputs G+ in Ei+1 . Since Ei+1 runs on G+ , the propagation argument above implies that every node of S outputs G+ in Ei+1 . 34

Finally, the witness wK−1 outputs G+ in EK−1 and cannot distinguish this execution from EK . It therefore also outputs G+ in EK . However, EK runs on G− , so termination and radius require this output to be a labeled subgraph of G− . This is impossible because {a, b} belongs to G+ but not to G− . Constructing our similarity chains. Lemma 20 reduces each lower bound of Theorem 2 to constructing a suitable similarity chain from the fault-free execution on G+ to an execution on G− . We do so first for a single standard crash (Lemma 23) and then for atomic crashes (Lemma 25). In both crash models, each step of the chain changes the messages of a single crashing node or, in the last step, the initial states of a and b. We find a witness for each step by bounding how far such a change can spread. For two executions E and E ′ in which every node of C ∪ S survives, and for t ∈ {0, . . . , T }, let Dt ⊆ C ∪ S be the set of nodes whose local histories through round t differ. Then, D0 consists of the nodes in C ∪ S with different initial states, and every node of S \ DT is a witness. The following lemma shows that, once the nodes of F stop sending messages, differences spread only inside G[S], by at most one hop per round. Lemma 22 (Spreading of differences). Let E and E ′ be executions of A on labeled graphs respecting (C, F, S), in which all nodes of C ∪ S survive, and let G be a graph that contains the graphs of both executions as subgraphs. Let 0 ≤ t0 ≤ T , and suppose that no node of F sends a message in any round t ∈ {t0 + 1, . . . , T } in either execution. Then, DT ∩ S ⊆ BG[S] (Dt0 ∩ S, T − t0 ). Proof. We show by induction on t that Dt ∩ S ⊆ BG[S] (Dt0 ∩ S, t − t0 ) for every t ∈ {t0 , . . . , T }. The lemma then follows by setting t = T . The base case t = t0 is immediate. For the induction step, let t ∈ {t0 + 1, . . . , T } and assume that the claim holds for t−1. It will suffice to show that a difference can spread by at most one hop in round t, i.e., that Dt ∩ S ⊆ BG[S] (Dt−1 ∩ S, 1). Together with the induction hypothesis and the triangle
inequality, this implies our claim: Dt ∩S ⊆ BG[S] BG[S] (Dt0 ∩S, t−1−t0 ), 1 ⊆ BG[S] (Dt0 ∩S, t−t0 ). To prove the one-hop inclusion, fix a node v ∈ S with v ∈ / BG[S] (Dt−1 ∩ S, 1). We show that v∈ / Dt . Since v ∈ / Dt−1 , its local histories through round t − 1 coincide in the two executions. In particular, its initial star is identical in both. This star specifies all neighbors of v, so v has the same neighbors in both executions. In round t, v receives messages only from its neighbors in S: the nodes of F send nothing in round t, and there are no edges between C and S. Let u be such a neighbor. Since {u, v} is an edge of G[S] and v is not within distance one of Dt−1 ∩ S, we have u ∈ / Dt−1 , so u has the same view at the end of round t − 1 in both executions. Moreover, u survives, and since A is deterministic, its round-t message to v is determined by this view. Hence, v receives the same messages in round t in both executions, and therefore has the same view at the end of round t. Consequently, v ∈ / Dt . We next compare executions on G+ and G− in which no node of F sends any message. Since the graphs differ only in the closing edge {a, b}, we have D0 = {a, b}. Applying Lemma 22 with G = G+ and t0 = 0 gives the following corollary, which we will use to justify the final step of each similarity chain. Corollary 1 (Switching the graph). Let E be an execution of A on G+ and E ′ an execution of A on G− , such that all nodes of C ∪ S survive in both and no node of F sends any message in either execution. Then, DT ∩ S ⊆ BG+ [S] ({a, b}, T ). One standard crash. We now construct a similarity chain with F = {z}, allowing only z to crash in the standard model. Starting from the fault-free execution on G+ , we aim to reach an execution in which z sends no messages. We can then apply Corollary 1 for the final switch to G− . In the 35

standard crash model, z’s crash-round messages may be delivered to any subset of its neighbors. We therefore compare executions in which z crashes in the same round, but one additional neighbor does not receive its message from z. Lemma 23 (One standard crash). Consider a pair G− , G+ with the partition and path/cycle structure specified earlier, where F = {z}, and let T ≥ 0. Assume that every node of S has eccentricity at most R − 1 in G+ , and that the following hold: (a) for every w ∈ NG+ (z) ∩ S, there is a node p ∈ S such that distG+ [S] (p, w) ≥ T ;
(b) there is a node q ∈ S such that distG+ [S] q, {a, b} > T . Then, no deterministic T -round algorithm solves ΠCN (R) on both graphs while tolerating one standard crash. For T = 0, condition (b) gives a node q ∈ S \ {a, b} with the same initial state in both graphs. The two fault-free executions therefore form a similarity chain with witness q, and Lemma 20 rules out such an algorithm. We henceforth assume T ≥ 1. As displayed in Figure 2, for T ≥ 1, our chain here first lets z crash in round T while still sending all its messages. It then removes these messages one at a time. Once z sends nothing in round T , it behaves exactly as if it had crashed in round T − 1 while sending all its messages, and the chain continues with round T − 1, and so on, until z crashes in round 1 without sending any message. Finally, it switches from G+ to G− . Since z ∈ / {a, b} and the graphs G+ and G− differ only in the edge {a, b}, the neighbors of z are the same in both graphs. We write N (z) := NG+ (z) = NG− (z). For the fixed deterministic algorithm A, specifying the graph and the crash behavior of z determines the execution. We describe this behavior by a standard crash schedule: either ⊥, indicating that z does not crash, or a pair (r, M ), where r ∈ {1, . . . , T } is its crash round and M ⊆ N (z). Under schedule (r, M ), node z follows A before round r. In round r, its prescribed messages to neighbors in M are delivered, while those to other neighbors are not. Node z remains inactive thereafter. For G ∈ {G+ , G− }, we write E(G, ⊥) for the fault-free execution on G and E(G, r, M ) for the execution with crash schedule (r, M ). In each case, every node other than z survives and follows A. To describe the schedules of our chain, we denote the d := |N (z)| neighbors of z by w1 , . . . , wd , in the order in which their messages are removed, and let Mj := N (z) \ {w1 , . . . , wj } for j ∈ {0, . . . , d}, so that M0 = N (z) and Md = ∅. Our chain consists of the following executions, in this order: E(G+ , ⊥), E(G+ , T, M0 ), . . . , E(G+ , T, Md ), E(G+ , T − 1, M0 ), . . . , E(G+ , 1, Md ), E(G− , 1, Md ). Apart from the last step, which switches from G+ to G− , the chain has two kinds of steps: silent step and drop step. In a silent step, from E(G+ , ⊥) to E(G+ , T, M0 ), or from E(G+ , r + 1, Md ) to E(G+ , r, M0 ) for some r < T , the node z sends exactly the same messages in both executions: all of them in the first case, and all of them through round r and none afterwards in the second. Hence, every node other than z has the same view in both executions. In a drop step, from E(G+ , r, Mj−1 ) to E(G+ , r, Mj ) for some r ∈ {1, . . . , T } and j ∈ {1, . . . , d}, only the round-r message of z to wj is removed, so only nodes of S close to wj can notice the step, as described by the lemma below. Lemma 24 (Dropping one message). Let r ∈ {1, . . . , T } and j ∈ {1, . . . , d}, and consider the two
executions E = E(G+ , r, Mj−1 ) and E ′ = E(G+ , r, Mj ). Then, DT ∩ S ⊆ BG+ [S] {wj } ∩ S, T − r . Proof. In both executions, z is the only node that crashes, and it does so in round r. Hence, the two executions coincide through round r − 1, i.e., Dr−1 = ∅. In round r, they differ only in the message from z to wj , so Dr ⊆ {wj }. Since z sends no message after round r in either
execution, Lemma 22 with t0 = r gives DT ∩ S ⊆ BG+ [S] (Dr ∩ S, T − r) ⊆ BG+ [S] {wj } ∩ S, T − r . 36

|S| = 8 surviving nodes, z

R = 3 (diameter 2 ≤ R − 1),

T = ⌊(|S| − 1)/2⌋ − 1 = 2,

wj = p9−j

round 2

round 2

round 2

round 2

z

z

z

z

···

+

G

E1 = E(G+ , 2, M0 ) crashes in round T = 2, all delivered (silent step)

E0 fault-free

E2 = E(G+ , 2, M1 ) p8 dropped

E3 = E(G+ , 2, M2 ) p8 , p7 dropped

E9 = E(G+ , 2, M8 ) nothing delivered

silent step: z sends the same messages in E9 and E10 , so every node of S is a witness round 1

round 1

round 1

round 1

round 1

z

z

z

z

z

···

+

G

E10 = E(G+ , 1, M0 ) crashes in round 1, all delivered

E11 = E(G+ , 1, M1 ) p8 dropped

E12 = E(G+ , 1, M2 ) p8 , p7 dropped

E13 = E(G+ , 1, M3 ) p8 , p7 , p6 dropped

E18 = E(G+ , 1, M8 ) crashes before round 1 closing edge removed; p4 cannot tell round 1 z −

G

p1 p2 p3 p4 p5 p6 p7 p8 E19 = E(G− , 1, M8 ) same schedule on G−

Figure 2: The similarity chain of Lemma 23 for the one-standard-crash construction with |S| = 8 surviving nodes, so T = ⌊(|S| − 1)/2⌋ − 1 = 2, and radius R = 3: both graphs have diameter 2 ≤ R − 1, so every fault-free output is the whole graph. A dark z crashes in the indicated round; a dotted spoke is a message of that round that is not delivered. Every execution has at most one crash. A ring marks a witness, at which the execution is indistinguishable from the previous one. We are now ready to prove the lower bound for standard crashes. Proof of Lemma 23. Fix a deterministic T -round algorithm A, and consider the chain described above. Every execution in this chain has at most one standard crash, namely of z, so the chain is admissible. It remains to verify the indistinguishability property of Definition 4. Recall that a node of S outside DT is a witness, so for each step it suffices to find a node of S that cannot notice it. In a silent step, as shown above, z sends the same messages in both executions, so every node other than z has the same view in both. Hence, every node of S is a witness. Next, consider a drop step, from E(G+ , r, Mj−1 ) to E(G+ , r, Mj ). By Lemma 24, every node of DT ∩ S is within distance T − r < T of {wj } ∩ S in G+ [S]. If wj ∈ / S, then DT ∩ S = ∅, and every node of S is a witness. Otherwise, condition (a) provides a node p ∈ S at distance at least T from wj , so p ∈ / DT , and p is a witness. Finally, consider the last step, from E(G+ , 1, Md ) to E(G− , 1, Md ). Since Md = ∅, the node z sends no message in either execution. Hence, by Corollary 1, every node of DT ∩ S is within distance T of {a, b} in G+ [S]. Condition (b) provides a node q ∈ S at distance more than T from {a, b}, so q∈ / DT , and q is a witness. Consequently, the chain is a similarity chain satisfying the assumptions of Lemma 20, so A violates 37

the requirements of ΠCN (R) in at least one of its executions. Since each of these executions has at most one standard crash, A does not solve ΠCN (R) on both graphs while tolerating one standard crash. Atomic crashes. We now turn to atomic crashes, where F may contain several nodes. Since a node that crashes atomically sends either all or none of its messages in a round, consecutive executions now differ in the crash round of an entire node of F . Such a step changes the messages to all its neighbors at once, so condition (a) below asks for a node of S far from all of them. Lemma 25 (Atomic crashes). Consider a pair G− , G+ with the partition and path/cycle structure specified above, and let T ≥ 0. Assume that every node of S has eccentricity at most R − 1 in G+ , and that the following hold:
(a) for every x ∈ F , there is a node p ∈ S such that distG+ [S] p, NG+ (x) ∩ S ≥ T ;
(b) there is a node q ∈ S such that distG+ [S] q, {a, b} > T . Here the distance to an empty set is infinity. Then, for every globally known crash bound f ≥ |F |, no deterministic T -round algorithm solves ΠCN (R) on both graphs under atomic crashes. We first handle T = 0. Condition (b) gives a node q ∈ S \ {a, b}. Since the graphs differ only in the edge {a, b}, node q has the same initial state in both graphs. The two fault-free executions therefore form a similarity chain with witness q. By Lemma 20, no deterministic zero-round algorithm solves ΠCN (R) on both graphs. We henceforth assume T ≥ 1. As displayed in Figure 3, for T ≥ 1, our chain starts from the fault-free execution. Each successive execution makes one additional node of F crash at the beginning of round T , until all nodes of F crash in that round. We then move the crashes earlier, one node and one round at a time, until they all occur at the beginning of round 1. Finally, we switch from G+ to G− . An atomic crash schedule is a map c : F → {1, . . . , T } ∪ {∞}. If c(x) = r < ∞, node x follows A through round r − 1, crashes before sending any message in round r, and remains inactive thereafter. If c(x) = ∞, node x survives. We write c∞ for the schedule with no crashes. For a labeled graph G respecting (C, F, S), let E(G, c) denote the execution determined by A, G, and c. Every node of C ∪ S survives, so this execution has at most |F | atomic crashes, all in F . To describe the schedules of our chain, we denote the k := |F | nodes of F by x1 , . . . , xk . For r ∈ {1, . . . , T } and s ∈ {0, . . . , k}, we denote by cr,s the schedule in which x1 , . . . , xs crash at the beginning of round r, and xs+1 , . . . , xk crash at the beginning of round r + 1 if r < T , or not at all if r = T . That is, the index s marks the cut between the nodes that crash in round r and those that crash one round later:   if i ≤ s, r cr,s (xi ) := r + 1 if i > s and r < T,   ∞ if i > s and r = T. Our chain consists of the following executions, in this order: E(G+ , cT,0 ), E(G+ , cT,1 ), . . . , E(G+ , cT,k ), E(G+ , cT −1,1 ), . . . , E(G+ , c1,k ), E(G− , c1,k ), where cT,0 = c∞ . We omit cr−1,0 , since it equals cr,k : in both, all nodes of F crash at the beginning of round r. Hence, apart from the last step, which switches from G+ to G− , every step, from E(G+ , cr,s−1 ) to E(G+ , cr,s ) for some r ∈ {1, . . . , T } and s ∈ {1, . . . , k}, changes only the crash time of xs : from no crash to round T if r = T , and from round r + 1 to r otherwise. Only nodes of S close to the neighbors of xs can notice such a step, as described by the lemma below. The only restriction on the graph in the next lemma is that there are no edges between C and S; it does not require G[S] to be a path or cycle. We will reuse this generality in Section 7.2.3. 38

|S| = 8 surviving nodes,

R = 4 (diameter 3 ≤ R − 1), round 2

x1

x2

x1

x2

T = ⌊|S|/4⌋ = 2

round 2

round 2

round 1

round 2

round 1

round 1

x1

x2

x1

x2

x1

x2

+

G

E0 fault-free

E1 x1 crashes in round T = 2

E2 x2 crashes in round 2

E3 x1 moved to round 1

E4 x2 moved to round 1 closing edge removed; p4 cannot tell round 1

round 1

x1

x2

G− p1 p2 p3 p4 p5 p6 p7 p8 E5 same schedule on G−

Figure 3: The similarity chain of Lemma 25 for the two-atomic-crash construction with |S| = 8 surviving nodes, so T = ⌊|S|/4⌋ = 2, and radius R = 4: both graphs have diameter 3 ≤ R − 1, so every fault-free output is the whole graph. Here x1 is adjacent to p1 , . . . , p4 and x2 to p5 , . . . , p8 . Each panel is an execution: a dark node crashes atomically in the indicated round, a light one never crashes. A ring marks a witness, at which the execution is indistinguishable from the previous one. Lemma 26 (Moving one atomic crash). Let G be a labeled graph respecting (C, F, S), let r ∈ {1, . . . , T } and s ∈ {1, . . . , k}, and consider the
two executions E = E(G, cr,s−1 ) and E ′ = E(G, cr,s ). Then, DT ∩ S ⊆ BG[S] NG (xs ) ∩ S, T − r . Proof. The two executions run on the same labeled graph, and no node crashes before round r. Their states and messages therefore coincide through round r − 1, so Dr−1 = ∅. In round r, every node other than xs has the same state and crash behavior in both executions, so it sends the same messages in both or no messages in either. Node xs sends its prescribed messages in E but crashes before sending them in E ′ . Thus, only its neighbors can receive different messages, giving Dr ∩ S ⊆ NG (xs ) ∩ S. If r < T , every node of F crashes by the beginning of round r + 1 in both executions; if r = T , there are no remaining rounds. Hence, Lemma 22 applies with t0 = r and gives
DT ∩ S ⊆ BG[S] (Dr ∩ S, T − r) ⊆ BG[S] NG (xs ) ∩ S, T − r .

We are now ready to prove the lower bound for atomic crashes. Proof of Lemma 25. Fix a crash bound f ≥ |F | and a deterministic T -round algorithm A, and consider the chain described above. Every execution in this chain has at most |F | ≤ f atomic crashes, all of them in F , so the chain is admissible. It remains to verify the indistinguishability property of Definition 4. As in the proof of Lemma 23, it suffices to find, for each step, a node of S outside DT . First, consider a step from E(G+ , cr,s−1 ) to E(G+ , cr,s ). By Lemma 26, every node of DT ∩ S is within distance T − r < T of NG+ (xs ) ∩ S in G+ [S]. Condition (a) provides a node p ∈ S at distance at least T from NG+ (xs ) ∩ S, so p ∈ / DT , and p is a witness. 39

Finally, consider the last step, from E(G+ , c1,k ) to E(G− , c1,k ). Under c1,k , every node of F crashes at the beginning of round 1, so no node of F sends a message in either execution. Hence, by Corollary 1, every node of DT ∩ S is within distance T of {a, b} in G+ [S]. Condition (b) provides a node q ∈ S at distance more than T from {a, b}, so q ∈ / DT , and q is a witness. Consequently, the chain is a similarity chain satisfying the assumptions of Lemma 20, so A violates the requirements of ΠCN (R) in at least one of its executions. Since each of these executions has at most f atomic crashes, A does not solve ΠCN (R) on both graphs with crash bound f under atomic crashes.

6.2

Linear Time with One or Two Crashes

We now focus on Theorem 2(i), which concerns general graphs: a single standard crash can force every algorithm for ΠCN (R) to take Ω(n) rounds for every R ≥ 3, and under atomic crashes, two crashes suffice for every R ≥ 4. The following lemma states these bounds precisely. Lemma 27 (Linear lower bounds). The following statements hold for deterministic algorithms in the synchronous LOCAL model, with the globally known size bound n. (a) Let R ≥ 3 and n ≥ 9. Every algorithm that solves ΠCN (R) on all graphs with at most n nodes while tolerating one standard crash needs more than ⌊n/2⌋ − 2 rounds. (b) Let R ≥ 4, n ≥ 10, and f ≥ 2. Every algorithm that solves ΠCN (R) on all graphs with at most n nodes under at most f atomic crashes needs more than ⌊(n − 2)/4⌋ rounds. We prove both parts by instantiating the graphs G+ and G− of the framework of Section 6.1 with C = ∅, as illustrated in Figure 4. The set F consists of a single node in the standard crash model and of two nodes in the atomic crash model, which together are adjacent to all of S. Through F , every node of S is within constant distance of every other node, so the eccentricity condition of Lemmas 23 and 25 holds already for small R. Without F , however, S induces a path or cycle on almost all n nodes, in which distances are linear in n. Since conditions (a) and (b) of both lemmas only concern distances in G+ [S], they hold with T = Θ(n). One standard crash

Two atomic crashes

R≥3

R≥4

x1

z

x2

Figure 4: The linear lower bounds in Theorem 2(i). Red nodes form F , green nodes form S, and C is empty. Dashed closing edges occur only in G+ . The original graphs have diameter two on the left and three on the right, while removing F leaves a long path or cycle. The drawings show six surviving nodes; the constructions extend to arbitrarily many. One standard crash. Here, a single crashing node z serves as a shortcut between all nodes of S. Let C = ∅, F = {z}, and S = {p1 , . . . , pn−1 }, so that |S| = n − 1 ≥ 8. We join z to every node of S, and obtain G− by adding the path p1 , . . . , p|S| , and G+ by additionally adding the closing edge {a, b} := {p1 , p|S| }. We now show that these graphs satisfy the requirements of Lemma 23 with T = ⌊(|S| − 1)/2⌋ − 1. 40

Proof of Lemma 27(a). The construction has n nodes, and both graphs have diameter at most two, since any two nodes are joined through z. Hence, every node of S has eccentricity at most 2 ≤ R−1 in G+ . We apply Lemma 23 with T := ⌊(|S| − 1)/2⌋ − 1 = ⌊n/2⌋ − 2. For condition (a), every w ∈ S has a node at distance ⌊|S|/2⌋ ≥ T from it in the cycle G+ [S]. For condition (b), the endpoints p1 and p|S| are adjacent in this cycle, so some node has distance ⌊(|S| − 1)/2⌋ > T from both of them. Hence, by Lemma 23, no T -round algorithm tolerating one standard crash solves ΠCN (R) on both graphs. Two atomic crashes. Under atomic crashes, a single node adjacent to all of S does not satisfy condition (a) of Lemma 25, which requires, for every crashing node, a node of S far from all of its neighbors. We therefore split z into two adjacent nodes, each adjacent to one half of S. Let C = ∅, F = {x1 , x2 }, and S = {p1 , . . . , pn−2 }, so that |S| = n − 2 ≥ 8. We join x1 and x2 by an edge, join x1 to p1 , . . . , p⌊|S|/2⌋ , and join x2 to the remaining nodes of S. As before, we obtain G− by adding the path p1 , . . . , p|S| , and G+ by additionally adding the closing edge {a, b} := {p1 , p|S| }. The edge {x1 , x2 } keeps the threshold at R ≥ 4: replacing it by a path through an additional node in C would increase the diameter to four, and the eccentricity condition would then require R ≥ 5. We now show that these graphs satisfy the requirements of Lemma 25 with T = ⌊|S|/4⌋. Proof of Lemma 27(b). The construction has n nodes, and both graphs have diameter at most three, since any two nodes of S are joined through x1 , x2 , or both. Hence, every node of S has eccentricity at most 3 ≤ R − 1 in G+ . We apply Lemma 25 with T := ⌊|S|/4⌋ and crash bound f ≥ 2 = |F |. For condition (a), each set NG+ (xi ) ∩ S is a contiguous block of the cycle G+ [S], and the complementary block contains at least ⌊|S|/2⌋ nodes. Its middle node therefore has distance at least ⌈⌊|S|/2⌋/2⌉ ≥ T from NG+ (xi ) ∩ S. For condition (b), as before, some node has distance ⌊(|S| − 1)/2⌋ > T from p1 and p|S| . Hence, by Lemma 25, no T -round algorithm solves ΠCN (R) on both graphs with crash bound f under atomic crashes.

6.3

An Exponential Lower Bound in the Radius

We next focus on Theorem 2(ii), which concerns graphs of maximum degree at most ∆: on such graphs, any algorithm for ΠCN (R) may need a number of rounds exponential in R. We prove the bounds under atomic crashes whenever f ≥ 2. The additional case R = 4 and f = 1 uses the standard crash-fault model. The constructions in Section 6.2 use crashing nodes whose degrees grow linearly with n. We now seek lower bounds for graphs of maximum degree at most ∆, where ∆ may be fixed independently of n. The eccentricity condition requires every node of S to be within distance R − 1 of every node of the graph. For ∆ ≥ 3, the degree bound therefore limits the graph to O((∆ − 1)R ) nodes. Our goal is to make the cycle G+ [S] as long as possible subject to these degree and eccentricity constraints. We give two constructions satisfying the degree and eccentricity constraints. The first uses a tree whose leaves form S: the tree provides short paths between these nodes before crashes, while the leaves form a long cycle in G+ (Figure 5). This construction yields a lower bound of Ω((∆ − 1)⌊(R−1)/2⌋ ) rounds. To obtain a stronger bound, we use a graph of small diameter as a core. We insert crashing nodes into selected edges of the core and connect each of them to a distinct node of S (Figure 6). Choosing these edges far apart limits the increase in distances caused by the insertions. This allows a longer √ cycle while preserving the eccentricity condition, improving the exponent from ⌊(R−1)/2⌋ to R−O∆ ( R).

41

C

F S closing edge

Figure 5: The tree construction for the Ω((∆−1)h ) bound in Theorem 2(ii), illustrated with ∆ = 3 and h = 3. The blue nodes form C, the red nodes form F and are the only ones that may crash, and the 2h = 8 green leaves form S. The dashed closing edge is present only in G+ . Each node of F is adjacent to a consecutive block of ∆ − 1 nodes of S, which is short compared to the surviving path or cycle. 6.3.1

The tree construction

Lemma 28 (Tree bound). Let ∆ ≥ 3 and R ≥ 4, let h := ⌊(R − 1)/2⌋, and let n ≥ 4 · (∆ − 1)h and f ≥ (∆ − 1)h−1 . Every deterministic algorithm that solves ΠCN (R) on all graphs with at most n nodes and maximum degree at most ∆ under at most f standard crashes needs at least (∆ − 1)h /8 rounds. The same lower bound holds under atomic crashes if f ≥ 2. We start with a complete rooted (∆ − 1)-ary tree of height h. Let S be its leaves, let F be the parents of the leaves, and let C consist of all remaining nodes. For R ≥ 5, we have h ≥ 2, so F contains at least two nodes. We treat the case R = 4 separately below. As depicted in Figure 5, we obtain G− by adding an edge between every two consecutive leaves in left-to-right order, so that G− [S] is a path, and G+ by additionally adding the closing edge between the first and the last leaf. The root has degree ∆ − 1, every other internal node of the tree has degree ∆, and every leaf has degree at most three, so both G− and G+ have maximum degree at most ∆. The construction has |S| = (∆−1)h , |F | = (∆−1)h−1 , and, by the geometric-series formula, |V | = ((∆ − 1)h+1 − 1)/(∆ − 2) ≤ 2 · (∆ − 1)h nodes. Moreover, both graphs contain the original tree, in which any two nodes are joined by a path of length at most 2h ≤ R − 1. The additional edges cannot increase distances, so every node of S has eccentricity at most R − 1 in both G− and G+ . For R = 4, we have h = 1, and the tree is a single parent adjacent to all leaves, which does not suffice under atomic crashes, as discussed in Section 6.2. We therefore use the two-crash construction of Section 6.2 with |S| = 2(∆ − 1): we have F = {x1 , x2 }, C = ∅, and S = {p1 , . . . , p2(∆−1) }, where x1 is adjacent to p1 , . . . , p∆−1 and x2 to p∆ , . . . , p2(∆−1) . The nodes x1 and x2 have degree ∆, every node of S has degree at most three, and the construction has 2∆ nodes. Any two leaves are joined by a path of length at most three through x1 , x2 , or both, so every node of S has eccentricity at most 3 = R − 1 in G+ . In both atomic-crash constructions, every node of F has exactly ∆ − 1 neighbors in S, which form a consecutive block of the path G− [S], and |F | ≥ 2. We first verify the requirements of Lemma 25 for these graphs, then treat f = 1 in the standard crash-fault model. Proof of Lemma 28. First, suppose f ≥ 2, and consider the constructions above. We verify that G− and G+ satisfy the lemma statement’s requirements, i.e., that they have maximum degree at most ∆ and at most n nodes. The degree bound holds by construction. For the number of nodes, we have |V | ≤ 2 · (∆ − 1)h ≤ n if R ≥ 5, and |V | = 2∆ ≤ 4(∆ − 1) ≤ n if R = 4, by the assumption on n.

42

Next, we verify the assumptions of Lemma 25. The crash bound is sufficient because |F | = (∆ − 1)h−1 ≤ f if R ≥ 5, and |F | = 2 ≤ f if R = 4. Moreover, as shown above, every node of S has eccentricity at most R − 1 in G+ . Both constructions have |S| ≥ 4, so we can set T := ⌊|S|/4⌋ − 1 ≥ 0. We subtract one because condition (b) requires a distance strictly greater than T . For condition (a), the sets NG+ (x)∩S, for x ∈ F , partition S into consecutive blocks of size ∆−1. Since |F | ≥ 2, each block contains at most half the nodes of the cycle G+ [S]. Its complementary block therefore contains at least |S|/2 nodes, and a middle node of this complement is at distance at least ⌈|S|/4⌉ ≥ T from the original block in G+ [S]. Thus, condition (a) holds for every x ∈ F . For condition (b), consider the endpoints of the closing edge. In G+ [S], a middle node of the path G− [S] is at distance at least ⌊(|S| − 1)/2⌋ from both endpoints. This distance is at least ⌊|S|/4⌋ = T + 1 > T , as required. All assumptions of Lemma 25 now hold, so no deterministic T -round algorithm solves ΠCN (R) on both graphs under atomic crashes. Hence, the worst-case round complexity is at least T + 1 = ⌊|S|/4⌋ rounds. Since |S| ≥ 4, rounding |S|/4 down loses at most a factor of two. Together with |S| ≥ (∆−1)h , this gives ⌊|S|/4⌋ ≥ |S|/8 ≥ (∆ − 1)h /8. Atomic crashes are a special case of standard crashes, so this proves the bound in both models for f ≥ 2. It remains to consider f = 1. Since (∆ − 1)h−1 ≤ f and ∆ ≥ 3, we have h = 1, and hence R = 4. We use the construction for a single crash from Section 6.2 with |S| = ∆: the ∆ nodes of S form a path in G− and a cycle in G+ , and z is adjacent to every node of S. Here, C = ∅ and F = {z}. Both graphs have maximum degree at most ∆ and ∆ + 1 ≤ 4(∆ − 1) ≤ n nodes. Every node of S has eccentricity at most two in G+ , so the eccentricity condition holds for R = 4. Set T := ⌊(∆ − 1)/4⌋. For condition (a) of Lemma 23, every w ∈ NG+ (z) ∩ S has a node at distance ⌊∆/2⌋ ≥ T from it in the cycle G+ [S]. For condition (b), a middle node of the path G− [S] is at distance at least ⌊(∆ − 1)/2⌋ > T from each endpoint of the closing edge, since ∆ ≥ 3. Thus, Lemma 23 applies, including when T = 0. The worst-case round complexity is therefore at least T + 1 > (∆ − 1)/4 ≥ (∆ − 1)h /8 in the standard crash-fault model. This completes the proof. 6.3.2

The sparse-core construction

We now turn to the stronger bound. In the tree construction, S consists of the leaves of the tree itself, and this loses a factor of two in the exponent: we ensure the eccentricity condition by choosing the tree height so that 2h ≤ R − 1, so it has only |S| = (∆ − 1)h leaves with h = ⌊(R − 1)/2⌋. The following lemma shows that this factor can be avoided. Lemma 29 (Sparse-core bound). For every integer ∆ ≥ 3, there exists an integer R0 (∆) ≥ 4 such that for every R ≥ R0 (∆), every n ≥ (∆ − 1)R , and every f ≥ ⌈(∆ − 1)R /∆⌉, the following holds: every deterministic algorithm that solves ΠCN (R) on all graphs with at most n nodes and maximum √ R−3⌈ R⌉ degree at most ∆ under at most f atomic crashes needs at least (∆ − 1) rounds. To obtain a larger set S, we build our construction around a ∆-regular graph H of diameter at most D, which we call the core. By the following lemma, such a graph exists with N = Ω∆ ((∆ − 1)D /D) nodes. Lemma 30 (Small-diameter regular cores). For every fixed integer ∆ ≥ 3, there are constants c∆ > 0 and D0 (∆) such that, for every integer D ≥ D0 (∆), there is a simple ∆-regular graph H of diameter at most D with N nodes, where c∆ · (∆ − 1)D /D ≤ N ≤ (∆ − 1)D . Proof. We use the diameter theorem of Bollobás and Fernandez de la Vega [BFdlV82], taking ε = 1 in [Bol01, Theorem 10.14]. For fixed ∆ ≥ 3, this theorem implies that, for all sufficiently 43

Subdivide each selected edge: ei ∈ M ui

H is ∆-regular,

yi vi

ui

D = R − ℓ − 5,

diam(H) ≤ D √ ℓ = ⌈ R⌉

vi

subdivided core on C ∪ F Selected edges: pairwise distance ≥ ℓ in H

y1 u1

y2 v1

p1

u2

y3 v2

u3

v3

p2

p3

S: the surviving path closing edge, present only in G+ √

Figure 6: The sparse-core construction for the stronger (∆ − 1)R−3⌈ R⌉ bound in Theorem 2(ii). The inset shows how a selected edge ei = {ui , vi } of the ∆-regular core H is replaced by ui , yi , vi ; the original edge is removed. Each red yi ∈ F also receives one green neighbor pi ∈ S. Blue nodes form C and retain degree ∆. Dotted lines represent routes with omitted core nodes and edges; neither their drawn lengths nor the depicted degrees are literal. The selected edges are pairwise at distance at least ℓ in H, so shortest core paths encounter few subdivisions. Three of the |F | = |S| = k attachment sites are shown. Only red nodes may crash; after they do, S remains a path, or a cycle with the dashed closing edge. large N with ∆ · N even, a simple ∆-regular graph with N nodes and diameter at most D exists whenever (∆ − 1)D−1 ≥ 3 · ∆ · N · ln N . Let N be the largest even integer not exceeding A := (∆ − 1)D−1 /(6 · ∆ · D · ln(∆ − 1)). For sufficiently large D, we have A/2 ≤ N ≤ A ≤ (∆ − 1)D , and hence ln N ≤ D · ln(∆ − 1). Therefore, 3 · ∆ · N · ln N ≤ 3 · ∆ · A · D · ln(∆ − 1) = (∆ − 1)D−1 /2, so the diameter theorem applies. Moreover, N ≥ A/2 = (∆ − 1)D /(12 · ∆ · (∆ − 1) · ln(∆ − 1) · D), which gives the claim with c∆ := 1/(12 · ∆ · (∆ − 1) · ln(∆ − 1)). The nodes of H form the set C, and we select a set M of edges of H as attachment sites. Since H is ∆-regular, we cannot connect the nodes of F to C by additional edges, so we subdivide the selected edges instead. More precisely, for each edge e = {u, v} ∈ M , we add a new node ye to F and a new node pe to S, replace e by the path u, ye , v, and add the edge {ye , pe }, as shown in Figure 6. We obtain G− by adding a path through all nodes of S, in an arbitrary order, and G+ by additionally adding the closing edge between its endpoints. This way, every selected edge contributes exactly one node of F and one node of S, so |S| = |M |. Moreover, there are no edges between C and S. It remains to decide which edges of H to select. Each subdivision makes paths through that edge one step longer: if we subdivided every edge of H, all distances in H would double. Bounding eccentricities using paths through the subdivided core would then require choosing D to be about √ R/2. Instead, we select edges of H that are pairwise at distance at least ℓ ≈ R. Then, a shortest √ √ path in H passes through only O(D/ℓ) = O( R) selected edges, so distances grow by only O( R), √ and we can choose D = R − O( R). We select edges greedily, keeping distance at least ℓ between them. Once no further edge can be selected, every node of H lies within distance ℓ of some selected edge. Each selected edge has only

44

O((∆ − 1)ℓ ) nodes − 1)ℓ ) selected edges. √ √ this close to it. Thus, covering all N nodes requires Ω(N/(∆ Since ℓ = ⌈ R⌉, this separation reduces the exponent by only O( R). Choosing the smaller √ core diameter D = √ R − O( R) causes another reduction of the same order. Together, these give |S| = (∆ − 1)R−O∆ ( R) . Choosing the parameters and attachment sites. We now √ make this precise. Fix ∆ ≥ 3, and assume that R is sufficiently large, depending on ∆. We set ℓ := ⌈ R⌉, the minimum distance between attachment sites, and D := R − ℓ−5, the upper bound on the core’s diameter. This choice of D leaves room for the extra distance caused by the subdivisions and by the nodes of S, so that every node of S has eccentricity at most R − 1, as we show below. Since R is large, so is D, and Lemma 30 provides a ∆-regular graph H of diameter at most D with N nodes, where c∆ · (∆ − 1)D /D ≤ N ≤ (∆ − 1)D . To select the attachment sites, we define the distance between edges e, e′ of H as distH (e, e′ ) := min{distH (u, v) : u ∈ e, v ∈ e′ }. Then, we choose an inclusion-maximal set M of edges of H with pairwise distance at least ℓ, and write k := |M | = |F | = |S|. Since two edges sharing an endpoint have distance 0 < ℓ, the edges of M form a matching. By maximality, every node of H lies within distance ℓ of an endpoint of some edge of M : every node has an incident edge, and every edge outside M P has an endpoint at distance less than ℓ from an endpoint of an edge in M . Moreover, at most 2 · ℓj=0 (∆ − 1)j ≤ 4 · (∆ − 1)ℓ nodes lie within distance ℓ of the endpoints of a single edge: in a breadth-first search from the two endpoints, each endpoint has at most ∆ − 1 neighbors other than the other endpoint, and each later node has at most ∆ − 1 new neighbors. Consequently, k≥

N c∆ · (∆ − 1)D−ℓ . ≥ 4D 4 · (∆ − 1)ℓ

(3)

We apply the construction described above with this set M of attachment sites. We now show that the resulting graphs G− and G+ satisfy the requirements of Lemma 25 with T = Ω(k), hence proving Lemma 29. Proof of Lemma 29. Fix an integer ∆ ≥ 3. Choose an integer R0 (∆) ≥ 4 such that, for every R ≥ R0 (∆), the core construction above is available, the lower bound on k in (3) is at least eight, and √ c∆ · (∆ − 1)⌈ R⌉−5 ≥ R. 32 √

Such a choice is possible by Lemma 30, (3), and the fact that (∆ − 1)⌈ R⌉ /R → ∞ as R → ∞. The threshold depends only on ∆. Fix R ≥ R0 (∆), and let n and f satisfy the assumptions of the lemma. We first check that G− and G+ have maximum degree at most ∆ and at most n nodes. The nodes of C keep degree ∆, every node of F has degree three, and every node of S has degree at most three. Since M is a matching, k ≤ N/2, so the construction has N + 2k ≤ 2N ≤ 2 · (∆ − 1)D ≤ (∆ − 1)R ≤ n nodes. The bound 2(∆ − 1)D ≤ (∆ − 1)R follows from R − D = ℓ + 5 and (∆ − 1)ℓ+5 ≥ 2. The final inequality uses the assumption n ≥ (∆ − 1)R . Next, we verify the requirements of Lemma 25. First, the construction respects the crash bound, since |F | = k ≤ (∆ − 1)D /2 ≤ (∆ − 1)R /∆ ≤ f. The first inequality follows from k ≤ N/2 and N ≤ (∆ − 1)D . The second uses R − D = ℓ + 5 and (∆ − 1)ℓ+5 ≥ ∆/2, while the last follows from the assumption on f . For the eccentricity condition, we first bound distances between nodes of C. Consider a shortest path in H of length λ ≤ D, containing κ selected edges. Subdividing these edges increases its length to λ + κ. If κ ≥ 1, the separation between consecutive selected edges gives λ ≥ κ + (κ − 1)ℓ. Thus, κ ≤ ⌈λ/(ℓ + 1)⌉, which also holds when κ = 0. Consequently, any two nodes of C have distance at most D + ⌈D/(ℓ + 1)⌉ ≤ D + ℓ in G+ , where the last inequality follows from D ≤ R ≤ ℓ2 . 45

Finally, every node of the construction is within distance two of C. We can therefore connect any node of S to any other node by reaching C, following a path between two nodes of C, and leaving C. The resulting distance is at most 2 + (D + ℓ) + 2 = R − 1. Hence, every node of S has eccentricity at most R − 1 in G+ . It remains to verify conditions (a) and (b) of Lemma 25. The graph G+ [S] is a cycle on k nodes, and each ye has exactly one neighbor pe in S. The distances are therefore as in the one-standard-crash construction of Section 6.2: for (a), pe has a node at distance ⌊k/2⌋ in G+ [S], and for (b), some node has distance ⌊(k − 1)/2⌋ from the endpoints of the closing edge. By the choice of R0 (∆), we have k ≥ 8, so both conditions hold with T := ⌊k/4⌋. By Lemma 25, no deterministic T -round algorithm solves ΠCN (R) on both graphs under atomic crashes, so every algorithm needs more than ⌊k/4⌋ ≥ k/8 rounds. Finally, we express this bound in terms of R. Substituting √ D = R − ℓ − 5 into (3) and using R⌉−5 /R rounds. The inequality D ≤ R, every algorithm needs at least (c∆ /32) · (∆ − 1)R−2⌈ √ imposed when choosing R0 (∆) makes this at least (∆ − 1)R−3⌈ R⌉ rounds.

6.4

Dependence on the Crash Bound and Radius

We now focus on Theorem 2(iii), which shows how the round complexity depends on the crash bound f : on graphs of
maximum degree at most ∆, any algorithm for ΠCN (R) may need Ω (R − 2 log∆−1 f ) · f · ∆ rounds. The following lemma gives bounds for atomic crashes with f ≥ 2 and f = 1 for standard crashes. Lemma 31 (Lower bounds in terms of f , R, and ∆). Let ∆ ≥ 3. The following hold for deterministic algorithms that solve ΠCN (R) on all graphs with at most n nodes and maximum degree at most ∆: that tolerates at most (a) Let f ≥ 2, R ≥ 2⌈log∆−1 f ⌉ + 4, and n ≥ R · f · ∆. Every such algorithm
f atomic crashes needs at least (∆ − 1) · f · R − 2⌈log∆−1 f ⌉ − 3 /4 rounds. (b) Let R ≥ 4 and n ≥ R · ∆. Every such algorithm that tolerates one standard crash needs more than ⌊(∆ − 1) · (R − 3)/4⌋ rounds. The main constraint is the bound on the number of crashes: since at most f nodes crash and each has degree at most ∆, at most f · ∆ nodes of S, which we call attachment sites, can be adjacent to F . If S consisted only of these sites, the cycle G+ [S] would have length O(f · ∆), so conditions (a) and (b) of Lemmas 23 and 25 could hold only for T = O(f · ∆), and the resulting lower bound would not grow with R. We therefore place about R − 2 log∆−1 f additional nodes of S between any two consecutive attachment sites, as illustrated in Figure 7. Along each subpath between consecutive attachment sites, every node is at distance at most half the subpath’s length from an attachment site. Each attachment site is adjacent to a node of F , and these nodes are leaves of a tree of diameter at most 2⌈log∆−1 f ⌉. We choose the subpath lengths so that every node of S has eccentricity at most R − 1 in G+ . This increases the cycle length by a factor of Θ(R − 2 log∆−1 f ). 6.4.1

Atomic crashes with f ≥ 2

We first prove the bound for atomic crashes in Lemma 31, following the idea above: we connect the f crashing nodes by a small tree, and separate their attachment sites by long subpaths of S. To this end, let h := ⌈log∆−1 f ⌉, so that the tree has height at most h, and let L := R − 2h − 3 be the number of edges between consecutive attachment sites. The assumption on R in Lemma 31(a) gives R ≥ 2h + 4, and hence L ≥ 1.

46

core tree: internal nodes C, leaves F

y1

y2

y3

y4

L edges

af (∆−1)

a1 S: the surviving path closing edge, present only in G+

Figure 7: The construction for Theorem 2(iii), illustrated with ∆ = 4 and f = 4. Every horizontal link represents a path of L edges; its omitted internal nodes also belong to S. The dashed closing edge is a single edge, present only in G+ . Each failing node is adjacent to a consecutive block of ∆ − 1 attachment sites. After F crashes, the core is disconnected from the surviving path or cycle, whose length is Θ(L · f · ∆). We take a rooted tree of height at most h with exactly f leaves, in which every internal node has at least two and at most ∆ − 1 children. We first show that such a tree exists: start with the complete (∆ − 1)-ary tree of height h, keep only the paths from the root to f of its leaves. Repeatedly remove any non-root node with exactly one child and connect its parent directly to that child. If the root has only one child, remove it and make its child the new root. We let F = {y1 , . . . , yf } be its leaves and C its internal nodes. Since every internal node has at least two children, |C| ≤ f − 1. Furthermore, the tree has height at most h, which implies that any two nodes of the tree have distance at most 2h. Next, we form a path with f · (∆ − 1) attachment sites a1 , . . . , af (∆−1) in this order, with exactly L edges between consecutive sites. Let S be the node set of this path, including the nodes between the sites. For each j ∈ {1, . . . , f }, we join yj to the ∆ − 1 consecutive sites a(j−1)(∆−1)+1 , . . . , aj(∆−1) . This defines G− , and adding the closing edge {a1 , af (∆−1) } gives G+ , as illustrated in Figure 7. Thus, G− [S] is a path, G+ [S] is a cycle, and the nodes of C have no neighbors in S. We now prove the bound for atomic crashes in Lemma 31, using Lemma 25 with T = Ω(L · f · ∆). Proof of Lemma 31(a). We first check that G− and G+ satisfy the requirements of the lemma statement, i.e., that they have maximum degree at most ∆ and at most n nodes. Every node of C has at most one parent and ∆ − 1 children, every yj has one parent and ∆ − 1 attachment sites as neighbors, and every node of S has degree at most three, so the maximum degree is at most ∆. Since |S| = (f ·(∆−1)−1)·L+1, the number of nodes is |S|+|F |+|C| ≤ L·f ·(∆−1)+2f ≤ R ·f ·∆ ≤ n. Next, we check the requirements of Lemma 25. The lemma applies with crash bound f = |F |. For the eccentricity condition, note that every node of S is within distance ⌊L/2⌋ of an attachment site. Passing through the tree, any p, q ∈ S therefore satisfy distG+ (p, q) ≤ 2⌊L/2⌋ + 2 + 2h ≤ L + 2h + 2 = R − 1. Similarly, for every p ∈ S and z ∈ C ∪ F , we have distG+ (p, z) ≤ ⌊L/2⌋ + 1 + 2h ≤ R − 1. This implies that every node of S has eccentricity at most R − 1 in G+ . It remains to verify conditions (a) and (b) of Lemma 25. All distances in this verification are measured in the cycle G+ [S]. For condition (a), fix yj ∈ F . Its ∆ − 1 attachment sites occur consecutively along the cycle and occupy a path with (∆ − 2) · L edges. The other path between the first and last of these sites has |S| − (∆ − 2) · L = (f − 1) · (∆ − 1) · L + 1 edges and has no neighbor of yj in its interior. Choose 47

a middle node p of this other path. The nearest attachment site of yj is therefore one of the two endpoints of this other path. Hence,  
f · (∆ − 1) · L (f − 1) · (∆ − 1) · L + 1 ≥ distG+ [S] p, NG+ (yj ) ∩ S = , 2 4 where the inequality uses f ≥ 2. For condition (b), choose a middle node q of the path from a1 to af (∆−1) that avoids the closing edge. This path has (f · (∆ − 1) − 1) · L edges, so  
(f · (∆ − 1) − 1) · L f · (∆ − 1) · L distG+ [S] q, {a1 , af (∆−1) } = ≥ , 2 4 where the inequality uses f · (∆ − 1) ≥ 4 and L ≥ 1. Taking T := ⌈f · (∆ − 1) · L/4⌉ − 1 gives T < f · (∆ − 1) · L/4, so both conditions hold. By Lemma 25, no deterministic T -round algorithm solves ΠCN (R) on both graphs under at most f atomic crashes. Hence, the worst-case round complexity is at least T + 1 ≥ (∆ − 1) · f · L/4. 6.4.2

One standard crash

We now prove Lemma 31(b) in the standard crash-fault model, with z as the only node that may crash. In the preceding construction for atomic crashes, the tree connects the f nodes that may crash. Here, only z may crash, so no tree is needed. We instead adapt the construction for a single crash from Section 6.2: z is adjacent to ∆ attachment sites, with additional nodes placed between consecutive sites along the path. More precisely, let C = ∅ and F = {z}, and let L := R−3 be the number of edges between consecutive attachment sites; the assumption R ≥ 4 gives L ≥ 1. We take ∆ attachment sites on a path with L edges between consecutive sites, let S be the node set of this path, and join z to every attachment site. This defines G− , and adding the closing edge between the first and the last site gives G+ . We now present the proof for one standard crash in Lemma 31, using Lemma 23 with T = Ω(R·∆). Proof of Lemma 31(b). We first check that G− and G+ satisfy the requirements in the lemma statement, i.e., that they have maximum degree at most ∆ and at most n nodes. The node z has degree ∆, and every node of S has degree at most three. Since |S| = (∆ − 1) · L + 1, the construction has |S| + 1 ≤ R · ∆ ≤ n nodes. Next, we check the requirements of Lemma 23. Every node of S can reach z by following at most ⌊L/2⌋ edges to an attachment site and then its edge to z. Thus, any two nodes of S have distance at most 2⌊L/2⌋ + 2 ≤ L + 2 = R − 1 in G+ . Since z is the only node outside S, every node of S has eccentricity at most R − 1 in G+ . For conditions (a) and (b), set T := ⌊(|S| − 1)/4⌋. All distances in these two conditions are measured in the cycle G+ [S]. For condition (a), fix w ∈ NG+ (z) ∩ S and choose a node p farthest from w along the cycle. Their distance is ⌊|S|/2⌋ ≥ T , as required. For condition (b), consider the path between the endpoints of the closing edge that avoids this edge. It has |S| − 1 edges. Choose a middle node q of this path. Its distance in the cycle to the nearer endpoint is ⌊(|S| − 1)/2⌋ > T , where the strict inequality follows from |S| ≥ 3. Thus, both endpoints are at distance greater than T from q. By Lemma 23, no deterministic T -round algorithm solves ΠCN (R) on both graphs when z may crash in the standard crash-fault model. Since |S| − 1 = (∆ − 1) · (R − 3), the worst-case round complexity is greater than ⌊(∆ − 1) · (R − 3)/4⌋.

48

6.5

Putting It All Together

We now combine the lemmas of Sections 6.2 to 6.4 into a proof of Theorem 2. Recall that atomic crashes are a special case of standard crashes, so every lower bound under atomic crashes also holds in the standard crash-fault model. Proof of Theorem 2. Part (i) follows from Lemma 27. Under a single standard crash, i.e., for f = 1, part (a) of the lemma gives a lower bound of more than ⌊n/2⌋ − 2 = Ω(n) rounds for every R ≥ 3. In the atomic crash-fault model, part (b) of the lemma gives more than ⌊(n − 2)/4⌋ = Ω(n) rounds for every R ≥ 4 and f = 2. The fixed lower thresholds on n do not affect the asymptotic bounds. Part (ii) follows from Lemmas 28 and 29. Under the assumptions on ∆, R, n, and
f in the ⌊(R−1)/2⌋ ⌊(R−1)/2⌋ /8 = Ω (∆ − 1) theorem, Lemma 28 gives a lower bound of (∆ − 1) rounds in the standard crash-fault model. The same lemma proves this bound under atomic crashes with the additional assumption f ≥ 2, as required by the theorem. For each integer ∆ ≥ 3, take √ R0 (∆) from Lemma 29. For every R ≥ R0 (∆), that lemma gives R−3⌈ R⌉ , provided that n ≥ (∆ − 1)R and f ≥ ⌈(∆ − 1)R /∆⌉. The the stronger bound (∆ − 1) threshold is independent of n and f . This bound holds under atomic crashes, and therefore also under standard crashes, proving the stronger claim in part (ii). Part (iii) follows from Lemma 31. First, suppose f ≥ 2, and let L := R − 2⌈log∆−1 f ⌉ − 3 ≥ 1. By Lemma 31(a), the round complexity is at least (∆ − 1) · f · L/4 under atomic crashes, and therefore also under standard crashes. To compare this with the bound in the theorem, note that ⌈log∆−1 f ⌉ < log∆−1 f +1 gives R−2 log∆−1 f < L+5 ≤ 6L. Together with ∆−1 ≥ 2∆/3, this yields the following: (R − 2 log∆−1 f ) · f · ∆ (∆ − 1) · f · L ∆·f ·L ≥ ≥ . 4 6 36 For f = 1, Lemma 31(b) requires more than ⌊(∆ − 1) · (R − 3)/4⌋ rounds in the standard crash-fault model. Since the round complexity is an integer, it is at least   (∆ − 1) · (R − 3) (∆ − 1) · (R − 3) R·∆ +1> ≥ , 4 4 24 where the last inequality uses R − 3 ≥ R/4 for R ≥ 4 and ∆ − 1 ≥ 2∆/3 for ∆ ≥ 3. Since log∆−1 1 = 0, this establishes the claimed bound for f = 1.

7

Crash Tolerance for Locally Checkable Labelings

We prove both parts of Theorem 4. Section 7.1 focuses on part (i) and shows that fault-free O(log∗ n) complexity is preserved under crash faults. Afterwards, Section 7.2 constructs an LCL with fault-free complexity Θ(log n) and crash-tolerant complexity Θ(n), proving part (ii).

7.1

Preserving Log-Star Complexity

To prove Theorem 4(i), fix an integer degree bound ∆ ≥ 2 and an LCL problem Π with checking radius ℓ ≥ 1 that admits a deterministic O(log∗ n)-round fault-free algorithm on all graphs of maximum degree at most ∆. We show that Π also admits a deterministic algorithm with the same asymptotic round complexity that tolerates any number of crashes. On graphs of bounded degree, every LCL problem with the assumed deterministic fault-free round complexity, including Π, admits a deterministic fault-free algorithm in the following two-stage normal form [CKP19] (see also [BCHM+ 21, proof of Theorem 7]): it first computes, in O(log∗ n) rounds, 49

a coloring with a constant number of colors such that any two distinct nodes within a fixed constant number of hops receive distinct colors. It then runs a constant-round algorithm that uses this coloring. More precisely, the normal form provides constants t, q ≥ 1, depending only on Π and ∆, and a deterministic LOCAL algorithm B. The constant t specifies the coloring distance and bounds the running time of B. We fix a normal form whose first stage is the Linial reduction schedule described below, and let q be its terminal palette bound. The candidate families and stopping rule are fixed as part of this choice. We express the coloring distance using graph powers. For a graph G of maximum degree at most ∆, let Gt denote its t-th power : it has the same node set as G, and two distinct nodes are adjacent if and only if their distance in G is at most t. The first stage computes a proper coloring c : V (G) → {1, . . . , q} of Gt , i.e., any two distinct nodes within distance t in G receive distinct colors. Given any such coloring on any graph G of maximum degree at most ∆, algorithm B solves Π within t fault-free rounds when each node v receives its color c(v) as an additional input. This guarantee applies independently of how the coloring was computed. Our crash-tolerant algorithm for Π follows these two stages. First, we show that the color reduction still produces the required q colors in O(log∗ n) rounds when nodes crash. Then, we construct consistent views of constant radius and use them to simulate B locally. Linial’s color reduction. We recall Linial’s color reduction without crashes [Lin92], applied to Gt . Let ∆Gt be a known upper bound on the maximum degree of Gt . Since ∆ and t are constants, ∆Gt is constant as well. We call the set of allowed colors the palette, and its size the palette bound. Let M denote the current palette bound. Initially, each node uses its identifier as its color, giving a proper coloring with the known palette bound M = max{2, n}cID . The algorithm then shrinks the palette in a sequence of reduction steps: each step maps a proper coloring with palette {1, . . . , M } to a proper coloring with a smaller palette {1, . . . , K}, which becomes the palette for the next step. In each reduction step, all nodes use the same globally known family of candidate sets F1 , . . . , FM ⊆ {1, . . . , K}, where Fi contains the possible new colors associated with old color i. The family is chosen so that every Fi contains at least one color outside the union of any at most ∆Gt candidate sets associated with other old colors. Such a family exists with K = O(∆2Gt log M ). Writing c(v) for the current color of v, each node learns its neighbors’ current colors in Gt and chooses the smallest candidate in Fc(v) that belongs to none of their candidate sets. Its new color   S is therefore c′ (v) = min Fc(v) \ u∈N t (v) Fc(u) . G It remains to verify that every node has an available new color and that the new coloring is proper. First, each node v has at most ∆Gt neighbors in Gt . Since the current coloring is proper, all these neighbors have colors different from c(v). The defining property of the candidate sets therefore ensures that Fc(v) contains at least one color outside all of their candidate sets, so v can choose a new color. Second, consider adjacent nodes u, v in Gt . Each chooses its new color from its own candidate set while excluding the other node’s candidate set: c′ (u) ∈ Fc(u) \ Fc(v) and c′ (v) ∈ Fc(v) \ Fc(u) . These two sets are disjoint, so c′ (u) ̸= c′ (v). Thus, the new coloring is proper. After the step, all colors lie in {1, . . . , K}. The next step uses a new candidate family based on this palette bound and the same degree bound ∆Gt . For constant ∆Gt , the palette bound decreases from nO(1) to O(log n), then to O(log log n), and eventually to at most q after O(log∗ n) steps. Each step on Gt is simulated by forwarding current colors for t = O(1) rounds in G, so the total communication complexity is O(log∗ n). Linial’s color reduction with crashes. We use the same initial colors, palette bounds, and globally known families of candidate sets as in the fault-free procedure. In each reduction step, nodes

50

send and forward current colors for t rounds in G, keeping their own current colors fixed during this exchange. Each message contains the source identifier and the reduction step number. At the end of the step, each node v that has not crashed forms the set Jv of distinct colors received from other nodes for this step, discarding any value equal to c(v). It then chooses the smallest candidate in Fc(v) that belongs to none of the candidate sets associated with colors in Jv . Its new color is therefore  S ′ c (v) = min Fc(v) \ j∈Jv Fj . A received color is included in Jv even if its source crashes during the step; if no color is received from a node, its candidate set is omitted for this step. The next step uses a new candidate family based on the new palette bound K and the same degree bound ∆Gt . Lemma 32 (Linial’s color reduction under crashes). Fix integers ∆ ≥ 2 and t ≥ 1, independent of n. Let G = (V, E) be a graph with at most n nodes and maximum degree at most ∆. Assume that nodes have identifiers from the known universe specified in Section 3.2 and globally known bounds n and ∆. Consider the color-reduction procedure above in the standard crash-fault model, and let A be the set of nodes that complete the coloring phase without crashing. These nodes may crash in later phases. The procedure has the following guarantees: • Existence of an available color. In every reduction step, each node that has not crashed has at least one available color to choose. • Palette bound. Each reduction step uses the same palette bound as its fault-free version. The fixed terminal palette bound q depends only on ∆ and t, and every node in A outputs a color in {1, . . . , q}. • Proper coloring. The resulting coloring c : A → {1, . . . , q} is proper on (G[A])t : c(u) ̸= c(v) for all distinct u, v ∈ A with distG[A] (u, v) ≤ t. • Round complexity. The phase uses the same predetermined reduction steps and takes the same number of rounds as the fault-free procedure, namely t rounds per reduction step and O(t log∗ n) = O(log∗ n) rounds in total for fixed ∆ and t. Proof. We first prove that, in every reduction step, an available color exists. Fix a reduction step and a node v that has not crashed by the end of that step. Every color received from another node during the t communication rounds originates at a node of NGt (v). Hence |Jv | ≤ ∆Gt , where ∆Gt is the fixed degree bound used in the procedure. Moreover, c(v) ∈ / Jv , since v discards any received color equal to c(v) when forming J . The defining property of the candidate sets therefore gives v S Fc(v) \ j∈Jv Fj ̸= ∅, so v can choose an available color. This holds even if some received colors originate at nodes that crash during the step. Next, we show that crashes do not affect the palette bounds or the number of rounds. In every reduction step, each node v chooses its new color from its own candidate set Fc(v) ⊆ {1, . . . , K}. Crashes can only reduce the set Jv of excluded candidate sets, so the new color still lies in {1, . . . , K}. Moreover, the degree bound ∆Gt , the candidate families, and the sequence of palette bounds are fixed in advance and coincide with those of the fault-free procedure. Since ∆Gt depends only on ∆ and t, this sequence reaches its fixed terminal palette bound q after O(log∗ n) reduction steps. Each step takes t communication rounds, so the procedure takes O(t log∗ n) = O(log∗ n) rounds in total. We prove properness on (G[A])t by induction over the reduction steps. Initially, the coloring is proper because identifiers are unique. Suppose it is proper at the beginning of a step, and let u, v ∈ A be distinct nodes with distG[A] (u, v) ≤ t. A path of length at most t in G[A] connects them, and every node on this path completes all t communication rounds of the step without crashing. Their current colors therefore reach each other before either endpoint updates its color. By the induction hypothesis, c(u) ̸= c(v), so neither received color is discarded: c(u) ∈ Jv and c(v) ∈ Ju . Consequently, v chooses c′ (v) ∈ / Fc(u) , whereas u chooses c′ (u) ∈ Fc(u) . Thus c′ (u) ̸= c′ (v), completing the induction. 51

Simulating B on consistent views. Our crash-tolerant algorithm first runs the color reduction above, using the same palette schedule as the fault-free color reduction of the normal form. It then simulates B on consistent views of radius R := t + ℓ + 1. To establish this, we run the ΠCN (R) algorithm of Algorithm 5 with fresh initial stars, each carrying its source’s original input label and its color after color reduction. For the analysis only, assign color 1 to all nodes outside A; they send no fresh stars or messages in this phase, so these assigned colors do not occur in any view. Each surviving node v then simulates B on its view Hv and adopts its own simulated output. Proof of Theorem 4(i). By Lemma 32, every node in A obtains a color in the normal form’s palette {1, . . . , q}, and this coloring is proper on (G[A])t . Next, we show that B solves Π on every view. In the second stage, we treat the color of each node as part of its input label. Since R ≥ 3, the proof of Theorem 3 shows that Algorithm 5 solves ΠCN (R) under any number of crashes, where nodes that crashed during the first stage count as crashed from the beginning. Therefore, by termination and radius, every surviving node v obtains a view Hv that is a labeled subgraph of G. Since colors are part of the input labels, every node of Hv appears in Hv with its color from the first stage, even if it crashes during the second stage. Moreover, Hv = G[Wv ], and every token in Wv was initiated by a node that completed the gathering phase of Algorithm 5, and hence the earlier color reduction. Thus, Wv ⊆ A and Hv ⊆ G[A]. Since distances in Hv are at least those in G[A], the coloring is proper on Hvt , so B solves Π on Hv within t rounds. We next verify local satisfaction. Fix a surviving node v. If any node in BG (v, ℓ) crashes during the execution, then v is locally satisfied by definition. Otherwise, every node in this neighborhood completes color reduction and survives the construction of the views. Thus, BG (v, ℓ) ⊆ A. As shown above, B produces a valid solution on each view within t rounds. Since the views satisfy ΠCN (R) with R = t + ℓ + 1, the simulation argument in the proof of Theorem 1(ii) shows that v’s checking neighborhood, including the output labels, is identical in the actual execution and in the simulation on Hv . Hence, the actual outputs satisfy the constraints of Π at v, so v is locally satisfied. Finally, color reduction takes O(log∗ n) rounds by Lemma 32. Since ∆ and R = t + ℓ + 1 are constants, constructing the consistent views takes O((∆ − 1)R ) = O(1) rounds by Theorem 3(ii) if ∆ ≥ 3, and O(R) = O(1) rounds by Theorem 3(iv) if ∆ = 2. Simulating B on these views requires no further communication, so the algorithm takes O(log∗ n) rounds in total.

7.2

An LCL with a Linear Crash-Fault Lower Bound

To prove Theorem 4(ii), we first construct an LCL problem with checking radius ℓ = 2 on graphs of maximum degree at most five. We then show that it has deterministic fault-free round complexity Θ(log n) and deterministic crash-tolerant round complexity Θ(n). Our problem, denoted Πbit , is built around a complete rooted ordered binary tree: every internal node has a left and a right child, and all leaves have the same depth. We join consecutive nodes in leftto-right order on each level by an edge so that each level forms a path. This graph family also appears in earlier LCL constructions [BBOS20, BCHM+ 21]. The input labels describe this tree-based structure and assign an input bit to the root. On a correctly labeled tree-based graph (without crashes), Πbit requires every node to output the root’s bit. To define Πbit on arbitrary input-labeled graphs, we also allow error outputs that certify structural defects or point toward them, subject to local checks. For the lower bound, we allow crashes only in the layer three edges above the leaves: crashing this entire layer before communication cuts the leaves off from the root, while every leaf’s radius-two checking neighborhood survives. We then use a similarity chain, as in Section 6, to compare executions with two inputs on the same graph that differ only in the root’s bit. In the executions of this chain, all leaves must agree on whether they output 0, output 1, or use an error output. Hence, if a leaf witnesses a

52

step of the chain, then all leaves make the same choice in both executions of that step. When the entire crashing layer fails before communication, the leaves cannot distinguish the two root bits. The chain therefore forces all leaves to output 0 even in the fault-free execution with root bit 1, a contradiction. 7.2.1

A locally verifiable ordered binary tree

This subsection formally defines the tree-based graphs Gh and the input labels that describe their structure. We give five tests, similar to local structural checks in [BBOS20, BCHM+ 21], that each node can evaluate within radius two. We show that a component in which every node passes all five tests is a correctly labeled copy of Gh for some h ≥ 0. If a component contains a node that fails a test, then every node in that component is within distance O(log n) of a node that fails a test (Lemma 33). For an integer h ≥ 0, define Gh by V (Gh ) := {(d, k) ∈ Z2 : 0 ≤ d ≤ h, 0 ≤ k < 2d }. The node (d, k) is at depth d and position k in its level; the root is (0, 0). Every node (d, k) with d < h has left child (d + 1, 2k) and right child (d + 1, 2k + 1). The edges of Gh are the parent–child edges and the horizontal edges joining (d, k) to (d, k + 1) whenever k + 1 < 2d . The number of nodes is nh := |V (Gh )| = 2h+1 − 1, the maximum degree is at most five, and diam(Gh ) ≤ 2h. We now define the structural input labels. To refer to specific neighbors while keeping the input alphabet fixed and finite, we use local port names. Consider an arbitrary graph of maximum degree at most five. At each node, assign distinct local port names from {1, . . . , 5} to its incident edges. Unused names are allowed, and the two endpoints of an edge may use different names. The structural part of the input label at v is τ (v) = (P (v), L(v), R(v), j(v), t(v)). The fields P (v), L(v), R(v) ∈ {⊥, 1, . . . , 5} designate ports toward the parent, the left horizontal neighbor, and the right horizontal neighbor, respectively; ⊥ denotes an absent reference. The field j(v) ∈ {⊥, left, right} specifies whether the node is a left or right child, with ⊥ for the root, and t(v) ∈ {internal, leaf} specifies the node type. The fields may take arbitrary values in their specified domains. An edge incident to v is called a child edge at v if its local port at v is not among P (v), L(v), R(v); its other endpoint is called a child of v. A copy of Gh is called correctly labeled if its input labels specify the parents, horizontal neighbors, child indices, and node types prescribed by its coordinates. An arbitrary input labeling might not follow these conventions consistently: the tests below check whether it does. Any required reference to a missing port or any other undefined expression causes the corresponding test to fail. We define the predicate Good(v) to hold if and only if all five tests pass at node v. (1) The non-⊥ values among P (v), L(v), R(v) are pairwise distinct and name existing ports. For every child u of v, the edge {u, v} has local port name P (u) at u. If v has parent p, then t(p) = internal and {p, v} is a child edge at p. For every right horizontal neighbor u of v, the edge {u, v} has local port name L(u) at u; for every left horizontal neighbor u of v, it has local port name R(u) at u. (2) If P (v) = ⊥, then j(v) = L(v) = R(v) = ⊥; otherwise j(v) ∈ {left, right}. If t(v) = internal, then v has exactly two children, one of each index. If t(v) = leaf, then v has no children. (3) If R(v) ̸= ⊥, then the right horizontal neighbor u of v satisfies t(u) = t(v). (4) Suppose P (v) ̸= ⊥, and let p be the parent of v. If j(v) = left, then v has a right horizontal neighbor u with j(u) = right, and the edge {u, p} exists and has local port name P (u) at u. If j(v) = right, then R(v) = ⊥ if and only if R(p) = ⊥. When j(v) = right and both entries are non-⊥, let u and q be the right horizontal neighbors of v and p, respectively. Then j(u) = left, and the edge {u, q} exists and has local port name P (u) at u. 53

(5) Suppose P (v) ̸= ⊥, and let p be the parent of v. If j(v) = right, then v has a left horizontal neighbor u with j(u) = left, and the edge {u, p} exists and has local port name P (u) at u. If j(v) = left, then L(v) = ⊥ if and only if L(p) = ⊥. When j(v) = left and both entries are non-⊥, let u and q be the left horizontal neighbors of v and p, respectively. Then j(u) = right, and the edge {u, q} exists and has local port name P (u) at u. Each test can be evaluated from the labeled radius-two neighborhood of v: tests (1), (2), (3) only involve v and its neighbors, while tests (4) and (5) compare the nodes reached by walks of length at most two. All input fields range over fixed finite sets, independently of n and h. Our error outputs will either certify a structural defect or point toward one. For an arbitrary assignment τ of structural input labels, we define the defect set Dτ := {v : ¬Good(v)}, consisting of the nodes at which at least one structural test fails. We define Jτ as the spanning subgraph of G consisting of mutually consistent parent–child edges. Error pointers may use only these edges. Specifically, its edge set consists of all {p, c} ∈ E(G) such that the local port name of {p, c} at c is P (c), j(c) ∈ {left, right}, t(p) = internal, and {p, c} is a child edge at p. Membership in Jτ requires only these conditions; other structural tests may fail. If Good(v) holds, every parent or child edge incident to v belongs to Jτ . The next lemma shows that the tests characterize correctly labeled copies of Gh . It also guarantees that, in every other component, each node can reach a structural defect through Jτ within O(log n) steps. Lemma 33 (Valid structures and nearby defects). Let G be a graph with at most n nodes and maximum degree at most five, equipped with the structural inputs above, and let K := ⌈log2 n⌉ + 1. Let X be a connected component of G. • If every node of X satisfies Good, then X is a correctly labeled copy of Gh for some h ≥ 0. • Otherwise, every node v of X satisfies distJτ (v, Dτ ) ≤ 4K. Proof. We first prove the second claim. Suppose that some node of X fails a structural test. Since every correctly labeled copy of Gh passes all five tests, X is not such a copy. We prove the distance bound by contradiction. Fix v ∈ X, and assume that no node of Dτ lies within Jτ -distance 4K of v. Every node u within this distance therefore satisfies Good(u). We show that X is a correctly labeled copy of some Gh , contradicting the assumption on X. We first show that following parent edges from v reaches a root r after fewer than K steps. Otherwise, the structural tests would force 2K > n distinct nodes below the node reached after K steps, a contradiction. Afterwards, we show that the levels below r end in a leaf level and form a correctly labeled copy of some Gh , which contains v and is therefore all of X. Assume that there is a walk of length K from v along parent edges, and let u be its endpoint. Reversing this walk gives a walk of length K from u to v in Jτ . Each node except the last is the parent of the next node, so test (1) requires it to be internal. We construct levels below u, starting with level zero consisting of u. To form the next level, we list each parent’s left and then right child, preserving the parents’ order. We prove that, for every d ≤ K, level d exists and contains 2d distinct nodes joined in this order by their right horizontal edges. Distinctness is needed only within each level; different levels need not yet be disjoint. Before proving the claim, we note that all nodes considered satisfy Good: a node at level d ≤ K is reachable from u by d parent–child edges in Jτ , so its Jτ -distance from v is at most K + d ≤ 2K < 4K. The claim holds at level zero. Suppose it holds at level d < K. The walk from u to v contains an internal node at this level, so test (3) makes the whole level internal. By test (2), each node 54

has two children, one of each index. These 2d+1 children are distinct because no node can have two designated parents. Tests (1), (4), and (5) connect each parent’s two children and connect the right child of each parent to the next parent’s left child. Thus the next level forms a horizontal path in the listed order, completing the induction. Level K would contain 2K > n distinct nodes, a contradiction. Hence, no walk of length K from v along parent edges exists. Following parent edges from v therefore stops after fewer than K steps, and by test (1), this happens only at a node r with P (r) = ⊥, i.e., at a root. The same construction below r produces levels that form horizontal paths and, by test (3), consist either entirely of internal nodes or entirely of leaves. Since 2K > n, a leaf level occurs at some depth h < K. Every node considered is within Jτ -distance less than 2K of v, so its tests pass. Different levels are disjoint because each node has a unique parent and r has none. The root conditions and tests (4)–(5) give exactly the horizontal edges of Gh , while tests (1)–(2) permit no additional parent or child edges. Hence no edge leaves the constructed copy of Gh . Since it contains v, it is the whole connected component of v. This contradicts our assumption on X, so distJτ (v, Dτ ) ≤ 4K, proving the second claim. For the first claim, suppose that every node of X satisfies Good, but X is not a correctly labeled copy of any Gh . The preceding argument uses only the assumption that X is not such a copy. Hence, for any v ∈ X, it gives a node w ∈ Dτ with distJτ (v, w) ≤ 4K. Since Jτ ⊆ G, the nodes v and w belong to the same connected component of G, so w ∈ X. This contradicts the assumption that every node of X satisfies Good. 7.2.2

The LCL and its fault-free complexity

Using the structural tests of Section 7.2.1, we now define our LCL problem and show that its fault-free complexity is Θ(log n). Problem definition. In addition to its structural label τ (v), a node v receives an input bit x(v) ∈ {0, 1} exactly when P (v) = ⊥. Thus, on a correctly labeled component Gh , only the root receives an input bit. As defined below, every node of a correctly labeled component Gh must output the input bit of the root (0, 0). In components with structural defects, nodes may instead output E to certify a defect, or ptr(p) to point toward one along the incident edge with local port name p. Definition 5 (The problem Πbit ). Πbit is the locally checkable labeling problem with checking radius two on graphs of maximum degree at most five with local port names in {1, . . . , 5}, specified as follows. • Inputs. Every node v receives its structural label τ (v) = (P (v), L(v), R(v), j(v), t(v)). If P (v) = ⊥, its input label is (τ (v), x(v)), where x(v) ∈ {0, 1} is an additional input bit; otherwise, its input label is τ (v). The input alphabet Σin consists of all labels of these two forms, with the structural fields ranging over the finite sets specified in Section 7.2.1. • Outputs. Every node v outputs a label from Σout := {0, 1, E} ∪ {ptr(p) : 1 ≤ p ≤ 5}. The labels E and ptr(p) are called error outputs. • Verifier. A node v accepts an output labeling if and only if the following checks pass in its labeled radius-two neighborhood: (a) either v and all its neighbors output the same bit, or they all use error outputs; (b) if node v outputs a bit b ∈ {0, 1}, then Good(v) holds, and if, in addition, P (v) = ⊥, then b = x(v); (c) if v outputs E, then v ∈ Dτ ; 55

(d) if v outputs ptr(p), then port p names an edge {v, u} of Jτ . If u also outputs a pointer, it must point to a node other than v. An output labeling is a solution of Πbit if and only if every node accepts. On a correctly labeled Gh , the root is the unique node v with P (v) = ⊥, so check (b) refers to it through its structural label, without using its coordinates. The proof of Lemma 34 shows that checks (a), (c), and (d) together rule out error outputs on such a component. Check (a) then forces all nodes to output the same bit, which must equal the root’s input bit by check (b). On components with structural defects, check (a) allows different error outputs at adjacent nodes. For example, a node outputting E may have a neighbor outputting ptr(p). In our constructions, pointers follow shortest paths in Jτ to a defect, which outputs E. We now verify that Πbit is an LCL. Each check is determined by the labeled radius-two neighborhood of v. The structural tests, and hence Good(v) and membership in Dτ , can be evaluated within radius two (Section 7.2.1). Whether an incident edge belongs to Jτ and whether a neighbor’s pointer points back to v are determined by the input and output labels at the endpoints. Since both alphabets are fixed finite sets and the maximum degree is at most five, Πbit is an LCL on all such input-labeled graphs, including those that are not correctly labeled copies of any Gh . Fault-Free Complexity. We may now establish the fault-free part of Theorem 4(ii). For the upper bound, Lemma 33 ensures that a node can gather enough information in O(log n) rounds to either find a defect reachable through Jτ and certify or point toward it, or reconstruct its correctly labeled component and output the root’s bit. For the lower bound, a leaf at distance h = Θ(log n) from the root cannot distinguish opposite root bits in fewer than h rounds. Lemma 34 (Fault-free round complexity). On input-labeled graphs of maximum degree at most five, Πbit has deterministic fault-free LOCAL round complexity Θ(log n). Proof. We first prove the upper bound. Let K := ⌈log2 n⌉ + 1. Our algorithm runs Algorithm 2 for 4K + 2 fault-free rounds and then computes its outputs locally, so it takes O(log n) rounds. After these rounds, every node v knows its labeled radius-(4K + 2) neighborhood. It can therefore evaluate the structural tests at all nodes within distance 4K and determine whether a defect is reachable by a path of at most 4K edges in Jτ . If so, it can compute its Jτ -distance to Dτ . If v ∈ Dτ , it outputs E. Otherwise, if its Jτ -distance to Dτ is at most 4K, it outputs ptr(p) along an edge of Jτ to a neighbor whose distance to Dτ is one less, breaking ties by local port name. If no defect is reachable within this distance, it outputs the input bit of the root of its component. The last case is well defined: if no node of Dτ is within Jτ -distance 4K of v, then Lemma 33 implies that the component of v is a correctly labeled Gh . Since nh ≤ n gives h < K, this component has diameter at most 2h < 2K, so v sees the entire component, including its root. We now show that all checks pass at every node. By Lemma 33, every component is either a correctly labeled copy of some Gh , or every node of the component has Jτ -distance at most 4K to Dτ . Consider first a correctly labeled Gh with root r. It contains no node of Dτ , so every node outputs x(r). Every node satisfies Good, and r is the only node with P (r) = ⊥, so checks (a) and (b) pass. Since no node outputs E or a pointer, checks (c) and (d) pass as well. We now consider a component with a structural defect. Every node outputs E or a pointer, so check (a) passes, and check (b) does not apply. Check (c) passes because only nodes of Dτ output E. For check (d), each pointer uses an edge of Jτ and decreases the Jτ -distance to Dτ by one. Thus, if v points to u, any pointer at u must lead to a node closer to Dτ than v, so it cannot point back to v. It remains to prove the fault-free lower bound of Ω(log n) rounds. We first show that, in every solution on a correctly labeled Gh with root r, every node outputs x(r). Since check (a) passes throughout 56

this connected component, either all nodes output the same bit or they all use error outputs. Suppose that all nodes use error outputs. Check (c) rules out E, since the component contains no defect, so every node outputs a pointer along an edge of the parent–child tree Jτ . Following pointers from any node eventually revisits a node. Since Jτ is a tree, the resulting cycle consists of two nodes pointing to each other, contrary to check (d). Hence, all nodes output the same bit, which is x(r) by check (b) at r. Now let n be a sufficiently large size bound, let h be the largest integer with nh ≤ n, and add n − nh isolated, correctly labeled one-node trees to Gh . Since n < nh+1 , we have h = Θ(log n). Assume that a deterministic algorithm A solves Πbit within T < h rounds. Consider two fault-free executions of A on this graph with identical identifiers, port names, and inputs except for opposite bits at the root of Gh . Horizontal edges preserve depth and vertical edges change it by one, so every leaf is at distance h > T from the root. Hence, a leaf has the same view through round T in both executions and produces the same output in both. However, by the claim above, it outputs the root bit, which differs between the two executions, a contradiction. Consequently, every deterministic algorithm for Πbit needs at least h = Ω(log n) rounds. 7.2.3

Crash-tolerant round complexity

In the following, we show that the crash-tolerant round complexity of Πbit is Θ(n), which completes the proof of Theorem 4(ii). The lower bound is established by the lemma below. Lemma 35 (Linear crash-tolerant lower bound). For every prescribed crash budget g(n) = Θ(n), every deterministic algorithm for Πbit that tolerates up to g(n) atomic crashes has worst-case round complexity Ω(n), with correctness as in Definition 1. To prove Lemma 35, we fix a correctly labeled Gh with Θ(n) nodes, in which only the nodes three levels above the leaves may crash. As in Section 6, we construct a similarity chain, here from the fault-free execution on Gh with root bit 0 to the fault-free execution on Gh with root bit 1, in which each step is witnessed by a leaf (Lemma 36). In every execution, either all leaves output the same bit or they all use error outputs. The unchanged output of each witness then forces all leaves to output 0 throughout the chain, contradicting the required output 1 at the other endpoint. Setup. Let n ≥ n4 be the globally known size bound, and let h be the largest integer with nh ≤ n. Then h ≥ 4 and n < nh+1 = 2nh + 1, so nh ≥ n/2. Let G be the graph obtained by adding n − nh isolated, correctly labeled one-node trees to Gh . Thus, G has exactly n nodes. The added components exchange no messages with Gh , and their input bits remain fixed throughout the argument. The crashes will occur in the level at depth h − 3, which contains f := 2h−3 = (nh + 1)/16 = Θ(n) nodes. We equip Gh with its correct structural inputs and fix its identifiers, port names, and the remaining global bounds. We also fix the input bits at the roots of the isolated components. Only the input bit x((0, 0)) of the root of Gh , which we call the root bit, will vary between our executions. Let F be the set of nodes of Gh at depth h − 3, let S consist of its bottom three levels, at depths h − 2, h − 1, h, and let C := V (G) \ (F ∪ S). In particular, C includes the added isolated nodes, which are omitted from Figure 8. We use three properties of this partition. First, every edge of Gh joins nodes at equal or adjacent depths, and the added nodes are isolated. Hence, G has no edges between C and S and respects (C, F, S) for both root bits. Second, every leaf of Gh is three edges from F , so BG (v, 2) ⊆ S for every such leaf v. Third, the leaves of Gh induce a horizontal path. Let T := f , and fix a deterministic T -round algorithm A. Since G respects (C, F, S), we can use the atomic crash schedules, views, indistinguishability, sets Dt , and similarity chains of Section 6.1 and Definition 4. The spreading lemmas used below apply to every deterministic algorithm on such

57

depth 0

h − 3 edges

root input b

1 C upper levels omitted F

h−1

ℓ=2

h−2 S

3 edges

h−3

h

Figure 8: The graph Gh and the crash layer F at depth h − 3. The dashed box marks S, the bottom three levels, and the leaves are shown in green. Only the leftmost and rightmost subtrees below F are expanded. Dotted branches and horizontal segments indicate omitted nodes. Every leaf is three edges from F , so its radius-two checking neighborhood is contained in the surviving subgraph Gh [S]. a graph; they do not require A to solve ΠCN (R). In the rest of this argument, a leaf means a leaf of Gh , rather than one of the added isolated nodes. For b ∈ {0, 1} and an atomic crash schedule c : F → {1, . . . , T } ∪ {∞}, we denote by E(b, c) the execution of A on G, with bit b at the root of Gh , in which every z ∈ F with c(z) < ∞ crashes at the beginning of round c(z) and every other node runs A for all T rounds. Every such execution has at most |F | = f atomic crashes, all in F , and all nodes of C ∪ S survive in it. Most steps of our chain change the crash time of a single node of F . To witness such a step, we need a leaf far from that node’s neighbors in S, with distances measured in Gh [S]. The following observation supplies this leaf and plays the role of condition (a) of Lemma 25. Observation 2 (Distant
leaves). Each node zi = (h − 3, i) ∈ F , 0 ≤ i < f , has a leaf pi with distGh [S] pi , NGh (zi ) ∩ S ≥ f . Proof. The top level of S, at depth h−2, has 2f nodes at positions 0, . . . , 2f −1. For w ∈ S, let π(w) be the position of its ancestor at depth h − 2. A parent–child edge in Gh [S] preserves π, and a horizontal edge changes it by at most one. Consequently, distGh [S] (u, v) ≥ |π(u) − π(v)| for all u, v ∈ S. The neighbors of zi in S are its two children, whose π-values are 2i and 2i+1. The leftmost leaf has π-value 0, so its distance to this neighbor set is at least 2i. The rightmost leaf has π-value 2f −1, giving a lower bound of 2f − 2i − 2. Choose pi to be the extreme leaf with the larger of these two bounds. The two bounds are even and sum to 2f − 2, so their maximum is at least f − 1. Since f =
2h−3 is even for h ≥ 4, an even integer at least f − 1 is at least f . Thus, distGh [S] pi , NGh (zi ) ∩ S ≥ f , as required. We now construct the chain. As in the proof of Lemma 25, it moves the crashes of the nodes of F earlier, one node and one round at a time, until all of F crashes before communication. At that point, S is cut off from the root, so we can switch the root bit without any leaf noticing. Finally, we undo the crashes with root bit 1. Lemma 36 (A chain between the root bits). For the deterministic T -round algorithm A fixed above, with T = f , there is a similarity chain from E(0, c∞ ) to E(1, c∞ ) in which every step has a leaf as a witness.

58

h = 4: F = {z0 , z1 } at depth 1, f = T = 2; the band S (depths 2–4) is drawn schematically 0

z0

0

z1

rd. 2 z0

0

z1

rd. 2 z0

0

z1

rd. 2

rd. 1 z0

0

z1

rd. 2

rd. 1 z0

z1

rd. 1

S

E0 = E(0, c∞ ) fault-free

E1 = E(0, c2,1 ) z0 crashes in round 2

E2 = E(0, c2,2 ) z1 crashes in round 2

E3 = E(0, c1,1 ) z0 moved to round 1

E4 = E(0, c1,2 ) z1 moved to round 1

root bit 0 → 1; F silent, so every leaf is a witness 1

z0

1

z1

rd. 2 z0

1

z1

rd. 2 z0

1

z1

rd. 2

rd. 1 z0

1

z1

rd. 2

rd. 1 z0

z1

rd. 1

S

E9 = E(1, c∞ ) fault-free

E8 = E(1, c2,1 )

E7 = E(1, c2,2 )

E6 = E(1, c1,1 )

E5 = E(1, c1,2 ) same schedule, root bit 1

Figure 9: The similarity chain of Lemma 36 for h = 4, where F = {z0 , z1 } and f = T = 2. Each panel is an execution E(b, c): the root carries its input bit b, a dark node of F crashes atomically in the indicated round, and the band is the surviving region S, of which only the children of F and the leaves are drawn. The top row moves the crashes from ∞ to round 2 to round 1 with root bit 0; the vertical step changes the root bit while F sends nothing; the bottom row traverses the same schedules backwards with root bit 1. A ring marks a leaf that cannot distinguish the execution from the previous one in the chain: the rightmost leaf for changes at z0 , the leftmost leaf for changes at z1 , and every leaf for the bit switch. All leaves output 0 in E0 , so they would still do so in the fault-free execution E9 with root bit 1. Proof. We use the schedules cr,s of Section 6.1 with k = |F | = f and xs := zs−1 for s = 1, . . . , f , i.e., with the nodes of F ordered by position. Recall that cT,0 = c∞ and cr−1,0 = cr,f for r ≥ 2. Since G respects (C, F, S), the lemmas of Section 6.1 apply to G. Moreover, G[S] = Gh [S] and NG (zi ) ∩ S = NGh (zi ) ∩ S, so they give the following two facts: (i) For E(b, cr,s−1 ) and E(b, cr,s ), which move
the crash of zs−1 into round r, Lemma 26 implies DT ∩ S ⊆ BGh [S] NGh (zs−1 ) ∩ S, T − r . Since T = f and r ≥ 1, we have T − r < f . By Observation 2, the leaf ps−1 is at distance at least f from this neighbor set, so ps−1 ∈ / DT . (ii) For E(0, c) and E(1, c) with a schedule c under which no node of F sends any message, the initial states differ only at the root, so D0 ∩ S = ∅, and Lemma 22 with t0 = 0 gives DT ∩ S = ∅: every leaf has the same view in both executions. Let E0 := E(0, c∞ ) and, for r = T, . . . , 1 and s = 1, . . . , f , E(T −r)·f +s := E(0, cr,s ). This defines E0 , . . . , Ef ·T . In execution Ef ·T = E(0, c1,f ), all nodes of F crash before round 1. Then, let Ef ·T +1 := E(1, c1,f ), and traverse the first part backwards with root bit 1: for j = 1, . . . , f · T , let Ef ·T +1+j use root bit 1 and the schedule of Ef ·T −j . The sequence ends at E2f ·T +1 = E(1, c∞ ); see Figure 9. In the following, we show that this sequence of executions is a similarity chain, i.e., that it satisfies Definition 4.

59

Every execution in this sequence is of the form E(b, c), so it has at most f atomic crashes, all in F , and is therefore admissible. It remains to show that every step has a leaf as a witness. We consider the three parts of the chain separately. For i < f · T , the executions Ei and Ei+1 both have root bit 0. The identities cT,0 = c∞ and cr−1,0 = cr,f ensure that every such step compares cr,s−1 with cr,s for some r and s, including the first step and the transitions between rounds. By (i), the leaf ps−1 witnesses this step. The step from Ef ·T to Ef ·T +1 keeps the schedule c1,f and only changes the root bit. Under c1,f , all of F crashes before round 1, so no node of F sends any message. By (ii), every leaf is a witness of this step. Finally, consider a step from Ei to Ei+1 after the root-bit switch. Both executions have root bit 1, and this part of the chain traverses the crash schedules from the first part in reverse order. Thus, for some r and s, the step changes the schedule from cr,s to cr,s−1 , reversing the earlier change from cr,s−1 to cr,s . Statement (i) applies to both root bits. In particular, with root bit 1, it shows that the leaf ps−1 has the same view through round T under these two schedules. Reversing the order of the executions does not change this equality of views. Hence, ps−1 is also a witness of the step from Ei to Ei+1 . Hence, the sequence is a similarity chain in which every step has a leaf as a witness. We may now present the proof of Lemma 35. Proof of Lemma 35. Consider a deterministic algorithm for Πbit that tolerates up to f atomic crashes, and suppose, for a contradiction, that it terminates within T = f rounds in every such execution on G. Once a node produces an output, we keep that output fixed and compare its local history through round T . Thus, we may use this algorithm as the T -round algorithm A of the setup. We first show that, in every execution E(b, c), either all leaves output the same bit or they all use error outputs. Only nodes of F crash, so every leaf survives. In addition, the radius-two neighborhood of every leaf lies in S, where no node crashes. Since A solves Πbit , Definition 1 requires the checks of Definition 5 to pass at every surviving node whose radius-two neighborhood contains no crashed node. In particular, check (a) passes at every leaf. Thus, adjacent leaves either output the same bit or both use error outputs. Since the leaves induce a path, the claim follows. Next, in the fault-free execution E(b, c∞ ), all leaves output b. In this execution, no node crashes, so all checks pass at every node and the outputs form a solution of Πbit . By the proof of Lemma 34, every node of such a solution on a correctly labeled Gh outputs the root bit, here b. Finally, we show that all leaves output 0 in every execution of the chain of Lemma 36. This holds in its first execution, E(0, c∞ ), by the preceding paragraph. Suppose that all leaves output 0 in an execution of the chain, and let w be a leaf witnessing the step to the next execution. Since w has the same view through round T in both executions and A is deterministic, it also outputs 0 in the next execution. By the first paragraph, all leaves in that execution must therefore output 0. Induction along the chain implies that all leaves output 0 in its last execution, E(1, c∞ ). However, this execution is fault-free with root bit 1, so every leaf must output 1, a contradiction. Consequently, every deterministic algorithm solving Πbit under up to f atomic crashes requires more than f rounds in at least one of these executions. Since f = (nh + 1)/16 ≥ n/32, its worst-case round complexity is Ω(n). More generally, let g(n) = Θ(n) be any prescribed crash budget. For sufficiently large n, choose f as the largest power of two at most min{g(n), (n + 1)/16}, set h = 3 + log2 f , and pad Gh with correctly labeled isolated nodes to obtain n nodes. Then nh = 16f − 1 ≤ n, f ≤ g(n), and f = Ω(n), so the same argument applies. Upper bound. It remains to prove the crash-tolerant O(n) upper bound of Theorem 4(ii). As in Theorem 1(ii), we obtain it by simulating the fault-free algorithm of Lemma 34 on consistent views.

60

Lemma 37 (Linear upper bound with standard crashes). With correctness as in Definition 1, Πbit can be solved by a deterministic O(n)-round LOCAL algorithm on every input-labeled graph of maximum degree at most five, tolerating any number of standard crashes. Proof. Let A0 be the fault-free algorithm of Lemma 34, and let T ′ = O(log n) be its round complexity. Our algorithm first runs Algorithm 4 with radius R := T ′ + 3. Each surviving node then simulates A0 on its view and outputs the label that this simulation computes for itself. We now show that this algorithm is correct. By Theorem 1(ii), it suffices that R ≥ T ′ + ℓ + 1 for the checking radius ℓ = 2, which holds by our choice of R, and that A0 solves Πbit on every view within T ′ rounds. Each view is a subgraph of the input graph that keeps the input labels and local port names of its nodes (see Section 3.3), and the global bounds are unchanged. A label in a view may name a port whose edge is missing from the view; test (1) then fails, so this is simply a structural defect. Hence, every view is an input-labeled graph of maximum degree at most five, on which A0 solves Πbit by Lemma 34. Finally, by Lemma 11 (see also Theorem 3(i)), Algorithm 4 solves ΠCN (R) within n − 1 rounds under any number of standard crashes, and the simulations require only local computation. Hence, the algorithm takes O(n) rounds in total. Putting it all together.

We now combine Lemmas 34, 35 and 37 to prove Theorem 4(ii).

Proof of Theorem 4(ii). The problem Πbit is defined on all input-labeled graphs of maximum degree at most five and has checking radius two. Its deterministic fault-free round complexity is Θ(log n) by Lemma 34. The Ω(n) lower bound holds already for Θ(n) allowed atomic crashes by Lemma 35, while Lemma 37 gives an O(n)-round algorithm tolerating any number of standard crashes. Since atomic crashes are a special case of standard crashes, the lower and upper bounds apply in both models, establishing deterministic crash-tolerant round complexity Θ(n). 7.2.4

Removing input labels

The separation in Theorem 4(ii) also holds without problem-specific input labels, with constant maximum degree and checking radius. We use the pendant-tree construction in the full version of [BBC+ 19, Section 3.8]; see also [CDRS26, Section 4 and Lemma 4.6] for input removal in promisefree LCLs. We describe the resulting local specification and verify the crash lower bound separately. Construction and fault-free complexity. Encode each label of Σin by its constant-size rooted tree from [BBC+ 19], attached to the original node by a single edge. The maximum degree becomes six. Use the direct decoder of that construction, before its optional radius reduction. On every graph X of maximum degree six, a constant number of local pruning steps identifies a set Vlabel . The main nodes are precisely the nodes outside Vlabel with exactly one neighbor in Vlabel ; denote their set by Vmain . Each main node decodes its input label within a constant radius, assigning a fixed label of Σin to failed or unassigned codes. Every main node has a neighbor outside Vmain , so the induced graph H := X[Vmain ] has maximum degree at most five. At each node of H, number its incident edges by their order among its physical ports, and interpret the decoded port references in this order. Define the input-free problem to use output alphabet Σout , requiring the checks of Πbit on H at nodes of Vmain , and output 0 elsewhere. Fix a constant physical checking radius ℓ′ sufficient for the decoder and these checks. Local decoding followed by the algorithm of Lemma 34 takes O(log n) rounds on every X. Thus the new LCL is promise-free: malformed encodings also have solutions, without additional error certificates. For genuine encodings of Gh , h ≥ 1, choose the structural labels for the induced port order before encoding them. The decoder recovers Gh and its labels exactly, so every valid output assigns 61

the encoded root bit to all original nodes. The encoding has Θ(2h ) nodes, and the attachments cannot shorten distances between original nodes. Changing only the root attachment therefore gives the same Ω(log n) indistinguishability argument as in Lemma 34. Let s bound the number of attachment nodes per original node. For any sufficiently large known size bound n, choose h maximal with (s + 1)nh ≤ n, and pad both encodings with isolated nodes to obtain exactly n nodes. Keep identifiers, ports on common edges, and all global bounds identical. Then 2h = Θ(n). Crash-tolerant complexity. Fix a constant L > ℓ′ and take n sufficiently large that h ≥ L + 1. Crash only the original nodes at depth h − L; this set F has size f = 2h−L = Θ(n). Let S contain the bottom L original levels and their attached trees, and put all remaining nodes outside F in C, including the attachments of nodes in F . There is no C–S edge, and every original leaf is at distance L > ℓ′ from F . As in the proof of Observation 2, assign each original node in S the position of its ancestor in the top original level of S, and extend this function constantly over each attached tree. Each edge still changes this function by at most one. Hence every node of F has an original leaf at distance at least f from its neighbors in S, measured in X[S]. With T = f , the crash-time changes in the proof of Lemma 36 therefore still have leaf witnesses. For its middle step, changing the root bit changes topology only inside C; when all of F crashes before communication, the initial states and histories throughout S are identical in the two encodings. All original leaf checks remain obligatory. Check (a) of Πbit forces a common output type along their horizontal path: 0, 1, or error. Each witness preserves this type across a chain step, whereas the fault-free endpoints force opposite bits. This gives Ω(n) rounds already with atomic crashes. Finally, totality on all physical subgraphs permits the general simulation of Theorem 1(ii), together with Theorem 3(i), giving O(n) rounds with standard crashes.

8

Crash-Tolerant Algorithms for Locally Checkable Problems

In this section, we focus on two locally checkable problems, namely edge grabbing and sinkless orientation. Both are LCL problems when the maximum degree is bounded by a constant. For fixed ∆, their outputs can be encoded by a local port choice (or ⊥) for edge grabbing and one orientation bit per incident port for sinkless orientation, using port names in {1, . . . , ∆}. Our results hold on graphs of arbitrary maximum degree. We first present a crash-tolerant transformation for edge grabbing that preserves the round complexity of the fault-free algorithm. In Section 8.2, we use this transformation to obtain a crash-tolerant transformation for sinkless orientation that increases the round complexity by one communication round, proving Theorem 5.

8.1

Edge Grabbing

The fault-free edge grabbing problem requires every node of degree at least three to grab exactly one of its incident edges and output it, while every node of degree less than three outputs ⊥. No edge is grabbed by both endpoints. Under crashes, we require these conditions only for surviving nodes. All degrees and incident edges below refer to the input graph G, including edges to nodes that crash. On a ∆-regular graph with ∆ ≥ 3 supplied with a proper edge ∆-coloring, fault-free edge grabbing is precisely the sinkless coloring problem studied in [BFH+ 16, Section 2.4]: each node outputs the color of its grabbed edge, and no edge may have its color chosen by both endpoints. Our formulation requires no supplied edge coloring and also covers nodes of degree less than three. The same work gives the elementary conversion from sinkless orientation to sinkless coloring without communication and the reverse conversion in one round. Our contribution here is the crash-tolerant

62

edge-grabbing transformation, which preserves the running time and enforces the requirements even at surviving nodes adjacent to crashes. Definition 6 (Crash-Tolerant Edge Grabbing). An algorithm solves crash-tolerant edge grabbing on G = (V, E) if the following conditions hold in every execution: (i) Every surviving node v with degG (v) ≥ 3 outputs an incident edge of G, and every surviving node v with degG (v) < 3 outputs ⊥. (ii) No edge is output by both of its surviving endpoints. We now state the main result for edge grabbing. Theorem 6 (Edge grabbing under crash faults). On graphs of arbitrary maximum degree, every deterministic T -round fault-free LOCAL algorithm for edge grabbing can be transformed into a deterministic T -round LOCAL algorithm solving crash-tolerant edge grabbing in the standard crash-fault model for any number of crashes. Let AEG be a deterministic T -round fault-free LOCAL algorithm for edge grabbing. Our transformation runs AEG while each node also keeps track of whether it has seen a failure during the execution of AEG . The key idea is to propagate failure information together with the simulated messages, ensuring that nodes that never learn of a failure behave as in a fault-free execution. If the simulated algorithm halts early, we retain its state and output and send no further simulated messages; the wrapper continues exchanging flags and produces its own output only after round T . In our algorithm, each node defines a flag see-failure that is initially false. In every round, each node sends its flag to each neighbor together with the messages that AEG would send to that neighbor. The flag and these messages are sent as a single message; if AEG has no message to send, the node sends only its flag. If a node v with see-failure = false receives no message from a neighbor u, or receives see-failure = true from u, it sets its own flag to true and stores the edge {u, v}. If several neighbors satisfy this condition in the same round, v chooses the one with the smallest identifier. Such a node no longer runs AEG and, from the next round on, sends only its flag to its neighbors. A surviving node of degree at least three grabs and outputs its stored edge if its flag is true, and uses AEG ’s output otherwise. We present the pseudocode of the transformation in Algorithm 6. We prove Theorem 6 using the following three lemmas describing the guarantees of Algorithm 6. We first show that nodes whose see-failure flags remain false produce the same outputs as in the fault-free execution of the underlying algorithm AEG . Lemma 38. Let E ⋆ be the fault-free execution of AEG on G. If a node v with deg(v) ≥ 3 completes Algorithm 6 with see-failure = false, then v’s output in Algorithm 6 is the same as v’s output in E ⋆ . Proof. Let E be an execution of Algorithm 6. Consider a node v of degree at least three that completes E with see-failure = false. By the output rule, v returns the output of its simulation of AEG . Since AEG is deterministic, its output is determined by its state at the end of round T . We therefore compare the simulated state of v in E with its state in the fault-free execution E ⋆ , using the same graph, identifiers, and inputs. If these states coincide after T rounds, then v produces the same output in both executions. As in Section 6.1, we use an indistinguishability argument and prove the following claim by induction on the round number t ∈ {0, . . . , T }: for every node v, if, at the end of round t of E, node v has not crashed and has see-failure = false, then the AEG -state of v at the end of round t is the same in E and E ⋆ . For the base case t = 0, the claim holds trivially since the AEG -states are initialized as in E ⋆ , and no rounds are executed. 63

Algorithm 6 Crash-Tolerant Edge Grabbing at node v Input: labeled star σv , algorithm AEG and its inputs, and number of rounds T . Output: an incident edge of G or ⊥. 1: Initialize the simulated state of AEG ; set e ← ⊥ and see-failure ← false. 2: for t = 1, . . . , T do 3: Prepare one message for each neighbor containing see-failure. 4: If see-failure = false, include the AEG -messages for that neighbor. 5: Send these messages and receive the messages delivered in round t. 6: if see-failure = false and (some neighbor’s message is missing or has flag true) then 7: Choose such a neighbor u with the smallest identifier. 8: see-failure ← true and e ← {u, v}. 9: else if see-failure = false then 10: Update the simulated state of AEG using the received AEG -messages. 11: end if 12: end for 13: If degG (v) < 3, return ⊥. 14: If see-failure = false, return the output of the simulated AEG . 15: return e. For the induction step, let 1 ≤ t ≤ T and consider a node v that completes round t with see-failure = false in E. Its flag was also false after t − 1 rounds, so the induction hypothesis gives the same AEG -state at the beginning of round t in both executions. We note that, if v receives see-failure = false from a neighbor u in round t, then the AEG -message received by v from u in round t is the same in both executions E and E ⋆ . Indeed, the flag received from u is the one it had at the beginning of round t, so u completed round t − 1 with see-failure = false. Although u may crash during round t, it had not crashed by the end of round t − 1. We may therefore apply the induction hypothesis to u and conclude that it has the same AEG -state at the beginning of round t in both executions. Since AEG is deterministic, the message v has received from u in round t contains exactly the AEG -message sent from u to v in round t of E ⋆ . When AEG prescribes no message from u to v, u sends only its flag, and v treats this as receiving no message from u in the simulation. Since v completes round t with see-failure = false, it has received a message with see-failure = false from every neighbor in round t. Consequently, at the beginning of round t, the simulated AEG -state of v in E equals its state in E ⋆ . The AEG -messages received by v in that round are also identical in the two executions. Its deterministic state update gives the same AEG -state at the end of round t, proving the induction step. Finally, let v satisfy the assumptions of the lemma. The claim at t = T gives the same final AEG -state in both executions. Since degG (v) ≥ 3 and see-failure = false, Algorithm 6 outputs the simulated AEG -output at v, which is therefore its output in E ⋆ . Next, we show that the outputs of Algorithm 6 satisfy property (i) of Definition 6. Lemma 39. If a surviving node v obtains an output e in Algorithm 6, then e = ⊥ if deg(v) < 3, and e is an incident edge of v if deg(v) ≥ 3. Proof. If deg(v) < 3, then v outputs e = ⊥ by the description of Algorithm 6. In the remainder of the proof, we assume that deg(v) ≥ 3. If v completes Algorithm 6 with see-failure = false, then v outputs the edge it obtains from AEG . By Lemma 38, this edge is the output of v in E ⋆ , the fault-free execution of AEG . As deg(v) ≥ 3, the correctness of AEG implies that e is an incident edge of v. 64

Otherwise, v completes Algorithm 6 with see-failure = true. Then, in the round in which v set see-failure ← true, it also set e ← {u, v} for a neighbor u that has either crashed or sent see-failure = true to v. As v never modifies e afterwards, e = {u, v} is an incident edge of v. We now establish that adjacent nodes do not grab the same edge, which implies property (ii) of Definition 6. Lemma 40. Let u and v be two adjacent surviving nodes that output edges e and e′ respectively in Algorithm 6. Then, e ̸= e′ . Proof. We assume that e = e′ . Since both u and v output edges, Lemma 39 guarantees that this edge is incident to both u and v. This implies that e = e′ = {u, v}. First, assume that both u and v complete Algorithm 6 with see-failure = false. By the output rule of Algorithm 6, both u and v have degree at least three, since they output edges. By Lemma 38, e and e′ are the outputs of u and v in the fault-free execution of AEG , and e = e′ contradicts the correctness of AEG . Next, suppose that exactly one of u and v completes Algorithm 6 with see-failure = true, and assume without loss of generality that this is u. Since v survives and its flag remains false, u receives a message with flag false from v in every round. Thus u cannot select v when setting its flag to true, so its stored edge is not {u, v}. This contradicts e = {u, v}. Finally, suppose that both nodes complete Algorithm 6 with see-failure = true. Let t be the first round in which either node sets its flag to true, and assume without loss of generality that u does so in round t. At the beginning of that round, v still has flag false, even if both nodes change their flags in the same round. Since v survives, u receives its round-t message with flag false. Hence u cannot select v in round t. Its stored edge therefore differs from {u, v} and is never changed, contradicting e = {u, v}. Finally, we show that Algorithm 6 is a crash-tolerant edge grabbing algorithm, completing the proof of Theorem 6. Proof of Theorem 6. Let AEG be a deterministic T -round fault-free LOCAL algorithm for edge grabbing, and consider Algorithm 6 on an input graph G. The algorithm is deterministic, since AEG is deterministic and the smallest identifier determines the choice among eligible neighbors. Each of the T iterations uses one communication round: the flag and any simulated AEG -messages are sent together. Every surviving node completes these iterations and then produces an output using local computation. Consider any execution in the standard crash-fault model. By Lemma 39, every surviving node v outputs an edge of G incident to v if degG (v) ≥ 3, and outputs ⊥ otherwise. By Lemma 40, no edge is output by both surviving endpoints. Thus both properties of Definition 6 hold, proving crash-tolerant edge grabbing for any number of crashes.

8.2

Sinkless Orientation

We now focus on Theorem 5. The fault-free sinkless orientation problem requires every node to orient its incident edges so that the endpoints of each edge agree on its direction and every node of degree at least three has at least one outgoing edge. To specify these orientations, each node outputs a set O of directed edges, where (u, v) denotes {u, v} directed from u to v. Under crashes, we require these conditions only for surviving nodes. As in Section 8.1, all degrees and incident edges refer to the input graph G, including edges to nodes that crash.

65

Definition 7 (Crash-Tolerant Sinkless Orientation). An algorithm solves crash-tolerant sinkless orientation on G = (V, E) if the following conditions hold in every execution: (i) Every surviving node v outputs a set O consisting of exactly one orientation of each edge of G incident to v. (ii) Every surviving node v with degG (v) ≥ 3 has at least one outgoing edge in its output O, that is, (v, u) ∈ O for some u ∈ NG (v). (iii) If adjacent surviving nodes u and v output O and O′ , respectively, then (u, v) ∈ O if and only if (u, v) ∈ O′ . We first show how any deterministic T -round fault-free edge grabbing algorithm yields a deterministic (T + 1)-round crash-tolerant sinkless orientation algorithm. Given a deterministic T -round faultfree edge grabbing algorithm, Algorithm 6 makes it crash-tolerant without increasing its round complexity. We show how one additional round converts the resulting edge grabbing outputs into a crashtolerant sinkless orientation. We then prove Theorem 5 by obtaining the required fault-free edge grabbing algorithm from a fault-free sinkless orientation algorithm, without additional communication. Let AEG be any deterministic T -round fault-free LOCAL algorithm for edge grabbing. Each node runs Algorithm 6 with AEG as input for T rounds, obtaining an edge grabbing output e; by Theorem 6, this procedure is crash-tolerant. In round T + 1, each node sends e to every neighbor, with e = ⊥ if it grabbed no edge. A node v first orients its grabbed edge, if any, outwards. For each remaining incident edge {u, v}, it orients the edge from u to v if it receives an announcement from u that u grabbed {u, v}, and towards the endpoint with the smaller identifier otherwise. The pseudocode is given in Algorithm 7, and Lemma 41 establishes its correctness and round complexity. Algorithm 7 Crash-Tolerant Sinkless Orientation at node v Input: labeled star σv , algorithm AEG and its inputs, and number of rounds T . Output: a set O of directed edges orienting every edge incident to v. 1: Run Algorithm 6 with AEG and T , and obtain output e. 2: O ← ∅. 3: In round T + 1, send e to every neighbor and receive the delivered messages. 4: if e = {u, v} ̸= ⊥ then 5: Add (v, u) to O. 6: end if 7: for every incident edge {u, v} not yet oriented do 8: if v received {u, v} from u then 9: Add (u, v) to O. 10: else 11: Orient {u, v} towards the endpoint with the smaller identifier. 12: Add the oriented edge to O. 13: end if 14: end for 15: return O. Lemma 41. On graphs of arbitrary maximum degree, every deterministic T -round LOCAL algorithm for edge grabbing in the fault-free setting can be transformed into a deterministic (T + 1)-round LOCAL algorithm for crash-tolerant sinkless orientation in the standard crash-fault model for any number of crashes. 66

Proof. We first verify that Algorithm 7 satisfies the properties of Definition 7. For property (i), the output set O is initially empty. A surviving node v first orients its grabbed edge outwards, if it has one, and then orients each remaining incident edge exactly once in the loop. Only orientations of edges incident to v are added. Hence its output contains exactly one orientation of every incident edge of G. For property (ii), let v be a surviving node with degG (v) ≥ 3. By Theorem 6, it grabs an incident edge. This edge is oriented outwards and its orientation is never changed, so v has an outgoing edge in its output. For property (iii), let u and v be adjacent surviving nodes. By Definition 6 and Theorem 6, at most one of them grabs {u, v}. If neither does, neither announces this edge, and both orient it towards the endpoint with the smaller identifier. Otherwise, assume without loss of generality that v grabs {u, v}. Node v orients it from v to u and announces it in round T + 1. Since u and v survive the execution, u receives this announcement. Node u does not grab {u, v}, so it processes this edge in the loop and also orients it from v to u. Thus their orientations agree in both cases. This establishes that Algorithm 7 satisfies the properties of Definition 7. It remains to show that Algorithm 7 is a deterministic (T + 1)-round algorithm. By Theorem 6, Algorithm 6 is a deterministic T -round algorithm. Algorithm 7 adds one communication round followed by deterministic local computation, and hence is a deterministic (T + 1)-round algorithm, completing the proof. We may now conclude the section by presenting the proof of Theorem 5. Proof of Theorem 5. Let ASO be any deterministic T -round fault-free LOCAL algorithm for sinkless orientation. Define an edge grabbing algorithm AEG as follows. On an input graph G, each node first executes ASO . A node v with degG (v) ≥ 3 then outputs {u, v}, where u has the smallest identifier among the neighbors to which v has an outgoing edge. Every node of degree less than three outputs ⊥. In every fault-free execution, the correctness of ASO guarantees that each node of degree at least three has an outgoing edge, so its choice is well defined. If v selects {u, v}, then both endpoints orient this edge from v to u, and hence u cannot select it as an outgoing edge. Thus no edge is selected by both endpoints, and AEG solves fault-free edge grabbing. Since the selection rule is deterministic and requires only local computation, AEG is a deterministic T -round algorithm. Applying Lemma 41 to AEG yields a deterministic (T + 1)-round LOCAL algorithm satisfying Definition 7 in the standard crash-fault model for any number of crashes, proving the theorem.

9

Conclusions

We introduced consistent neighborhoods as a general primitive for simulating deterministic fault-free local algorithms in the presence of crash failures. For locally checkable problems, this simulation guarantees correctness at surviving nodes whose checking neighborhoods contain no crashed node, provided that the fault-free algorithm is correct on every subgraph of the input graph. We establish upper and lower bounds on the round complexity of constructing consistent neighborhoods. On general graphs, our O(n)-round upper bound is tight even for constant radius and a single crash. For every fixed ∆ ≥ 3, we show that exponential dependence on the radius is unavoidable in the worst case. When a crash bound f ≥ 1 is known, O(R · ∆ · f ) rounds suffice. Graphs of maximum degree two and graphs of girth greater than 2R admit O(R)-round algorithms. Our results also show that crash failures affect locally checkable problems differently across complexity regimes. On graphs of fixed maximum degree, every LCL problem with deterministic fault-free complexity O(log∗ n) retains this upper bound under crashes. In contrast, a problem with fault-free complexity Θ(log n) can require Θ(n) rounds. Sinkless orientation demonstrates 67

the potential of problem-specific transformations: any deterministic T -round fault-free algorithm yields a crash-tolerant algorithm using only one additional round, with guarantees that also apply to surviving nodes adjacent to crashes.

10

AI Methodology

The authors developed the main ideas and proof sketches for all results without assistance from large language models (LLMs). We subsequently used the ChatGPT models 5.6sol, 6 Astra, and 6.1sol to help formalize and, in some cases, simplify these ideas. LLMs also contributed concrete ideas in developing the formal arguments, notably the use of propagation graphs in the consistent-neighborhood upper bounds of Section 5.4. For writing and proof-checking throughout the paper, we used the ChatGPT models as well as Claude Fable 5.1 and Opus 5.5; the Claude models were used only for these tasks. LLMs were also used to create all figures. The authors take full responsibility for the correctness, originality, and integrity of all content, including material prepared with LLM assistance and the references.

68

References [AKY91]

Yehuda Afek, Shay Kutten, and Moti Yung. Memory-efficient self stabilizing protocols for general networks. In 4th International Workshop on Distributed Algorithms (WDAG 1990), volume 486 of Lecture Notes in Computer Science, pages 15–28, 1991. doi:10.1007/3-540-54099-7_2.

[AMPV22]

John Augustine, Anisur Rahaman Molla, Gopal Pandurangan, and Yadu Vasudev. Byzantine connectivity testing in the congested clique. In 36th International Symposium on Distributed Computing (DISC 2022), volume 246 of Leibniz International Proceedings in Informatics (LIPIcs), pages 7:1–7:21, 2022. doi:10.4230/LIPIcs.DISC.2022.7.

[APSV91]

Baruch Awerbuch, Boaz Patt-Shamir, and George Varghese. Self-stabilization by local checking and correction (extended abstract). In 32nd Annual Symposium on Foundations of Computer Science (FOCS 1991), pages 268–277, 1991. doi:10.1109/SFCS.1991.185378.

[APSVD94] Baruch Awerbuch, Boaz Patt-Shamir, George Varghese, and Shlomi Dolev. Self-stabilization by local checking and global reset (extended abstract). In 8th International Workshop on Distributed Algorithms (WDAG 1994), pages 326–339, 1994. doi:10.1007/BFb0020443. [AV91]

Baruch Awerbuch and George Varghese. Distributed program checking: a paradigm for building self-stabilizing distributed protocols (extended abstract). In 32nd Annual Symposium on Foundations of Computer Science (FOCS 1991), pages 258–267, 1991. doi:10.1109/SFCS.1991.185377.

[AW04]

Hagit Attiya and Jennifer Welch. Distributed Computing: Fundamentals, Simulations, and Advanced Topics. John Wiley & Sons, second edition, 2004. doi:10.1002/0471478210.

[BBC+ 19]

Alkida Balliu, Sebastian Brandt, Yi-Jun Chang, Dennis Olivetti, Mikaël Rabie, and Jukka Suomela. The distributed complexity of locally checkable problems on paths is decidable. In 38th ACM Symposium on Principles of Distributed Computing (PODC 2019), pages 262–271, 2019. Full version: https://arxiv.org/abs/1811.01672v2. doi:10.1145/3293611.3331606.

[BBOS18]

Alkida Balliu, Sebastian Brandt, Dennis Olivetti, and Jukka Suomela. Almost global problems in the LOCAL model. In 32nd International Symposium on Distributed Computing (DISC 2018), volume 121 of Leibniz International Proceedings in Informatics (LIPIcs), pages 9:1–9:16, 2018. doi:10.4230/LIPIcs.DISC.2018.9.

[BBOS20]

Alkida Balliu, Sebastian Brandt, Dennis Olivetti, and Jukka Suomela. How much does randomness help with locally checkable problems? In 39th ACM Symposium on Principles of Distributed Computing (PODC 2020), pages 299–308, 2020. doi:10.1145/3382734.3405715.

[BCHM+ 21] Alkida Balliu, Keren Censor-Hillel, Yannic Maus, Dennis Olivetti, and Jukka Suomela. Locally checkable labelings with small messages. In 35th International Symposium on Distributed Computing (DISC 2021), volume 209 of Leibniz International Proceedings in Informatics (LIPIcs), pages 8:1–8:18, 2021. doi:10.4230/LIPIcs.DISC.2021.8. 69

[BEG18]

Leonid Barenboim, Michael Elkin, and Uri Goldenberg. Locally-iterative distributed (∆ + 1)-coloring below Szegedy–Vishwanathan barrier, and applications to self-stabilization and to restricted-bandwidth models. In 37th ACM Symposium on Principles of Distributed Computing (PODC 2018), pages 437–446, 2018. doi:10.1145/3212734.3212769.

[BEIK24]

Shimon Bitton, Yuval Emek, Taisuke Izumi, and Shay Kutten. Fully adaptive self-stabilizing transformer for LCL problems, 2024. arXiv:2105.09756v3. First posted in 2021; revised September 2024. doi:10.48550/arXiv.2105.09756.

[Ben83]

Michael Ben-Or. Another advantage of free choice: Completely asynchronous agreement protocols (extended abstract). In 2nd ACM Symposium on Principles of Distributed Computing (PODC 1983), pages 27–30, 1983. doi:10.1145/800221.806707.

[BFdlV82]

Béla Bollobás and W. Fernandez de la Vega. The diameter of random regular graphs. Combinatorica, 2(2):125–134, 1982. doi:10.1007/BF02579310.

[BFH+ 16]

Sebastian Brandt, Orr Fischer, Juho Hirvonen, Barbara Keller, Tuomo Lempiäinen, Joel Rybicki, Jukka Suomela, and Jara Uitto. A lower bound for the distributed Lovász local lemma. In 48th Annual ACM Symposium on Theory of Computing (STOC 2016), pages 479–488, 2016. doi:10.1145/2897518.2897570.

[BFLM+ 24] Alkida Balliu, Pierre Fraigniaud, Patrick Lambein-Monette, Dennis Olivetti, and Mikaël Rabie. Asynchronous fault-tolerant distributed proper coloring of graphs. In 38th International Symposium on Distributed Computing (DISC 2024), volume 319 of Leibniz International Proceedings in Informatics (LIPIcs), pages 5:1–5:20, 2024. doi:10.4230/LIPIcs.DISC.2024.5. [BGK+ 25]

Alkida Balliu, Mohsen Ghaffari, Fabian Kuhn, Augusto Modanese, Dennis Olivetti, Mikaël Rabie, Jukka Suomela, and Jara Uitto. Shared randomness helps with local distributed problems. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025), volume 334 of Leibniz International Proceedings in Informatics (LIPIcs), pages 16:1–16:18, 2025. doi:10.4230/LIPIcs.ICALP.2025.16.

[BHK+ 18]

Alkida Balliu, Juho Hirvonen, Janne H. Korhonen, Tuomo Lempiäinen, Dennis Olivetti, and Jukka Suomela. New classes of distributed time complexity. In 50th Annual ACM Symposium on Theory of Computing (STOC 2018), pages 1307–1318, 2018. doi:10.1145/3188745.3188860.

[BHM+ 22]

Alkida Balliu, Juho Hirvonen, Darya Melnyk, Dennis Olivetti, Joel Rybicki, and Jukka Suomela. Local mending. In Structural Information and Communication Complexity: 29th International Colloquium (SIROCCO 2022), pages 1–20, 2022. doi:10.1007/978-3-031-09993-9_1.

[BKM19]

Philipp Bamberger, Fabian Kuhn, and Yannic Maus. Local distributed algorithms in highly dynamic networks. In IEEE International Parallel and Distributed Processing Symposium (IPDPS 2019), pages 33–42, 2019. doi:10.1109/IPDPS.2019.00015.

[Bol01]

Béla Bollobás. Random Graphs, volume 73 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, second edition, 2001. doi:10.1017/CBO9780511814068. 70

[Bra19]

Sebastian Brandt. An automatic speedup theorem for distributed problems. In 38th ACM Symposium on Principles of Distributed Computing (PODC 2019), pages 379–388, 2019. doi:10.1145/3293611.3331611.

[CDGF+ 19] Armando Castañeda, Carole Delporte-Gallet, Hugues Fauconnier, Sergio Rajsbaum, and Michel Raynal. Making local algorithms wait-free: the case of ring coloring. Theory of Computing Systems, 63(2):344–365, 2019. doi:10.1007/s00224-017-9772-y. [CDPR20]

Arnaud Casteigts, Swan Dubois, Franck Petit, and John M. Robson. Robustness: A new form of heredity motivated by dynamic networks. Theoretical Computer Science, 806:429–445, 2020. doi:10.1016/j.tcs.2019.08.008.

[CDRS26]

Antonio Cruciani, Avinandan Das, Alesya Raevskaya, and Jukka Suomela. It does not matter how you define locally checkable labelings, 2026. arXiv:2602.18188. To appear in DISC 2026. doi:10.48550/arXiv.2602.18188.

[CFP+ 23]

Armando Castañeda, Pierre Fraigniaud, Ami Paz, Sergio Rajsbaum, Matthieu Roy, and Corentin Travers. Synchronous t-resilient consensus in arbitrary graphs. Information and Computation, 292:105035, 2023. Preliminary version in SSS 2019, pp. 53–68. doi:10.1016/j.ic.2023.105035.

[Cha20]

Yi-Jun Chang. The complexity landscape of distributed locally checkable problems on trees. In 34th International Symposium on Distributed Computing (DISC 2020), volume 179 of Leibniz International Proceedings in Informatics (LIPIcs), pages 18:1–18:17, 2020. doi:10.4230/LIPIcs.DISC.2020.18.

[CHD18]

Keren Censor-Hillel and Michal Dory. Fast distributed approximation for TAP and 2-edge-connectivity. In 21st International Conference on Principles of Distributed Systems (OPODIS 2017), volume 95 of Leibniz International Proceedings in Informatics (LIPIcs), pages 21:1–21:20, 2018. doi:10.4230/LIPIcs.OPODIS.2017.21.

[CHDK+ 21] Keren Censor-Hillel, Neta Dafni, Victor I. Kolobov, Ami Paz, and Gregory Schwartzman. Fast deterministic algorithms for highly-dynamic networks. In 24th International Conference on Principles of Distributed Systems (OPODIS 2020), volume 184 of Leibniz International Proceedings in Informatics (LIPIcs), pages 28:1–28:16, 2021. doi:10.4230/LIPIcs.OPODIS.2020.28. [CHFGS25] Keren Censor-Hillel, Orr Fischer, Ran Gelles, and Pedro Soto. Two for one, one for all: Deterministic LDC-based robust computation in congested clique. In 39th International Symposium on Distributed Computing (DISC 2025), volume 356 of Leibniz International Proceedings in Informatics (LIPIcs), pages 20:1–20:19, 2025. doi:10.4230/LIPIcs.DISC.2025.20. [CHHK16]

Keren Censor-Hillel, Elad Haramaty, and Zohar Karnin. Optimal dynamic distributed MIS. In 35th ACM Symposium on Principles of Distributed Computing (PODC 2016), pages 217–226, 2016. doi:10.1145/2933057.2933083.

[CHS26]

Keren Censor-Hillel and Pedro Soto. Computing in a faulty congested clique. In 29th International Conference on Principles of Distributed Systems (OPODIS 2025), volume 361 of Leibniz International Proceedings in Informatics (LIPIcs), pages 10:1–10:19, 2026. doi:10.4230/LIPIcs.OPODIS.2025.10. 71

[CKOO23]

Bogdan S. Chlebus, Dariusz R. Kowalski, Jan Olkowski, and Jedrzej Olkowski. Disconnected agreement in networks prone to link failures. In Stabilization, Safety, and Security of Distributed Systems: 25th International Symposium (SSS 2023), volume 14310 of Lecture Notes in Computer Science, pages 207–222, 2023. doi:10.1007/978-3-031-44274-2_16.

[CKP19]

Yi-Jun Chang, Tsvi Kopelowitz, and Seth Pettie. An exponential separation between randomized and deterministic complexity in the LOCAL model. SIAM Journal on Computing, 48(1):122–143, 2019. doi:10.1137/17M1117537.

[CLPR09]

Shiri Chechik, M. Langberg, David Peleg, and Liam Roditty. Fault-tolerant spanners for general graphs. In 41st Annual ACM Symposium on Theory of Computing (STOC 2009), pages 435–444, 2009. doi:10.1145/1536414.1536475.

[CNnMR26] David Cifuentes-Núñez, Pedro Montealegre, and Ivan Rapaport. Recognizing hereditary properties in the presence of Byzantine nodes. In 29th International Conference on Principles of Distributed Systems (OPODIS 2025), volume 361 of Leibniz International Proceedings in Informatics (LIPIcs), pages 26:1–26:15, 2026. doi:10.4230/LIPIcs.OPODIS.2025.26. [CP17]

Yi-Jun Chang and Seth Pettie. A time hierarchy theorem for the LOCAL model. In 58th Annual Symposium on Foundations of Computer Science (FOCS 2017), pages 156–167, 2017. doi:10.1109/FOCS.2017.23.

[CPS21]

Johanne Cohen, Laurence Pilard, and Jonas Sénizergues. Self-stabilization and Byzantine tolerance for maximal independent set. In Stabilization, Safety, and Security of Distributed Systems (SSS 2021), pages 479–483, 2021. doi:10.1007/978-3-030-91081-5_33.

[DFPR25]

Swan Dubois, Laurent Feuilloley, Franck Petit, and Mikaël Rabie. When should you wait before updating?—toward a robustness refinement. Theoretical Computer Science, 1041:115220, 2025. Preliminary version in SAND 2023, LIPIcs 257, 7:1–7:15. doi:10.1016/j.tcs.2025.115220.

[DGFFR25] Carole Delporte-Gallet, Hugues Fauconnier, Pierre Fraigniaud, and Mikaël Rabie. Distributed computing in the asynchronous LOCAL model. Theoretical Computer Science, 1025:114952, 2025. doi:10.1016/j.tcs.2024.114952. [Dij74]

Edsger W. Dijkstra. Self-stabilizing systems in spite of distributed control. Communications of the ACM, 17(11):643–644, 1974. doi:10.1145/361179.361202.

[DIJM24]

Stéphane Devismes, David Ilcinkas, Colette Johnen, and Frédéric Mazoı̈t. Asynchronous self-stabilization made fast, simple, and energy-efficient. In 43rd ACM Symposium on Principles of Distributed Computing (PODC 2024), pages 538–548, 2024. doi:10.1145/3662158.3662803.

[DK11]

Michael Dinitz and Robert Krauthgamer. Fault-tolerant spanners: better and simpler. In 30th ACM Symposium on Principles of Distributed Computing (PODC 2011), pages 169–178, 2011. doi:10.1145/1993806.1993830.

[DLS13]

Shlomi Dolev, Omri Liba, and Elad M. Schiller. Self-stabilizing Byzantine resilient topology discovery and message delivery (extended abstract). In Networked Systems: 72

First International Conference (NETYS 2013), volume 7853 of Lecture Notes in Computer Science, pages 42–57, 2013. doi:10.1007/978-3-642-40148-0_4. [Dol82]

Danny Dolev. The Byzantine generals strike again. Journal of Algorithms, 3(1):14–30, 1982. doi:10.1016/0196-6774(82)90004-9.

[DS83]

Danny Dolev and H. Raymond Strong. Authenticated algorithms for Byzantine agreement. SIAM Journal on Computing, 12(4):656–666, 1983. doi:10.1137/0212045.

[DTZ12]

Swan Dubois, Sébastien Tixeuil, and Nini Zhu. problem. In Fun with Algorithms (FUN 2012), doi:10.1007/978-3-642-30347-0_13.

[FG26]

Orr Fischer and Ran Gelles. The task completion problem and its application to crash-resilient computation. In 45th ACM Symposium on Principles of Distributed Computing (PODC 2026), pages 348–359, 2026. doi:10.1145/3796701.3815916.

[Fis83]

Michael J. Fischer. The consensus problem in unreliable distributed systems (a brief survey). In Foundations of Computation Theory (FCT 1983), pages 127–140, 1983. doi:10.1007/3-540-12689-9_99.

[FL82]

Michael J. Fischer and Nancy A. Lynch. A lower bound for the time to assure interactive consistency. Information Processing Letters, 14(4):183–186, 1982. doi:10.1016/0020-0190(82)90033-3.

[FLMR22]

Pierre Fraigniaud, Patrick Lambein-Monette, and Mikaël Rabie. Fault tolerant coloring of the asynchronous cycle. In 36th International Symposium on Distributed Computing (DISC 2022), volume 246 of Leibniz International Proceedings in Informatics (LIPIcs), pages 23:1–23:22, 2022. doi:10.4230/LIPIcs.DISC.2022.23.

[FLP85]

Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson. Impossibility of distributed consensus with one faulty process. Journal of the ACM, 32(2):374–382, 1985. doi:10.1145/3149.214121.

[FNP25]

Pierre Fraigniaud, Minh Hang Nguyen, and Ami Paz. Agreement tasks in fault-prone synchronous networks of arbitrary structure. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025), volume 327 of Leibniz International Proceedings in Informatics (LIPIcs), pages 34:1–34:21, 2025. Full version: https://arxiv.org/abs/2410.21538. doi:10.4230/LIPIcs.STACS.2025.34.

[GKM17]

Mohsen Ghaffari, Fabian Kuhn, and Yannic Maus. On the complexity of local distributed graph problems. In 49th Annual ACM Symposium on Theory of Computing (STOC 2017), pages 784–797, 2017. doi:10.1145/3055399.3055471.

[GP16]

Mohsen Ghaffari and Merav Parter. Near-optimal distributed algorithms for faulttolerant tree structures. In 28th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2016), pages 387–396, 2016. doi:10.1145/2935764.2935795.

[GS17]

Mohsen Ghaffari and Hsin-Hao Su. Distributed degree splitting, edge coloring, and orientations. In 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), pages 2505–2523, 2017. doi:10.1137/1.9781611974782.166.

73

The Byzantine brides pages 107–118, 2012.

[Had87]

Vassos Hadzilacos. Connectivity requirements for Byzantine agreement under restricted types of failures. Distributed Computing, 2(2):95–103, 1987. doi:10.1007/BF01667081.

[HN25]

Adar Hadad and Moni Naor. Shared randomness in locally checkable problems: The role of computational assumptions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025), volume 353 of Leibniz International Proceedings in Informatics (LIPIcs), pages 50:1–50:23, 2025. doi:10.4230/LIPIcs.APPROX/RANDOM.2025.50.

[JM09]

Arshad Jhumka and Luca Mottola. On consistent neighborhood views in wireless sensor networks. In 28th IEEE International Symposium on Reliable Distributed Systems (SRDS 2009), pages 199–208, 2009. doi:10.1109/SRDS.2009.19.

[JM16]

Arshad Jhumka and Luca Mottola. Neighborhood view consistency in wireless sensor networks. ACM Transactions on Sensor Networks, 12(3):19:1–19:41, 2016. doi:10.1145/2901296.

[KP95]

Shay Kutten and David Peleg. Tight fault locality (extended abstract). In 36th Annual Symposium on Foundations of Computer Science (FOCS 1995), pages 704–713, 1995. doi:10.1109/SFCS.1995.492672.

[KW13]

Michael König and Roger Wattenhofer. On local fixing. In Principles of Distributed Systems (OPODIS 2013), pages 191–205, 2013. doi:10.1007/978-3-319-03850-6_14.

[LF82]

Leslie Lamport and Michael J. Fischer. Byzantine generals and transaction commit protocols. Technical Report Op. 62, SRI International, April 1982. URL: https://www.microsoft.com/en-us/research/wp-content/uploads/2016/12/ Byzantine-Generals-and-Transaction-Commit-Protocols.pdf.

[Lin92]

Nathan Linial. Locality in distributed graph algorithms. SIAM Journal on Computing, 21(1):193–201, 1992. doi:10.1137/0221015.

[LSW09]

Christoph Lenzen, Jukka Suomela, and Roger Wattenhofer. Local algorithms: Self-stabilization on speed. In Stabilization, Safety, and Security of Distributed Systems (SSS 2009), pages 17–34, 2009. doi:10.1007/978-3-642-05118-0_2.

[Lyn96]

Nancy A. Lynch. Distributed Algorithms. Morgan Kaufmann, San Francisco, CA, 1996.

[MNS95]

Alain Mayer, Moni Naor, and Larry Stockmeyer. Local computations on static and dynamic graphs. In 3rd Israel Symposium on the Theory of Computing and Systems (ISTCS 1995), pages 268–278, 1995. doi:10.1109/ISTCS.1995.377023.

[MSV23]

Darya Melnyk, Jukka Suomela, and Neven Villani. Mending partial solutions with few changes. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022), volume 253 of Leibniz International Proceedings in Informatics (LIPIcs), pages 21:1–21:17, 2023. doi:10.4230/LIPIcs.OPODIS.2022.21.

[NA02]

Mikhail Nesterenko and Anish Arora. Tolerance to unbounded Byzantine faults. In 21st IEEE Symposium on Reliable Distributed Systems (SRDS 2002), pages 22–29, 2002. doi:10.1109/RELDIS.2002.1180170.

[NS95]

Moni Naor and Larry Stockmeyer. What can be computed locally? SIAM Journal on Computing, 24(6):1259–1277, 1995. doi:10.1137/S0097539793254571. 74

[NT06]

Mikhail Nesterenko and Sébastien Tixeuil. Discovering network topology in the presence of Byzantine faults. In Structural Information and Communication Complexity: 13th International Colloquium (SIROCCO 2006), volume 4056 of Lecture Notes in Computer Science, pages 212–226, 2006. Journal version: IEEE Transactions on Parallel and Distributed Systems 20(12):1777–1789 (2009), doi: 10.1109/TPDS.2009.25. doi:10.1007/11780823_17.

[Par20]

Merav Parter. Distributed constructions of dual-failure fault-tolerant distance preservers. In 34th International Symposium on Distributed Computing (DISC 2020), volume 179 of Leibniz International Proceedings in Informatics (LIPIcs), pages 21:1–21:17, 2020. doi:10.4230/LIPIcs.DISC.2020.21.

[Par22]

Merav Parter. Nearly optimal vertex fault-tolerant spanners in optimal time: sequential, distributed, and parallel. In 54th Annual ACM Symposium on Theory of Computing (STOC 2022), pages 1080–1092, 2022. doi:10.1145/3519935.3520047.

[Pel00]

David Peleg. Distributed Computing: A Locality-Sensitive Approach. Monographs on Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics, 2000. doi:10.1137/1.9780898719772.

[PPS16]

Merav Parter, David Peleg, and Shay Solomon. Local-on-average distributed tasks. In 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016), pages 220–239, 2016. doi:10.1137/1.9781611974331.ch17.

[PSL80]

Marshall Pease, Robert Shostak, and Leslie Lamport. Reaching agreement in the presence of faults. Journal of the ACM, 27(2):228–234, 1980. doi:10.1145/322186.322188.

[Rab83]

Michael O. Rabin. Randomized Byzantine generals. In 24th Annual Symposium on Foundations of Computer Science (FOCS 1983), pages 403–409, 1983. doi:10.1109/SFCS.1983.48.

[RG20]

Václav Rozhon and Mohsen Ghaffari. Polylogarithmic-time deterministic network decomposition and distributed derandomization. In 52nd Annual ACM Symposium on Theory of Computing (STOC 2020), pages 350–363, 2020. doi:10.1145/3357713.3384298.

[Tur19]

Volker Turau. Making randomized algorithms self-stabilizing. In Structural Information and Communication Complexity (SIROCCO 2019), pages 309–324, 2019. doi:10.1007/978-3-030-24922-9_21.

[TV15]

Lewis Tseng and Nitin Vaidya. Crash-tolerant consensus in directed graphs, 2015. arXiv:1412.8532v2.

[WW20]

Ye Wang and Roger Wattenhofer. Asynchronous Byzantine agreement in incomplete networks. In 2nd ACM Conference on Advances in Financial Technologies (AFT 2020), pages 178–188, 2020. doi:10.1145/3419614.3423250.

75

Related documents

• Safe Hypergraph Contraction via Capacity-Aware Repair Certificates#1156949
• Constant-Factor Local Approximation for Bipartite Densest Subgraph#1388680
• SOLANET: Distributed Neighbor Graph Construction on GPU-Accelerated Systems#238582
• A Fundamental Limit in Decentralized Decision-Making#984397
• Dynamic Conflict Clustering with Lightweight Learning and Strategic Repair for Distributed Constraint Satisfaction#1326908