Coded Distributed Computing Under Combination Networks

Area of Science:

• Computer Science
• Information Theory
• Distributed Systems

Background:

• Distributed computing frameworks face communication overhead challenges.
• Coded distributed computing (CDC) utilizes coding techniques to mitigate this overhead.
• Existing CDC schemes may not be optimal for complex network topologies like (H,L)-combination networks.

Purpose of the Study:

• To develop and analyze a novel transmission scheme for coded distributed computing in (H,L)-combination networks.
• To characterize the shuffle phase transmission using coefficient matrices.
• To improve communication efficiency (uplink and downlink loads) while maintaining network robustness.

Main Methods:

• Characterization of the transmission scheme for the shuffle phase using coefficient matrix analysis.
• Application of the Combined Placement Delivery Array (CPDA) to derive the optimal scheme.
• Comparative analysis against baseline schemes to quantify improvements.

Main Results:

• A novel transmission scheme for the shuffle phase in (H,L)-combination networks is obtained.
• The proposed scheme significantly reduces both uplink and downlink communication loads.
• The scheme maintains the robustness and efficiency of the distributed computing network.

Conclusions:

• The novel CDC scheme effectively addresses communication overhead in (H,L)-combination networks.
• CPDA is a valuable tool for designing efficient coded distributed computing strategies.
• The findings offer a more efficient and robust solution for distributed computing systems.