Map–Shuffle–Reduce Arrays for Cascaded Coded Distributed Computing: Bounds and Constructions

Cascaded coded distributed computing (CDC) reduces Shuffle communication through redundant Map computations and replicated output assignments. We propose Map–Shuffle–Reduce arrays (MSRAs), a unified framework for describing file placement, output assignment, transmitter selection, and one-shot XOR delivery. For fixed placement, assignment, and equal-length packetization, minimizing communication load is equivalent to minimizing the number of distinct array labels. We establish communication lower bounds for two settings: coded transmissions involving different file–output pairs, and the case where every output function is assigned to all nodes. We develop two cyclic MSRA constructions that attain the corresponding bounds under their respective conditions. In particular, the packetized construction achieves a communication load of Lcomm=(K−r)/(K−1) when 2≤r<K and K−r divides K−1, using only N=K files and Q=1 output function. For partial output assignment, we introduce a group–helper construction that delivers complete intermediate values without splitting them into smaller packets. Under regular file storage and direct one-shot decoding using locally computed intermediate values, this construction attains a receiver-gain lower bound for its parameter family. Finally, we demonstrate how existing CDC schemes can be represented within the MSRA framework and compare their communication and implementation tradeoffs.