上海科技大学知识管理系统

Coded distributed computing, proposed by Li et al., offers significant potential for reducing the communication load in MapReduce computing systems. In the setting of the cascaded coded distributed computing that consisting of K nodes, N input files, and Q output functions, the objective is to compute each output function through s > 1 nodes with a computation load r > 1, enabling the application of coding techniques during the Shuffle phase to achieve minimum communication load. However, for most existing coded distributed computing schemes, a major limitation lies in their demand for splitting the original data into an exponentially growing number of input files in terms of N/(K) â N and requiring r an exponentially large number of output functions Q/(K ) â N, which imposes stringent requirements s for implementation and results in significant coding complexity when K is large. In this paper, we focus on the cascaded case of K/s â N, deliberately designing the strategy of data placement and output functions assignment based on a grouping method, such that a low-complexity Shuffle strategy of two rounds is achievable. The main advantages of the proposed scheme include: 1) the multicast gains equal to (r + s â 1)(1â 1/s) and r + s â 1 which is approximate to r + s â 1 when s is relatively large, and the communication load is quite approximate to or surprisingly better than the optimal state -of -the -art scheme proposed by Li et al.; 2) the proposed scheme requires significantly less number of input files and output functions; 3) all the operations are implemented over the minimum binary field F2 in the one-shot fashion. Finally, we derive a new information-theoretic converse bound for the cascaded coded distributed computing framework, under the given strategies of data placement and output functions assignment. We demonstrate that the communication load of the proposed scheme is order optimal within a factor of 2; and is also approximately optimal when K is sufficiently large for a given r.