  A central issue of distributed computing systems is how to optimally allocate
computing and storage resources and design data shuffling strategies such that
the total execution time for computing and data shuffling is minimized. This is
extremely critical when the computation, storage and communication resources
are limited. In this paper, we study the resource allocation and coding scheme
for the MapReduce-type framework with limited resources. In particular, we
focus on the coded distributed computing (CDC) approach proposed by Li et al..
We first extend the asymmetric CDC (ACDC) scheme proposed by Yu et al. to the
cascade case where each output function is computed by multiple servers. Then
we demonstrate that whether CDC or ACDC is better depends on system parameters
(e.g., number of computing servers) and task parameters (e.g., number of input
files), implying that neither CDC nor ACDC is optimal. By merging the ideas of
CDC and ACDC, we propose a hybrid scheme and show that it can strictly
outperform CDC and ACDC. Furthermore, we derive an information-theoretic
converse showing that for the MapReduce task using a type of weakly symmetric
Reduce assignment, which includes the Reduce assignments of CDC and ACDC as
special cases, the hybrid scheme with a corresponding resource allocation
strategy is optimal, i.e., achieves the minimum execution time, for an
arbitrary amount of computing servers and storage memories.
