A New Combinatorial Coded Design for Heterogeneous Distributed Computing
arXiv:2007.11116
Abstract
Coded Distributed Computing (CDC) introduced by Li et al. in 2015 offers an efficient approach to trade computing power to reduce the communication load in general distributed computing frameworks such as MapReduce and Spark. In particular, increasing the computation load in the Map phase by a factor of r can create coded multicasting opportunities to reduce the communication load in the Shuffle phase by the same factor. However, the CDC scheme is designed for the homogeneous settings, where the storage, computation load and communication load on the computing nodes are the same. In addition, it requires an exponentially large number of input files (data batches), reduce functions and multicasting groups relative to the number of nodes to achieve the promised gain. We address the CDC limitations by proposing a novel CDC approach based on a combinatorial design, which accommodates heterogeneous networks where nodes have varying storage and computing capabilities. In addition, the proposed approach requires an exponentially less number of input files compared to the original CDC scheme proposed by Li et al. Meanwhile, the resulting computation-communication trade-off maintains the multiplicative gain compared to conventional uncoded unicast and asymptotically achieves the optimal performance proposed by Li et al.
30 pages, 5 pages
References in corpus (9)
- Speeding Up Distributed Machine Learning Using Codes
- On the Capacity Region for Index Coding
- Minimizing Latency for Secure Distributed Computing
- Fundamental Limits of Coded Linear Transform
- Robust Gradient Descent via Moment Encoding with LDPC Codes
- Distributed Computing with Heterogeneous Communication Constraints: The Worst-Case Computation Load and Proof by Contradiction
- On the Placement Delivery Array Design for Coded Caching Scheme in D2D Networks
- Heterogeneous Coded Distributed Computing: Joint Design of File Allocation and Function Assignment
- The Benefit of Being Flexible in Distributed Computation
Cited by in corpus (3)
- A Combinatorial Design for Cascaded Coded Distributed Computing on General Networks
- Cache-aided Interference Management using Hypercube Combinatorial Cache Design with Reduced Subpacketizations and Order Optimal Sum-Degrees of Freedom
- FLCD: A Flexible Low Complexity Design of Coded Distributed Computing