# Coded Computation across Shared Heterogeneous Workers with Communication Delay

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 42 references that are in the map.
- First posted on arXiv 23 Sep 2021.

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

- [Wireless Network Intelligence at the Edge](https://mlsanity.com/paper/1812.02858/) (2018)
- [Speeding Up Distributed Machine Learning Using Codes](https://mlsanity.com/paper/1512.02673/) (2015)
- [Lagrange Coded Computing: Optimal Design for Resiliency, Security and Privacy](https://mlsanity.com/paper/1806.00939/) (2018)
- [Coded Computing for Low-Latency Federated Learning over Wireless Edge Networks](https://mlsanity.com/paper/2011.06223/) (2020)
- [Straggler-aware Distributed Learning: Communication Computation Latency Trade-off](https://mlsanity.com/paper/2004.04948/) (2020)
- [Coded Computation over Heterogeneous Clusters](https://mlsanity.com/paper/1701.05973/) (2017)
- [Parallel and Distributed Methods for Nonconvex Optimization--Part II: Applications](https://mlsanity.com/paper/1601.04059/) (2016)
- [A Unified Coding Framework for Distributed Computing with Straggling Servers](https://mlsanity.com/paper/1609.01690/) (2016)
- [A Survey of Coded Distributed Computing](https://mlsanity.com/paper/2008.09048/) (2020)
- [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)
- [Joint Coding and Scheduling Optimization for Distributed Learning over Wireless Edge Networks](https://mlsanity.com/paper/2103.04303/) (2021)
- [A Scalable Framework for Wireless Distributed Computing](https://mlsanity.com/paper/1608.05743/) (2016)
- [Exploiting Moving Intelligence: Delay-Optimized Computation Offloading in Vehicular Fog Networks](https://mlsanity.com/paper/1902.09401/) (2019)
- [Efficient Redundancy Techniques for Latency Reduction in Cloud Systems](https://mlsanity.com/paper/1508.03599/) (2015)
- [Bivariate Polynomial Coding for Efficient Distributed Matrix Multiplication](https://mlsanity.com/paper/2001.07227/) (2020)
- [Optimal Load Allocation for Coded Distributed Computation in Heterogeneous Clusters](https://mlsanity.com/paper/1904.09496/) (2019)

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

- [Timeliness-Oriented Scheduling and Resource Allocation in Multi-Region Collaborative Perception](https://mlsanity.com/paper/2601.04542/) (2026)

## Abstract (arXiv)

Distributed computing enables large-scale computation tasks to be processed over multiple workers in parallel. However, the randomness of communication and computation delays across workers causes the straggler effect, which may degrade the performance. Coded computation helps to mitigate the straggler effect, but the amount of redundant load and their assignment to the workers should be carefully optimized. In this work, we consider a multi-master heterogeneous-worker distributed computing scenario, where multiple matrix multiplication tasks are encoded and allocated to workers for parallel computation. The goal is to minimize the communication plus computation delay of the slowest task. We propose worker assignment, resource allocation and load allocation algorithms under both dedicated and fractional worker assignment policies, where each worker can process the encoded tasks of either a single master or multiple masters, respectively. Then, the non-convex delay minimization problem is solved by employing the Markov's inequality-based approximation, Karush-Kuhn-Tucker conditions, and successive convex approximation methods. Through extensive simulations, we show that the proposed algorithms can reduce the task completion delay compared to the benchmarks, and observe that dedicated and fractional worker assignment policies have different scopes of applications.