Distributed Learning over Unreliable Networks

Chen Yu, Hanlin Tang, Cédric Renggli, Simon Kassing, Ankit Singla, Dan Alistarh, Ce Zhang, Ji Liu

Most distributed training systems assume a perfectly reliable network: if a worker machine sends a gradient or a model update, the system assumes it must arrive. If it doesn't, the system typically stalls or retransmits, leading to significant communication bottlenecks.

However, modern machine learning algorithms are known to be inherently noise-tolerant. This raises a provocative question: Can we design a system that is intentionally tolerant of network unreliability? If distributed training could allow a 1% or 10% packet drop rate without ruining the model, we could treat ML traffic as "low priority," freeing up critical network bandwidth for latency-sensitive applications like real-time web services.

The Reliable Parameter Server (RPS) Algorithm

To address this, researchers introduce the RPS (Reliable Parameter Server) algorithm. RPS adapts the standard AllReduce communication pattern (specifically the Reduce-Scatter and All-Gather steps) to handle packet loss gracefully.

RPS Communication Architecture

The algorithm operates in three main steps:

  1. Model Partitioning: The model is split into $n$ blocks, with each worker "owning" the averaging process for one specific block.
  2. RPS Reduce-Scatter: Workers attempt to send their local blocks to the designated "owner" worker. If a packet is dropped, the owner simply averages the subset of blocks that actually arrived.
  3. RPS All-Gather: The owners broadcast the new averages back to all workers. If a worker fails to receive an updated block, it simply keeps its old local version of that block for the next iteration.

The core contribution of this work is a novel theoretical analysis proving that this "faulty" communication still achieves a convergence rate of $O(1/\sqrt{nT})$, which perfectly matches the rate of centralized SGD on a flawless network.

Key Insights: Why Does This Work?

  • Model vs. Gradient Averaging: The paper highlights that model averaging (averaging the actual weights) is far superior to gradient averaging in unreliable settings. In gradient averaging, a lost packet is a permanent error that accumulates over time. In model averaging, the system is self-correcting; even if a worker misses an update, it will likely catch the next one and be "pulled" back toward the global consensus.
  • Strength in Numbers: Counter-intuitively, the negative impact of packet drops actually diminishes as the number of parameter servers increases. Larger clusters are more robust to individual communication failures.
  • The "Scavenger" Strategy: By allowing ML traffic to be lossy, it can be treated as "scavenger" traffic in a data center. It only consumes bandwidth that isn't actively needed by high-priority, delay-sensitive tasks.

Empirical Results

The researchers validated RPS using standard benchmarks, including image classification (ResNet-20 and ResNet-110 on CIFAR-10) and Natural Language Understanding (LSTM on the ATIS corpus).

Training loss across different models and arrival rates

The results demonstrate remarkable resilience:

  • Negligible Accuracy Loss: On ResNet-110, dropping 1% of packets had no impact on final training loss. Even at a 10% drop rate (90% arrival), the training loss only increased by a tiny margin (approx. 0.01).
  • Linear Speedup: The algorithm maintains "linear speedup," meaning that adding more workers continues to reduce training time proportionally, despite the unreliable network.
  • System-Wide Benefits: In data center simulations, allowing a 10% drop rate for ML training allowed a colocated web service to run 1.2x faster. This proves that network unreliability isn't just a theoretical curiosity—it’s a practical tool for better resource management.

Limitations and Future Work

While promising, the current theoretical proof focuses on a constant learning rate, which causes the model to converge to a "ball" around the optimum rather than a single point. Future work could explore more complex decaying schedules. Additionally, the analysis assumes packet drops are independent and identically distributed (I.I.D.). In real-world networks, drops often happen in "bursts" due to temporary congestion, which might affect the algorithm differently. Finally, future systems could automatically tune hyperparameters (like the learning rate) based on the observed real-time packet drop rate to continuously optimize performance.

Summary updated

Abstract

Most of today’s distributed machine learning systems assume <em>reliable networks</em>: whenever two machines exchange information (e.g., gradients or models), the network should guarantee the deli...
BibTeX
@inproceedings{yu2019distributed,
  author = {Chen Yu and Hanlin Tang and Cédric Renggli and Simon Kassing and Ankit Singla and Dan Alistarh and Ce Zhang and Ji Liu},
  title = {{Distributed Learning over Unreliable Networks}},
  booktitle = {International Conference on Machine Learning},
  year = {2019},
  url = {https://openreview.net/forum?id=BJ-zVoZd-B},
}

Loading related content...

Figure