{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T03:09:06Z","timestamp":1760238546830,"version":"build-2065373602"},"reference-count":25,"publisher":"MDPI AG","issue":"7","license":[{"start":{"date-parts":[[2022,7,15]],"date-time":"2022-07-15T00:00:00Z","timestamp":1657843200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Nature Science Foundation of China (NSFC)","doi-asserted-by":"publisher","award":["61901267"],"award-info":[{"award-number":["61901267"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Information"],"abstract":"<jats:p>This work studies a general distributed coded computing system based on the MapReduce-type framework, where distributed computing nodes within a half-duplex network wish to compute multiple output functions. We first introduce a definition of communication delay to characterize the time cost during the date shuffle phase, and then propose a novel coding strategy that enables parallel transmission among the computation nodes by delicately designing the data placement, message symbols encoding, data shuffling, and decoding. Compared to the coded distributed computing (CDC) scheme proposed by Li et al., the proposed scheme significantly reduces the communication delay, in particular when the computation load is relatively smaller than the number of computing nodes K. Moreover, the communication delay of CDC is a monotonically increasing function of K, while the communication delay of our scheme decreases as K increases, indicating that the proposed scheme can make better use of the computing resources.<\/jats:p>","DOI":"10.3390\/info13070342","type":"journal-article","created":{"date-parts":[[2022,7,15]],"date-time":"2022-07-15T00:17:10Z","timestamp":1657844230000},"page":"342","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Coded Parallel Transmission for Half-Duplex Distributed Computing"],"prefix":"10.3390","volume":"13","author":[{"given":"Qixuan","family":"Zai","sequence":"first","affiliation":[{"name":"Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, 77 Massachusetts Avenue, Cambridge, MA 02139, USA"},{"name":"School of Information Science and Technology, ShanghaiTech University, Shanghai 201210, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kai","family":"Yuan","sequence":"additional","affiliation":[{"name":"School of Information Science and Technology, ShanghaiTech University, Shanghai 201210, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4383-9995","authenticated-orcid":false,"given":"Youlong","family":"Wu","sequence":"additional","affiliation":[{"name":"School of Information Science and Technology, ShanghaiTech University, Shanghai 201210, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2022,7,15]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Cristea, V., Dobre, C., Stratan, C., Pop, F., and Costan, A. (2010). Large-Scale Distributed Computing and Applications: Models and Trends Information Science Reference, IGI Publishing.","DOI":"10.4018\/978-1-61520-703-9"},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Nikoletseas, S., and Rolim, J.D. (2011). Theoretical Aspects of Distributed Computing in Sensor Networks, Springer.","DOI":"10.1007\/978-3-642-14849-1"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2491245","article-title":"Spanner: Google\u2019s globally distributed database","volume":"31","author":"Corbett","year":"2013","journal-title":"ACM Trans. Comput. Syst."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/s10586-011-0171-x","article-title":"An overview of energy efficiency techniques in cluster computing systems","volume":"16","author":"Valentini","year":"2013","journal-title":"Clust. Comput."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Sadashiv, N., and Kumar, S.D. (2011, January 3\u20135). Cluster, grid and cloud computing: A detailed comparison. Proceedings of the 2011 6th International Conference on Computer Science Education (ICCSE), Singapore.","DOI":"10.1109\/ICCSE.2011.6028683"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"709","DOI":"10.1016\/j.parco.2013.09.009","article-title":"A survey on resource allocation in high performance distributed computing systems","volume":"39","author":"Hussain","year":"2013","journal-title":"Parallel Comput."},{"key":"ref_7","unstructured":"Idrissi, H.K., Kartit, A., and El Marraki, M. (2013, January 26\u201327). A taxonomy and survey of cloud computing. Proceedings of the 2013 National Security Days (JNS3), Rabat, Morocco."},{"key":"ref_8","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_9","doi-asserted-by":"crossref","first-page":"472","DOI":"10.14778\/1920841.1920903","article-title":"The performance of mapreduce: An in-depth study","volume":"3","author":"Jiang","year":"2010","journal-title":"Proc. VLDB Endow."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1145\/2189750.2150984","article-title":"Tarazu: Optimizing mapreduce on heterogeneous clusters","volume":"40","author":"Ahmad","year":"2012","journal-title":"ACM SIGARCH Comput. Archit. News"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"1649","DOI":"10.1109\/TPDS.2016.2587645","article-title":"ishuffle: Improving hadoop performance with shuffle-on-write","volume":"28","author":"Guo","year":"2016","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"98","DOI":"10.1145\/2043164.2018448","article-title":"Managing data transfers in computer clusters with orchestra","volume":"41","author":"Chowdhury","year":"2011","journal-title":"ACM SIGCOMM Comput. Commun. Rev."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Zhang, Z., Cherkasova, L., and Loo, B.T. (2013, January 9\u201312). Performance modeling of mapreduce jobs in heterogeneous cloud environments. Proceedings of the 2013 IEEE Sixth International Conference on Cloud Computing, Washington, DC, USA.","DOI":"10.1109\/CLOUD.2013.107"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Georgiou, Z., Symeonides, M., Trihinas, D., Pallis, G., and Dikaiakos, M.D. (2018, January 17\u201320). Streamsight: A query-driven framework for streaming analytics in edge computing. Proceedings of the 2018 IEEE\/ACM 11th International Conference on Utility and Cloud Computing (UCC), Zurich, Switzerland.","DOI":"10.1109\/UCC.2018.00023"},{"key":"ref_15","unstructured":"Krizhevsky, A., Sutskever, I., and Hinton, G.E. (2012). Imagenet classification with deep convolutional neural networks. Adv. Neural Inf. Process. Syst., 25."},{"key":"ref_16","unstructured":"Attia, M.A., and Tandon, R. (2017). Combating computational heterogeneity in large-scale distributed computing via work exchange. arXiv."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1145\/2847220.2847223","article-title":"Using straggler replication to reduce latency in large-scale parallel computing","volume":"43","author":"Wang","year":"2015","journal-title":"ACM Sigmetrics Perform. Eval. Rev."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"608","DOI":"10.1016\/j.jpdc.2012.12.012","article-title":"Mapreduce with communication overlap (marco)","volume":"73","author":"Ahmad","year":"2013","journal-title":"J. Parallel Distrib. Comput."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"1663","DOI":"10.1109\/TPDS.2016.2627558","article-title":"Leveraging adaptive i\/o to optimize collective data shuffling patterns for big data analytics","volume":"28","author":"Nicolae","year":"2016","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"556","DOI":"10.1109\/TC.2013.216","article-title":"Virtual shuffling for efficient data movement in mapreduce","volume":"64","author":"Yu","year":"2013","journal-title":"IEEE Trans. Comput."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Zaharia, M., Borthakur, D., Sen Sarma, J., Elmeleegy, K., Shenker, S., and Stoica, I. (2010, January 13\u201316). Delay scheduling: A simple technique for achieving locality and fairness in cluster scheduling. Proceedings of the 5th European Conference on Computer Systems, Paris, France.","DOI":"10.1145\/1755913.1755940"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"2856","DOI":"10.1109\/TIT.2014.2306938","article-title":"Fundamental limits of caching","volume":"60","author":"Niesen","year":"2014","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"1029","DOI":"10.1109\/TNET.2014.2317316","article-title":"Decentralized coded caching attains order-optimal memory-rate tradeoff","volume":"23","author":"Niesen","year":"2015","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"ref_24","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_25","doi-asserted-by":"crossref","first-page":"7253","DOI":"10.1109\/TIT.2016.2614722","article-title":"Multi-server coded caching","volume":"62","author":"Shariatpanahi","year":"2016","journal-title":"IEEE Trans. Inf. Theory"}],"container-title":["Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2078-2489\/13\/7\/342\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T23:50:52Z","timestamp":1760140252000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2078-2489\/13\/7\/342"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,15]]},"references-count":25,"journal-issue":{"issue":"7","published-online":{"date-parts":[[2022,7]]}},"alternative-id":["info13070342"],"URL":"https:\/\/doi.org\/10.3390\/info13070342","relation":{},"ISSN":["2078-2489"],"issn-type":[{"type":"electronic","value":"2078-2489"}],"subject":[],"published":{"date-parts":[[2022,7,15]]}}}