2025/05/09 by Orr Fischer, Fischer, Orr, Merav Parter +1 · 1 citation
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Distributed #Distributed systems and fault tolerance #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2505.05735
openalex publication_date 2025/05/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Resilient computation in all-to-all-communication models has attracted tremendous attention over the years. Most of these works assume the classical faulty model which restricts the total number of corrupted edges (or vertices) by some integer fault parameter f. A recent work by [Bodwin, Haeupler and Parter, SODA 2024] introduced a stronger notion of fault-tolerance, in the context of graph sparsification, which restricts the degree of the failing edge set F, rather than its cardinality. For a subset of faulty edges F, the faulty-degree deg(F) is the largest number of faults in F incident to any given node. In this work, we study the communication aspects of this faulty model which allows us to handle almost linearly more edge faults (possibly quadratic), with no extra cost. Our end results are general compilers that take any Congested Clique algorithm and simulate it, in a round by round manner, in the presence of a α-Byzantine mobile adversary that controls a α-fraction of the edges incident to each node in the fully connected network. For every round i, the mobile adversary is allowed to select a distinct set of corrupted edges Fi under the restriction that deg(Fi)≤ αn. In the non-adaptive setting, the Fi sets are selected at the beginning of the simulation, while in the adaptive setting, these edges can be chosen based on the entire history of the protocol up to round i. We show general compilers for the non-adaptive, adaptive, and deterministic settings. A key component of our algorithms is a new resilient routing scheme which may be of independent interest. Our approach is based on a combination of techniques, including error-correcting-code, locally decodable codes, cover-free families, and sparse recovery sketches.