Map–Shuffle–Reduce Arrays for Cascaded Coded Distributed Computing: Bounds and Constructions
Entropy · 12.11.2026 · 28 (11) · 1247
DOI: 10.3390/e28111247 ↗Kurz gefasst
Fachartikel in der Zeitschrift Entropy, online erschienen am 12.11.2026. Verfasst von Jiaqi Fang und 4 weiteren Autor:innen. Die Arbeit nennt 21 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Foundation Strengthening Action Plan of Guangxi Basic Research Program, Natural Science Foundation of Guangxi.
Abstract (Originalsprache)
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
Förderung
- Foundation Strengthening Action Plan of Guangxi Basic Research Program
- Natural Science Foundation of Guangxi
Zitieren
APA
Fang, J., Huang, Y., Wu, G., Zhang, M., & Cheng, M. (2026). Map–Shuffle–Reduce Arrays for Cascaded Coded Distributed Computing: Bounds and Constructions. Entropy, 28(11), 1247. https://doi.org/10.3390/e28111247
Vancouver
Fang J, Huang Y, Wu G, Zhang M, Cheng M. Map–Shuffle–Reduce Arrays for Cascaded Coded Distributed Computing: Bounds and Constructions. Entropy. 2026;28(11):1247. doi:10.3390/e28111247
BibTeX
@article{Fang2026,
author = {Fang, Jiaqi and Huang, Yifei and Wu, Guolin and Zhang, Mingming and Cheng, Minquan},
title = {Map–Shuffle–Reduce Arrays for Cascaded Coded Distributed Computing: Bounds and Constructions},
journal = {Entropy},
year = {2026},
volume = {28},
number = {11},
pages = {1247},
doi = {10.3390/e28111247}
}
EUVIMED