A Survey of Coded Distributed Computing

Abstract

Distributed computing has become a common approach for large-scale computation of tasks due to benefits such as high reliability, scalability, computation speed, and costeffectiveness. However, distributed computing faces critical issues related to communication load and straggler effects. In particular, computing nodes need to exchange intermediate results with each other in order to calculate the final result, and this significantly increases communication overheads. Furthermore, a distributed computing network may include straggling nodes that run intermittently slower. This results in a longer overall time needed to execute the computation tasks, thereby limiting the performance of distributed computing. To address these issues, coded distributed computing (CDC), i.e., a combination of coding theoretic techniques and distributed computing, has been recently proposed as a promising solution. Coding theoretic techniques have proved effective in WiFi and cellular systems to deal with channel noise. Therefore, CDC may significantly reduce communication load, alleviate the effects of stragglers, provide fault-tolerance, privacy and security. In this survey, we first introduce the fundamentals of CDC, followed by basic CDC schemes. Then, we review and analyze a number of CDC approaches proposed to reduce the communication costs, mitigate the straggler effects, and guarantee privacy and security. Furthermore, we present and discuss applications of CDC in modern computer networks. Finally, we highlight important challenges and promising research directions related to CDC

References in corpus (34)

• Very Deep Convolutional Networks for Large-Scale Image Recognition
• Communication-Efficient Learning of Deep Networks from Decentralized Data
• Network Function Virtualization: State-of-the-art and Research Challenges
• The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks
• QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding
• Speeding Up Distributed Machine Learning Using Codes
• Lagrange Coded Computing: Optimal Design for Resiliency, Security and Privacy
• Coded Sparse Matrix Multiplication
• Minimizing Latency for Secure Distributed Computing
• Minimizing Latency for Secure Coded Computing Using Secret Sharing via Staircase Codes
• OverSketch: Approximate Matrix Multiplication for the Cloud
• Data Shuffling in Wireless Distributed Computing via Low-Rank Optimization
• Polynomially Coded Regression: Optimal Straggler Mitigation via Data Encoding
• Approximate Gradient Coding via Sparse Random Graphs
• CodedPrivateML: A Fast and Privacy-Preserving Framework for Distributed Machine Learning
• ErasureHead: Distributed Gradient Descent without Delays Using Approximate Gradient Coding
• Learning a Code: Machine Learning for Approximate Non-Linear Coded Computation
• Fundamental Limits of Coded Linear Transform
• Rate-Efficiency and Straggler-Robustness through Partition in Distributed Two-Sided Secure Matrix Computation
• A Practical Guide to Randomized Matrix Computations with MATLAB Implementations
• Incentive Mechanism Design for Resource Sharing in Collaborative Edge Learning
• Towards Federated Learning in UAV-Enabled Internet of Vehicles: A Multi-Dimensional Contract-Matching Approach
• Coded Network Function Virtualization: Fault Tolerance via In-Network Coding
• On the Capacity of Secure Distributed Batch Matrix Multiplication
• Gradient Coding via the Stochastic Block Model
• Straggler-Resilient and Communication-Efficient Distributed Iterative Linear Solver
• On Batch-Processing Based Coded Computing for Heterogeneous Distributed Computing Systems
• Coded Computing for Federated Learning at the Edge
• Combating Computational Heterogeneity in Large-Scale Distributed Computing via Work Exchange
• Coded Distributed Computing with Heterogeneous Function Assignments
• Private Coded Computation for Machine Learning
• Heterogeneous Coded Distributed Computing: Joint Design of File Allocation and Function Assignment
• Optimal Load Allocation for Coded Distributed Computation in Heterogeneous Clusters
• Timely-Throughput Optimal Coded Computing over Cloud Networks

Cited by in corpus (4)

• Coded Computation across Shared Heterogeneous Workers with Communication Delay
• A Game-theoretic Approach Towards Collaborative Coded Computation Offloading
• Optimization-based Block Coordinate Gradient Coding for Mitigating Partial Stragglers in Distributed Learning
• Jointly Optimize Coding and Node Selection for Distributed Computing over Wireless Edge Networks