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.
- 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.
- 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.
- 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.
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.
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