Moshpit SGD: Communication-Efficient Decentralized Training on Heterogeneous Unreliable Devices

Max Ryabinin, Eduard Gorbunov, Vsevolod Plokhotnyuk, Gennady Pekhimenko

Abstract

Distributed deep learning on unreliable, heterogeneous hardware faces a trade-off between the efficiency of All-Reduce and the robustness of gossip protocols. This paper presents Moshpit SGD, a decentralized training method that utilizes a Distributed Hash Table (DHT) for dynamic peer grouping. By performing iterative All-Reduce within these shifting groups, Moshpit SGD achieves exponential convergence and high fault tolerance. Experimental results on ImageNet and ALBERT-large demonstrate up to 1.5x speedups on preemptible cloud instances compared to traditional data-parallel training.

Introduction

Distributed deep learning usually relies on All-Reduce protocols (like Ring All-Reduce) to synchronize gradients across workers. While highly efficient, these protocols are "weakest-link" systems: if a single node lags or fails, the entire training process stalls. This makes them unsuitable for "unreliable" environments like federated learning or clusters of cheap, preemptible cloud instances.

The traditional alternative is gossip-based averaging, where nodes only talk to a few neighbors. Gossip is robust to failures but is communication-heavy and slow to propagate information across the whole network. Moshpit SGD aims to bridge this gap, providing the speed of All-Reduce with the resilience of decentralized gossip.

Moshpit All-Reduce: Dynamic Decentralized Averaging

The core innovation is Moshpit All-Reduce, an iterative protocol where workers perform averaging in small, independent, and dynamically changing groups.

  1. Decentralized Matchmaking: Instead of a fixed communication graph, workers use a Distributed Hash Table (DHT) to find peers. Each worker computes a "group key" based on its current iteration and a virtual grid coordinate.
  2. Butterfly All-Reduce: Once a small group (e.g., 32 nodes) is formed via the DHT, they perform a standard Butterfly All-Reduce. This is much faster than gossiping because it uses optimal bandwidth within the group.
  3. Dynamic Re-grouping: In the next round, workers change their group keys to ensure they meet new peers. This "shuffling" ensures that local information spreads exponentially fast across the entire swarm.
Example averaging order for 9 peers in 2 rounds. Peers are split into groups that run All-Reduce in parallel.

To handle heterogeneous devices (varying from 100Mb/s to 1Gb/s), the protocol uses a linear programming approach to assign smaller chunks of data to slower workers, preventing them from bottlenecking their local group.

Theoretical and Practical Insights

  • Exponential Convergence: Unlike standard gossip, which converges linearly relative to the network's spectral gap, Moshpit All-Reduce converges exponentially. This means it reaches a global consensus much faster as the number of total peers grows.
  • Equivalence to Local SGD: The authors prove that Moshpit SGD is theoretically equivalent to Centralized (Local) SGD, ensuring that the decentralized nature doesn't sacrifice final model quality.
  • Exploiting Preemptible Nodes: By being fault-tolerant, researchers can use "spot" or "preemptible" instances that are up to 3x cheaper than dedicated nodes, even if those instances are frequently killed and restarted.

Experimental Evaluation

The authors evaluated Moshpit SGD on major benchmarks including ImageNet (ResNet-50) and BookCorpus (ALBERT-large).

  • ResNet-50 on ImageNet: Moshpit SGD reached 75% accuracy 1.3x faster than Stochastic Gradient Push (a state-of-the-art gossip method) in a heterogeneous setup with 64 servers.
  • ALBERT-large Pretraining: Using a fleet of 66 preemptible GPUs spread across three continents, Moshpit SGD was 1.5x faster than traditional data-parallel training (AR-SGD).
  • Fault Tolerance: In synthetic tests, while standard All-Reduce failed completely with even a 0.5% node failure rate, Moshpit All-Reduce continued to converge reliably.
Convergence of averaging protocols with a 0.5% node failure rate (p=0.005). Moshpit Averaging remains robust while standard All-Reduce fails.

Conclusion and Future Work

Moshpit SGD provides a robust framework for training large models on the "wild" internet. While highly effective, future work could address the latency added by DHT matchmaking in high-speed environments and explore combining the protocol with gradient compression techniques like quantization. Additionally, "topology awareness"—preferring to group nodes in the same data center before grouping across oceans—remains a promising direction for further optimization.

Summary updated

BibTeX
@inproceedings{ryabinin2021moshpit,
  author = {Max Ryabinin and Eduard Gorbunov and Vsevolod Plokhotnyuk and Gennady Pekhimenko},
  title = {{Moshpit SGD: Communication-Efficient Decentralized Training on Heterogeneous Unreliable Devices}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=cwWfDHYpb1z},
}
Figure