Two for One, One for All: Deterministic LDC-Based Robust Computation in Congested Clique

Keren Censor-Hillel, Orr Fischer, Ran Gelles, Pedro Soto

This paper, presented by researchers from Technion, Bar-Ilan University, and Virginia Tech, tackles a fundamental challenge in distributed computing: how to keep a network running even when an adversary is actively knocking nodes offline.

TL;DR

The authors present a deterministic "compiler" that makes any algorithm in the Congested Clique model resilient to a constant fraction of adversarial node crashes. By using Locally Decodable Codes (LDCs) and a novel "adaptive doubling" strategy, they ensure that a $T$-round algorithm can still finish in $T^2 n^{o(1)}$ rounds, even if nearly half the network disappears.

What Problem Does This Paper Address?

In distributed computing, the Congested Clique model represents a network of $n$ nodes where everyone can talk to everyone else, but bandwidth is strictly limited (usually $O(\log n)$ bits per message). While we have very fast algorithms for this model, they are typically "brittle"—if a single node crashes, its local data is lost, and the entire computation might fail.

The challenge is even harder when the crashes are adversarial. Instead of random hardware failures, imagine an intelligent attacker who knows your algorithm and crashes exactly the nodes that are most critical to the next step. Previous solutions to this problem relied on standard error-correcting codes, which required nodes to download massive amounts of data to recover a single lost bit, leading to "traffic jams" (congestion) that slowed the network to a crawl.

Methods

The researchers move away from traditional block codes and instead utilize Locally Decodable Codes (LDCs).

  1. LDCs for Bandwidth Efficiency: Unlike standard codes, LDCs allow a node to recover a specific piece of missing information by querying only a tiny, sub-polynomial number of other nodes. This drastically reduces the communication overhead.
  2. Deterministic Derandomization: LDCs are usually randomized. However, in a crash-fault scenario, the "erasure" locations are known (everyone knows which nodes didn't send a message). The authors show how to deterministically pick query sets that avoid crashed nodes while ensuring no single healthy node is overwhelmed with requests (load balancing).
  3. The "Two for One" Doubling Strategy: To counter an adversary who targets the specific nodes being queried, the authors use an adaptive strategy. If a decoding attempt fails because the adversary crashed the target nodes, the system doubles the number of attempts. If the "decoder" node itself is crashed, it is replaced by two new nodes. Because the adversary has a finite "budget" of nodes they can crash ($\alpha n$), this doubling eventually forces the adversary to run out of moves before the algorithm runs out of nodes.

Datasets

Not discussed in the paper. As a theoretical work in distributed algorithms, the results are established through mathematical proofs and complexity analysis rather than empirical testing on specific datasets.

Key Insights and Ideas

  • LDCs as a Congestion Tool: The most striking insight is that LDCs aren't just for data integrity; they are a powerful tool for managing bandwidth in a distributed setting. By limiting how many nodes you need to talk to, you prevent the "all-to-all" communication bottlenecks typical of robust systems.
  • Knowledge is Power: Because crash faults are "erasures" (we know what is missing) rather than "errors" (maliciously altered data), the authors can transform randomized sampling into a deterministic schedule.
  • Resource Exhaustion: The "doubling" mechanism creates a mathematical trap for the adversary. Every time the adversary successfully blocks a computation step, they have to spend an exponentially increasing portion of their crash budget to keep blocking it in the next round.

Key Results

  • The Compiler: The authors prove that any $T$-round Congested Clique algorithm can be transformed into a robust version that completes in $T^2 n^{o(1)}$ rounds.
  • Circuit Robustness: For a general circuit of depth $d$, width $\omega$, and gate fan $\Delta$, the robust round complexity is: $$d \cdot \left\lceil \frac{\omega}{n^2} + \frac{\Delta}{n} \right\rceil \cdot 2^{O(\sqrt{\log n} \log \log n)}$$
  • High Resilience: The system remains functional even if a constant fraction $\alpha < 1$ (e.g., 10%, 20%, or even 49%) of the nodes are crashed by an adversary.

Limitations and Future Work

  • The $T^2$ Overhead: While $T^2 n^{o(1)}$ is a major theoretical breakthrough, the quadratic jump in rounds means that for very long-running algorithms, the overhead could still be significant in practice.
  • Crash vs. Byzantine Faults: This paper specifically handles crash faults (nodes stop talking). It does not address Byzantine faults, where nodes stay online but send malicious, lying messages. Handling Byzantine adversaries with LDCs would likely require much more complex "locally correctable" properties.
  • Initialization: The authors note that if a node crashes before the very first round, its input is lost forever. They suggest starting with "encoded inputs" to bypass this, but in a real-world scenario, the initial distribution of data remains a delicate phase.

Summary updated

BibTeX
@inproceedings{censorhillel2025two,
  author = {Keren Censor-Hillel and Orr Fischer and Ran Gelles and Pedro Soto},
  title = {{Two for One, One for All: Deterministic LDC-Based Robust Computation in Congested Clique}},
  booktitle = {DISC},
  year = {2025},
  doi = {10.4230/lipics.disc.2025.20},
}

Loading related content...

Figure