{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T01:02:55Z","timestamp":1760058175478,"version":"build-2065373602"},"reference-count":26,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2025,3,16]],"date-time":"2025-03-16T00:00:00Z","timestamp":1742083200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Key Lab of Education Blockchain and Intelligent Technology, Ministry of Education","award":["EBME24-15"],"award-info":[{"award-number":["EBME24-15"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>Coded distributed computing (CDC) is a powerful approach to reduce the communication overhead in distributed computing frameworks by utilizing coding techniques. In this paper, we focus on the CDC problem in (H,L)-combination networks, where H APs act as intermediate pivots and K=HL workers are connected to different subsets of L APs. Each worker processes a subset of the input file and computes intermediate values (IVs) locally, which are then exchanged via uplink and downlink transmissions through the AP station to ensure that all workers compute their assigned output functions. In this paper, we first novelly characterize the transmission scheme for the shuffle phase from the view point of the coefficient matrix and then obtain the scheme by using the Combined Placement Delivery Array (CPDA). Compared with the baseline scheme, our scheme significantly improves the uplink and downlink communication loads while maintaining the robustness and efficiency of the combined multi-AP network.<\/jats:p>","DOI":"10.3390\/e27030311","type":"journal-article","created":{"date-parts":[[2025,3,17]],"date-time":"2025-03-17T07:49:57Z","timestamp":1742197797000},"page":"311","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Coded Distributed Computing Under Combination Networks"],"prefix":"10.3390","volume":"27","author":[{"given":"Yongcheng","family":"Yang","sequence":"first","affiliation":[{"name":"Key Lab of Education Blockchain and Intelligent Technology, Ministry of Education, Guangxi Normal University, Guilin 541004, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yifei","family":"Huang","sequence":"additional","affiliation":[{"name":"Key Lab of Education Blockchain and Intelligent Technology, Ministry of Education, Guangxi Normal University, Guilin 541004, China"},{"name":"School of Science, Guilin University of Aerospace Technology, Guilin 541004, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaohuan","family":"Qin","sequence":"additional","affiliation":[{"name":"State Key Laboratory for Chemistry and Molecular Engineering of Medicinal Resources, School of Chemistry and Pharmaceutical Science, Guangxi Normal University, Guilin 541004, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4957-9418","authenticated-orcid":false,"given":"Shenglian","family":"Lu","sequence":"additional","affiliation":[{"name":"Key Lab of Education Blockchain and Intelligent Technology, Ministry of Education, Guangxi Normal University, Guilin 541004, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2025,3,16]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1145\/1327452.1327492","article-title":"MapReduce: Simplified data processing on large clusters","volume":"51","author":"Dean","year":"2008","journal-title":"Commun. ACM"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1145\/1272998.1273005","article-title":"Dryad: Distributed data-parallel programs from sequential building blocks","volume":"41","author":"Isard","year":"2007","journal-title":"SIGOPS Oper. Syst. Rev."},{"key":"ref_3","unstructured":"Zaharia, M., Chowdhury, M., Franklin, M.J., Shenker, S., and Stoica, I. (2010, January 22\u201325). Spark: Cluster Computing with Working Sets. Proceedings of the 2nd USENIX Workshop on Hot Topics in Cloud Computing (HotCloud 10), Boston, MA, USA."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1109\/TIT.2017.2756959","article-title":"A Fundamental Tradeoff Between Computation and Communication in Distributed Computing","volume":"64","author":"Li","year":"2018","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Li, S., Maddah-Ali, M.A., and Avestimehr, A.S. (2016, January 4\u20138). A Unified Coding Framework for Distributed Computing with Straggling Servers. Proceedings of the 2016 IEEE Globecom Workshops (GC Wkshps), Washington, DC, USA.","DOI":"10.1109\/GLOCOMW.2016.7848828"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"7311","DOI":"10.1109\/TCOMM.2020.3020549","article-title":"A Fundamental Storage-Communication Tradeoff for Distributed Computing with Straggling Nodes","volume":"68","author":"Yan","year":"2020","journal-title":"IEEE Trans. Commun."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Yan, Q., Wigger, M., Yang, S., and Tang, X. (2019, January 7\u201312). A Fundamental Storage-Communication Tradeoff in Distributed Computing with Straggling Nodes. Proceedings of the 2019 IEEE International Symposium on Information Theory (ISIT), Paris, France.","DOI":"10.1109\/ISIT.2019.8849615"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Yu, Q., Li, S., Maddah-Ali, M.A., and Avestimehr, A.S. (2017, January 21\u201325). How to optimally allocate resources for coded distributed computing?. Proceedings of the 2017 IEEE International Conference on Communications (ICC), Paris, France.","DOI":"10.1109\/ICC.2017.7996730"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Attia, M.A., and Tandon, R. (2016, January 27\u201330). On the worst-case communication overhead for distributed data shuffling. Proceedings of the 2016 54th Annual Allerton Conference on Communication, Control, and Computing (Allerton), Monticello, IL, USA.","DOI":"10.1109\/ALLERTON.2016.7852338"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Attia, M.A., and Tandon, R. (2016, January 4\u20138). Information Theoretic Limits of Data Shuffling for Distributed Learning. Proceedings of the 2016 IEEE Global Communications Conference (GLOBECOM), Washington, DC, USA.","DOI":"10.1109\/GLOCOM.2016.7841903"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Elmahdy, A., and Mohajer, S. (2018, January 17\u201322). On the Fundamental Limits of Coded Data Shuffling. Proceedings of the 2018 IEEE International Symposium on Information Theory (ISIT), Vail, CO, USA.","DOI":"10.1109\/ISIT.2018.8437672"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Song, L., Srinivasavaradhan, S.R., and Fragouli, C. (2017, January 6\u201310). The benefit of being flexible in distributed computation. Proceedings of the 2017 IEEE Information Theory Workshop (ITW), Kaohsiung, Taiwan.","DOI":"10.1109\/ITW.2017.8278019"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Srinivasavaradhan, S.R., Song, L., and Fragouli, C. (2018, January 17\u201322). Distributed Computing Trade-offs with Random Connectivity. Proceedings of the 2018 IEEE International Symposium on Information Theory (ISIT), Vail, CO, USA.","DOI":"10.1109\/ISIT.2018.8437653"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"6101","DOI":"10.1109\/TIT.2019.2924621","article-title":"Wireless MapReduce Distributed Computing","volume":"65","author":"Li","year":"2019","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Parrinello, E., Lampiris, E., and Elia, P. (2018, January 17\u201322). Coded Distributed Computing with Node Cooperation Substantially Increases Speedup Factors. Proceedings of the 2018 IEEE International Symposium on Information Theory (ISIT), Vail, CO, USA.","DOI":"10.1109\/ISIT.2018.8437333"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Li, S., Yu, Q., Maddah-Ali, M.A., and Avestimehr, A.S. (2016, January 4\u20138). Edge-Facilitated Wireless Distributed Computing. Proceedings of the 2016 IEEE Global Communications Conference (GLOBECOM), Washington, DC, USA.","DOI":"10.1109\/GLOCOM.2016.7841765"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"2643","DOI":"10.1109\/TNET.2017.2702605","article-title":"A Scalable Framework for Wireless Distributed Computing","volume":"25","author":"Li","year":"2017","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"5686","DOI":"10.1109\/TCOMM.2023.3298981","article-title":"A Fundamental Tradeoff Among Storage, Computation, and Communication for Distributed Computing Over Star Network","volume":"71","author":"Yan","year":"2023","journal-title":"IEEE Trans. Commun."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Ji, M., Wong, M.F., Tulino, A.M., Llorca, J., Caire, G., Effros, M., and Langberg, M. (July, January 28). On the fundamental limits of caching in combination networks. Proceedings of the 2015 IEEE 16th International Workshop on Signal Processing Advances in Wireless Communications (SPAWC), Stockholm, Sweden.","DOI":"10.1109\/SPAWC.2015.7227127"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Peter, E., Krishnan Namboodiri, K.K., and Rajan, B.S. (2024, January 24\u201328). Wireless MapReduce Arrays for Coded Distributed Computing. Proceedings of the 2024 IEEE Information Theory Workshop (ITW), Shenzhen, China.","DOI":"10.1109\/ITW61385.2024.10806973"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Yan, Q., Wigger, M., and Yang, S. (2018, January 17\u201322). Placement Delivery Array Design for Combination Networks with Edge Caching. Proceedings of the 2018 IEEE International Symposium on Information Theory (ISIT), Vail, CO, USA.","DOI":"10.1109\/ISIT.2018.8437603"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"5965","DOI":"10.1109\/TCOMM.2020.3005712","article-title":"Improved Constructions of Coded Caching Schemes for Combination Networks","volume":"68","author":"Cheng","year":"2020","journal-title":"IEEE Trans. Commun."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Huang, L., Wang, J., Cheng, M., Deng, Q., and Zhong, B. (2022). Coded Caching for Combination Networks with Multiaccess. Information, 13.","DOI":"10.3390\/info13040191"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"2716","DOI":"10.1109\/TCOMM.2024.3351367","article-title":"Coded Caching for Dense-User Combination Network in Binary Field","volume":"72","author":"Zhang","year":"2024","journal-title":"IEEE Trans. Commun."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"849","DOI":"10.1109\/TIT.2015.2504556","article-title":"Fundamental Limits of Caching in Wireless D2D Networks","volume":"62","author":"Ji","year":"2016","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"3388","DOI":"10.1109\/TCOMM.2019.2893942","article-title":"Placement Delivery Array Design for Coded Caching Scheme in D2D Networks","volume":"67","author":"Wang","year":"2019","journal-title":"IEEE Trans. Commun."}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/27\/3\/311\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T16:54:28Z","timestamp":1760028868000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/27\/3\/311"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,3,16]]},"references-count":26,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2025,3]]}},"alternative-id":["e27030311"],"URL":"https:\/\/doi.org\/10.3390\/e27030311","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2025,3,16]]}}}