FLCD: A Flexible Low Complexity Design of Coded Distributed Computing

We propose a flexible low complexity design (FLCD) of coded distributed computing (CDC) with empirical evaluation on Amazon Elastic Compute Cloud (Amazon EC2). CDC can expedite MapReduce like computation by trading increased map computations to reduce communication load and shuffle time. A main novelty of FLCD is to utilize the design freedom in defining map and reduce functions to develop asymptotic homogeneous systems to support varying intermediate values (IV) sizes under a general MapReduce framework. Compared to existing designs with constant IV sizes, FLCD offers greater flexibility in adapting to network parameters and significantly reduces the implementation complexity by requiring fewer input files and shuffle groups. The FLCD scheme is the first proposed low-complexity CDC design that can operate on a network with an arbitrary number of nodes and computation load. We perform empirical evaluations of the FLCD by executing the TeraSort algorithm on an Amazon EC2 cluster. This is the first time that theoretical predictions of the CDC shuffle time are validated by empirical evaluations. The evaluations demonstrate a 2.0 to 4.24x speedup compared to conventional uncoded MapReduce, a 12 to 52 percent reduction in total time, and a wider range of operating network parameters compared to existing CDC schemes.

Automated summary

We propose a flexible low complexity design (FLCD) of coded distributed computing (CDC) and evaluate it empirically on Amazon EC2. FLCD utilizes the design freedom to define map and reduce functions and develop asymptotic homogeneous systems for varying IV sizes under a general MapReduce framework. Compared to existing designs, FLCD offers greater flexibility and significantly reduces implementation complexity. This is the first low-complexity CDC design that can operate on a network with an arbitrary number of nodes and computation load. Empirical evaluations demonstrate its speedup compared to conventional MapReduce, reduction in total time, and wider operating network parameters compared to existing CDC schemes.