Network Coding Approaches for Distributed Computation over Lossy Wireless Networks.

Area of Science:

• Computer Science
• Electrical Engineering
• Applied Mathematics

Background:

• Wireless distributed computing systems face latency challenges due to worker node straggling and packet losses.
• Matrix multiplications are fundamental to many machine learning applications, making their efficient computation critical.

Purpose of the Study:

• To develop novel coding approaches for wireless distributed computing systems performing large-scale matrix multiplications.
• To mitigate latency issues caused by straggling workers and channel fading.

Main Methods:

• Proposed a random linear network coding (RLNC) approach leveraging the linearity of matrix multiplication.
• Developed a practical variation using batched sparse (BATS) codes to reduce RLNC overheads.
• Theoretically analyzed latency convergence for RLNC in large matrix size scenarios.

Main Results:

• RLNC demonstrates ratelessness, high straggler tolerance, and near-ideal load balancing.
• Theoretical analysis shows RLNC latency converges to the optimum in probability as matrix size increases.
• Numerical simulations validate the effectiveness of both RLNC and BATS-based approaches.

Conclusions:

• The proposed RLNC and BATS-based coding schemes effectively reduce latency in wireless distributed matrix multiplication.
• These methods offer robust solutions for machine learning tasks in challenging wireless environments.
• The findings contribute to more efficient and reliable distributed computing systems.