# Gradient Coding with Dynamic Clustering for Straggler-Tolerant Distributed Learning

arXiv: https://arxiv.org/abs/2103.01206 · HTML: https://mlsanity.com/paper/2103.01206/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 49 references that are in the map.
- First posted on arXiv 1 Mar 2021.

## Builds on (most cited first, 28 of 28)

- [Revisiting Distributed Synchronous SGD](https://mlsanity.com/paper/1702.05800/) (2017)
- [Speeding Up Distributed Machine Learning Using Codes](https://mlsanity.com/paper/1512.02673/) (2015)
- [Slow and Stale Gradients Can Win the Race: Error-Runtime Trade-offs in Distributed SGD](https://mlsanity.com/paper/1803.01113/) (2018)
- [Polynomial Codes: an Optimal Design for High-Dimensional Coded Matrix Multiplication](https://mlsanity.com/paper/1705.10464/) (2017)
- [On the Optimal Recovery Threshold of Coded Matrix Multiplication](https://mlsanity.com/paper/1801.10292/) (2018)
- [Communication-Computation Efficient Gradient Coding](https://mlsanity.com/paper/1802.03475/) (2018)
- [Gradient Coding from Cyclic MDS Codes and Expander Graphs](https://mlsanity.com/paper/1707.03858/) (2017)
- [Straggler-aware Distributed Learning: Communication Computation Latency Trade-off](https://mlsanity.com/paper/2004.04948/) (2020)
- [Improving Distributed Gradient Descent Using Reed-Solomon Codes](https://mlsanity.com/paper/1706.05436/) (2017)
- [Gradient Coding with Clustering and Multi-message Communication](https://mlsanity.com/paper/1903.01974/) (2019)
- [Near-Optimal Straggler Mitigation for Distributed Gradient Methods](https://mlsanity.com/paper/1710.09990/) (2017)
- [LAGC: Lazily Aggregated Gradient Coding for Straggler-Tolerant and Communication-Efficient Distributed Learning](https://mlsanity.com/paper/1905.09148/) (2019)
- [A Unified Coded Deep Neural Network Training Strategy Based on Generalized PolyDot Codes for Matrix Multiplication](https://mlsanity.com/paper/1811.10751/) (2018)
- [A Survey of Coded Distributed Computing](https://mlsanity.com/paper/2008.09048/) (2020)
- [Anytime Stochastic Gradient Descent: A Time to Hear from all the Workers](https://mlsanity.com/paper/1810.02976/) (2018)
- [Heterogeneity-aware Gradient Coding for Straggler Tolerance](https://mlsanity.com/paper/1901.09339/) (2019)
- [Timely Distributed Computation with Stragglers](https://mlsanity.com/paper/1910.03564/) (2019)
- [Speeding Up Distributed Gradient Descent by Utilizing Non-persistent Stragglers](https://mlsanity.com/paper/1808.02240/) (2018)
- [Gradient Coding Based on Block Designs for Mitigating Adversarial Stragglers](https://mlsanity.com/paper/1904.13373/) (2019)
- [Distributed Gradient Descent with Coded Partial Gradient Computations](https://mlsanity.com/paper/1811.09271/) (2018)
- [Age-Based Coded Computation for Bias Reduction in Distributed Learning](https://mlsanity.com/paper/2006.01816/) (2020)
- [Hierarchical Coding for Distributed Computing](https://mlsanity.com/paper/1801.04686/) (2018)
- [Polynomially Coded Regression: Optimal Straggler Mitigation via Data Encoding](https://mlsanity.com/paper/1805.09934/) (2018)
- [Bivariate Polynomial Coding for Efficient Distributed Matrix Multiplication](https://mlsanity.com/paper/2001.07227/) (2020)
- [Gradient Coding with Dynamic Clustering for Straggler Mitigation](https://mlsanity.com/paper/2011.01922/) (2020)
- [Robust Gradient Descent via Moment Encoding with LDPC Codes](https://mlsanity.com/paper/1805.08327/) (2018)
- [On the Effect of Task-to-Worker Assignment in Distributed Computing Systems with Stragglers](https://mlsanity.com/paper/1808.02838/) (2018)
- [Age of Information with Gilbert-Elliot Servers and Samplers](https://mlsanity.com/paper/2002.05711/) (2020)

## Built on by (most cited first, 8 of 8)

- [Distributed Learning based on 1-Bit Gradient Coding in the Presence of Stragglers](https://mlsanity.com/paper/2403.14716/) (2024)
- [Gradient Coding with Iterative Block Leverage Score Sampling](https://mlsanity.com/paper/2308.03096/) (2023)
- [Optimization-based Block Coordinate Gradient Coding for Mitigating Partial Stragglers in Distributed Learning](https://mlsanity.com/paper/2206.02450/) (2022)
- [Gradient Coding in Decentralized Learning for Evading Stragglers](https://mlsanity.com/paper/2402.04193/) (2024)
- [Adaptive Coded Federated Learning: Privacy Preservation and Straggler Mitigation](https://mlsanity.com/paper/2403.14905/) (2024)
- [Nested Gradient Codes for Straggler Mitigation in Distributed Machine Learning](https://mlsanity.com/paper/2212.08580/) (2022)
- [Design and Optimization of Hierarchical Gradient Coding for Distributed Learning at Edge Devices](https://mlsanity.com/paper/2406.10831/) (2024)
- [Coded Robust Aggregation for Distributed Learning under Byzantine Attacks](https://mlsanity.com/paper/2506.01989/) (2025)

## Abstract (arXiv)

Distributed implementations are crucial in speeding up large scale machine learning applications. Distributed gradient descent (GD) is widely employed to parallelize the learning task by distributing the dataset across multiple workers. A significant performance bottleneck for the per-iteration completion time in distributed synchronous GD is straggling workers. Coded distributed computation techniques have been introduced recently to mitigate stragglers and to speed up GD iterations by assigning redundant computations to workers. In this paper, we consider gradient coding (GC), and propose a novel dynamic GC scheme, which assigns redundant data to workers to acquire the flexibility to dynamically choose from among a set of possible codes depending on the past straggling behavior. In particular, we consider GC with clustering, and regulate the number of stragglers in each cluster by dynamically forming the clusters at each iteration; hence, the proposed scheme is called GC with dynamic clustering (GC-DC). Under a time-correlated straggling behavior, GC-DC gains from adapting to the straggling behavior over time such that, at each iteration, GC-DC aims at distributing the stragglers across clusters as uniformly as possible based on the past straggler behavior. For both homogeneous and heterogeneous worker models, we numerically show that GC-DC provides significant improvements in the average per-iteration completion time without an increase in the communication load compared to the original GC scheme.