# Coded Computation over Heterogeneous Clusters

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Jan 2017.

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

- [CodedPaddedFL and CodedSecAgg: Straggler Mitigation and Secure Aggregation in Federated Learning](https://mlsanity.com/paper/2112.08909/) (2021)
- [Joint Coding and Scheduling Optimization for Distributed Learning over Wireless Edge Networks](https://mlsanity.com/paper/2103.04303/) (2021)
- [List-Decodable Coded Computing: Breaking the Adversarial Toleration Barrier](https://mlsanity.com/paper/2101.11653/) (2021)
- [Coding for Straggler Mitigation in Federated Learning](https://mlsanity.com/paper/2109.15226/) (2021)
- [Coding for Distributed Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2101.02308/) (2021)
- [Coded Computation across Shared Heterogeneous Workers with Communication Delay](https://mlsanity.com/paper/2109.11246/) (2021)
- [Randomized Polar Codes for Anytime Distributed Machine Learning](https://mlsanity.com/paper/2309.00682/) (2023)
- [Multi-Agent Reinforcement Learning Based Coded Computation for Mobile Ad Hoc Computing](https://mlsanity.com/paper/2104.07539/) (2021)
- [Distributed Multi-Agent Reinforcement Learning with One-hop Neighbors and Compute Straggler Mitigation](https://mlsanity.com/paper/2202.09019/) (2022)
- [Iterative Sketching for Secure Coded Regression](https://mlsanity.com/paper/2308.04185/) (2023)
- [Successive Refinement in Large-Scale Computation: Advancing Model Inference Applications](https://mlsanity.com/paper/2402.07229/) (2024)
- [Approximate Gradient Coding for Distributed Learning with Heterogeneous Stragglers](https://mlsanity.com/paper/2510.22539/) (2025)

## Abstract (arXiv)

In large-scale distributed computing clusters, such as Amazon EC2, there are several types of "system noise" that can result in major degradation of performance: bottlenecks due to limited communication bandwidth, latency due to straggler nodes, etc. On the other hand, these systems enjoy abundance of redundancy - a vast number of computing nodes and large storage capacity. There have been recent results that demonstrate the impact of coding for efficient utilization of computation and storage redundancy to alleviate the effect of stragglers and communication bottlenecks in homogeneous clusters. In this paper, we focus on general heterogeneous distributed computing clusters consisting of a variety of computing machines with different capabilities. We propose a coding framework for speeding up distributed computing in heterogeneous clusters by trading redundancy for reducing the latency of computation. In particular, we propose Heterogeneous Coded Matrix Multiplication (HCMM) algorithm for performing distributed matrix multiplication over heterogeneous clusters that is provably asymptotically optimal for a broad class of processing time distributions. Moreover, we show that HCMM is unboundedly faster than any uncoded scheme. To demonstrate practicality of HCMM, we carry out experiments over Amazon EC2 clusters where HCMM is found to be up to 61%, 46% and 36% respectively faster than three benchmark load allocation schemes - Uniform Uncoded, Load-balanced Uncoded, and Uniform Coded. Additionally, we provide a generalization to the problem of optimal load allocation in heterogeneous settings, where we take into account the monetary costs associated with the clusters. We argue that HCMM is asymptotically optimal for budget-constrained scenarios as well, and we develop a heuristic algorithm for (HCMM) load allocation for budget-limited computation tasks.