# Straggler-aware Distributed Learning: Communication Computation Latency Trade-off

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Apr 2020.

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

- [Gradient Coding with Dynamic Clustering for Straggler-Tolerant Distributed Learning](https://mlsanity.com/paper/2103.01206/) (2021)
- [Robust Federated Learning with Connectivity Failures: A Semi-Decentralized Framework with Collaborative Relaying](https://mlsanity.com/paper/2202.11850/) (2022)
- [SCoTTi: Save Computation at Training Time with an adaptive framework](https://mlsanity.com/paper/2312.12483/) (2023)
- [Adaptive Stochastic Gradient Descent for Fast and Communication-Efficient Distributed Learning](https://mlsanity.com/paper/2208.03134/) (2022)
- [Argus: Federated Non-convex Bilevel Learning over 6G Space-Air-Ground Integrated Network](https://mlsanity.com/paper/2505.09106/) (2025)
- [Coded Computation across Shared Heterogeneous Workers with Communication Delay](https://mlsanity.com/paper/2109.11246/) (2021)
- [Lightweight Projective Derivative Codes for Compressed Asynchronous Gradient Descent](https://mlsanity.com/paper/2201.12990/) (2022)
- [Noise Resilient Over-The-Air Federated Learning In Heterogeneous Wireless Networks](https://mlsanity.com/paper/2503.19549/) (2025)
- [Cost-Efficient Distributed Learning via Combinatorial Multi-Armed Bandits](https://mlsanity.com/paper/2202.08302/) (2022)
- [Generalized Lagrange Coded Computing: A Flexible Computation-Communication Tradeoff for Resilient, Secure, and Private Computation](https://mlsanity.com/paper/2204.11168/) (2022)
- [Fast and Straggler-Tolerant Distributed SGD with Reduced Computation Load](https://mlsanity.com/paper/2304.08589/) (2023)
- [Approximate Gradient Coding for Privacy-Flexible Federated Learning with Non-IID Data](https://mlsanity.com/paper/2404.03524/) (2024)
- [Distributed Multi-Head Learning Systems for Power Consumption Prediction](https://mlsanity.com/paper/2501.12133/) (2025)
- [Channel-Adaptive Robust Aggregation for Over-the-Air Federated Learning in Heterogeneous Networks](https://mlsanity.com/paper/2607.04218/) (2026)
- [Pipelined Gradient Coding](https://mlsanity.com/paper/2607.20739/) (2026)

## Abstract (arXiv)

When gradient descent (GD) is scaled to many parallel workers for large scale machine learning problems, its per-iteration computation time is limited by the straggling workers. Straggling workers can be tolerated by assigning redundant computations and coding across data and computations, but in most existing schemes, each non-straggling worker transmits one message per iteration to the parameter server (PS) after completing all its computations. Imposing such a limitation results in two main drawbacks; over-computation due to inaccurate prediction of the straggling behaviour, and under-utilization due to treating workers as straggler/non-straggler and discarding partial computations carried out by stragglers. In this paper, to overcome these drawbacks, we consider multi-message communication (MMC) by allowing multiple computations to be conveyed from each worker per iteration, and design straggler avoidance techniques accordingly. Then, we analyze how the proposed designs can be employed efficiently to seek a balance between the computation and communication latency to minimize the overall latency. Furthermore, through extensive simulations, both model-based and real implementation on Amazon EC2 servers, we identify the advantages and disadvantages of these designs in different settings, and demonstrate that MMC can help improve upon existing straggler avoidance schemes.