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

Abstract

Training deep neural networks on large datasets can often be accelerated by using multiple compute nodes. This approach, known as distributed training, can utilize hundreds of computers via specialized message-passing protocols such as Ring All-Reduce. However, running these protocols at scale requires reliable high-speed networking that is only available in dedicated clusters. In contrast, many real-world applications, such as federated learning and cloud-based distributed training, operate on unreliable devices with unstable network bandwidth. As a result, these applications are restricted to using parameter servers or gossip-based averaging protocols. In this work, we lift that restriction by proposing Moshpit All-Reduce — an iterative averaging protocol that exponentially converges to the global average. We demonstrate the efficiency of our protocol for distributed optimization with strong theoretical guarantees. The experiments show 1.3x speedup for ResNet-50 training on ImageNet compared to competitive gossip-based strategies and 1.5x speedup when training ALBERT-large on preemptible compute nodes.
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