# Gradient Coding with Clustering and Multi-message Communication

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Mar 2019.

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

- [Gradient Coding with Dynamic Clustering for Straggler-Tolerant Distributed Learning](https://mlsanity.com/paper/2103.01206/) (2021)
- [Distributed Learning based on 1-Bit Gradient Coding in the Presence of Stragglers](https://mlsanity.com/paper/2403.14716/) (2024)
- [STSyn: Speeding Up Local SGD with Straggler-Tolerant Synchronization](https://mlsanity.com/paper/2210.03521/) (2022)
- [Lightweight Projective Derivative Codes for Compressed Asynchronous Gradient Descent](https://mlsanity.com/paper/2201.12990/) (2022)
- [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)
- [Robust Distributed Bayesian Learning with Stragglers via Consensus Monte Carlo](https://mlsanity.com/paper/2112.09794/) (2021)
- [Adaptive Worker Grouping For Communication-Efficient and Straggler-Tolerant Distributed SGD](https://mlsanity.com/paper/2201.04301/) (2022)
- [Iterative Sketching for Secure Coded Regression](https://mlsanity.com/paper/2308.04185/) (2023)
- [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)

Gradient descent (GD) methods are commonly employed in machine learning problems to optimize the parameters of the model in an iterative fashion. For problems with massive datasets, computations are distributed to many parallel computing servers (i.e., workers) to speed up GD iterations. While distributed computing can increase the computation speed significantly, the per-iteration completion time is limited by the slowest straggling workers. Coded distributed computing can mitigate straggling workers by introducing redundant computations; however, existing coded computing schemes are mainly designed against persistent stragglers, and partial computations at straggling workers are discarded, leading to wasted computational capacity. In this paper, we propose a novel gradient coding (GC) scheme which allows multiple coded computations to be conveyed from each worker to the master per iteration. We numerically show that the proposed GC with multi-message communication (MMC) together with clustering provides significant improvements in the average completion time (of each iteration), with minimal or no increase in the communication load.