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

Orr Fischer, Merav Parter

TL;DR

This paper introduces a breakthrough in resilient distributed computing by shifting the focus from the total number of faults to the degree of faults per node. By doing so, the authors provide "compilers" that allow standard all-to-all communication protocols to survive nearly quadratic edge corruptions ($O(n^2)$) with only constant-round overhead—essentially providing massive fault tolerance "for free."

What Problem Does This Paper Address?

In distributed networks, "all-to-all" communication (where every node needs to send a unique message to every other node) is a fundamental building block. Traditionally, researchers have studied resilience against Byzantine adversaries who can corrupt a fixed number of edges, $f$. However, if $f$ is small (e.g., linear in the number of nodes $n$), a clever adversary can completely isolate a single node by corrupting all its incident edges.

The authors tackle a more robust model: the $\alpha$-Byzantine Degree (BD) adversary. Instead of a global budget $f$, the adversary can corrupt an $\alpha$-fraction of the edges incident to every node in every round. Crucially, this adversary is "mobile," meaning it can choose a different set of edges to corrupt in each round. This model allows for up to $O(n^2)$ total corruptions across the network, a much harsher environment than previous models could handle efficiently.

Methods

The authors develop a suite of "resilient compilers" using several sophisticated tools from theoretical computer science:

  1. Resilient Super-Message Routing: The core primitive. It treats large messages (super-messages) by encoding them with Error-Correcting Codes (ECC) and distributing the bits across a subset of nodes defined by Cover-Free Families. This ensures that even if an adversary corrupts many edges, enough "clean" bits reach the destination to allow for successful decoding.
  2. Locally Decodable Codes (LDCs): To handle adaptive adversaries (who can choose which edges to corrupt based on the history of the protocol), the authors use LDCs. These allow a node to recover a specific bit of a message by querying only a small, random subset of other nodes, making it impossible for the adversary to predict and block the necessary information.
  3. Sparse Recovery Sketches: These are used to "clean" the received data. Nodes use sketches to identify which specific messages were corrupted and apply corrections without needing to re-transmit everything.
  4. Deterministic Compilers: For scenarios where randomness isn't available, they provide algorithms using a recursive matching pattern that completes in $O(\log n)$ rounds.

Datasets

Not discussed in the paper. As a theoretical work in distributed algorithms, the results are proven mathematically rather than evaluated on empirical datasets.

Key Insights and Ideas

  • From Cardinality to Degree: The most significant "aha" moment is realizing that the bottleneck for resilience isn't the total number of faults in the network, but the congestion of faults at any single node. By limiting the faulty degree, you can tolerate a massive number of total errors.
  • Information Concentration: To bypass the bandwidth limits of the "Congested Clique" model, the algorithms concentrate information on a few key nodes. By using ECCs, they ensure that the "truth" is distributed such that no local adversary can hide it.
  • LDCs as a Shield against Adaptivity: Adaptive adversaries are notoriously difficult because they "rush" to corrupt the most important edges. By using LDCs, the protocol makes every edge equally (un)important until the very last moment, effectively neutralizing the adversary's ability to strategize.

Key Results

The paper provides several "compilers" that simulate one round of a fault-free protocol in a faulty environment:

  • Non-Adaptive Adversary: Achieves $O(1)$ round simulation for a constant fraction $\alpha$ of edge corruptions. This supports a total of $\Omega(n^2)$ corruptions.
  • Adaptive Adversary: Achieves $O(1)$ round simulation for $\alpha = 1/n^{o(1)}$. This is a major improvement over prior work (Fischer and Parter, 2023), which required $poly \log n$ rounds and could not support $\alpha$ values this high.
  • Deterministic Results: They provide the first deterministic $O(1)$ round simulation for $\alpha = O(1/\sqrt{n})$, proving that randomness is helpful but not always strictly necessary for high resilience.

Limitations and Future Work

  • The Value of $\alpha$: In the adaptive setting, the fraction of tolerable faults $\alpha$ is tied to the state-of-the-art in Locally Decodable Codes. As LDC research progresses, the $\alpha$ in this paper could potentially be improved to a larger constant.
  • Node vs. Edge Faults: This work focuses primarily on edge corruptions. While some results might extend to node failures, a mobile adversary that can corrupt nodes presents a different set of challenges regarding internal state persistence.
  • Computational Complexity: While the round complexity (communication) is optimized to $O(1)$, the local computation required for some of the more complex codes and sketches can be high, though the authors note it remains polynomial. Exploring more computationally efficient versions of these resilient routes is a natural next step.

Summary updated

BibTeX
@inproceedings{fischer2025all,
  author = {Orr Fischer and Merav Parter},
  title = {{All-to-All Communication with Mobile Edge Adversary: Almost Linearly More Faults, For Free}},
  booktitle = {PODC},
  year = {2025},
  doi = {10.1145/3732772.3733536},
}
Figure