All-to-All Communication with Mobile Edge Adversary: Almost Linearly More Faults, For Free

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.