# Heterogeneity-aware Gradient Coding for Straggler Tolerance

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Jan 2019.

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

- [Taming Resource Heterogeneity In Distributed ML Training With Dynamic Batching](https://mlsanity.com/paper/2305.12213/) (2023)
- [Gradient Coding with Dynamic Clustering for Straggler-Tolerant Distributed Learning](https://mlsanity.com/paper/2103.01206/) (2021)
- [Optimal Communication-Computation Trade-Off in Heterogeneous Gradient Coding](https://mlsanity.com/paper/2103.01589/) (2021)
- [Sequential Gradient Coding For Straggler Mitigation](https://mlsanity.com/paper/2211.13802/) (2022)
- [Design and Optimization of Hierarchical Gradient Coding for Distributed Learning at Edge Devices](https://mlsanity.com/paper/2406.10831/) (2024)
- [Coding-Enforced Resilient and Secure Aggregation for Hierarchical Federated Learning](https://mlsanity.com/paper/2601.17995/) (2026)

## Abstract (arXiv)

Gradient descent algorithms are widely used in machine learning. In order to deal with huge volume of data, we consider the implementation of gradient descent algorithms in a distributed computing setting where multiple workers compute the gradient over some partial data and the master node aggregates their results to obtain the gradient over the whole data. However, its performance can be severely affected by straggler workers. Recently, some coding-based approaches are introduced to mitigate the straggler problem, but they are efficient only when the workers are homogeneous, i.e., having the same computation capabilities. In this paper, we consider that the workers are heterogeneous which are common in modern distributed systems. We propose a novel heterogeneity-aware gradient coding scheme which can not only tolerate a predetermined number of stragglers but also fully utilize the computation capabilities of heterogeneous workers. We show that this scheme is optimal when the computation capabilities of workers are estimated accurately. A variant of this scheme is further proposed to improve the performance when the estimations of the computation capabilities are not so accurate. We conduct our schemes for gradient descent based image classification on QingCloud clusters. Evaluation results show that our schemes can reduce the whole computation time by up to 3× compared with a state-of-the-art coding scheme.