{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,13]],"date-time":"2026-05-13T14:12:32Z","timestamp":1778681552434,"version":"3.51.4"},"reference-count":37,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2023,2,27]],"date-time":"2023-02-27T00:00:00Z","timestamp":1677456000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"the Water Conservancy Project of Jiangsu Province","award":["2021053"],"award-info":[{"award-number":["2021053"]}]},{"name":"the Water Conservancy Project of Jiangsu Province","award":["61872171"],"award-info":[{"award-number":["61872171"]}]},{"name":"the Water Conservancy Project of Jiangsu Province","award":["B210201053"],"award-info":[{"award-number":["B210201053"]}]},{"name":"the Water Conservancy Project of Jiangsu Province","award":["BK20190058"],"award-info":[{"award-number":["BK20190058"]}]},{"name":"the Water Conservancy Project of Jiangsu Province","award":["FNSRFP-2021-ZD-07"],"award-info":[{"award-number":["FNSRFP-2021-ZD-07"]}]},{"name":"the National Natural Science Foundation of China","award":["2021053"],"award-info":[{"award-number":["2021053"]}]},{"name":"the National Natural Science Foundation of China","award":["61872171"],"award-info":[{"award-number":["61872171"]}]},{"name":"the National Natural Science Foundation of China","award":["B210201053"],"award-info":[{"award-number":["B210201053"]}]},{"name":"the National Natural Science Foundation of China","award":["BK20190058"],"award-info":[{"award-number":["BK20190058"]}]},{"name":"the National Natural Science Foundation of China","award":["FNSRFP-2021-ZD-07"],"award-info":[{"award-number":["FNSRFP-2021-ZD-07"]}]},{"DOI":"10.13039\/501100012226","name":"the Fundamental Research Funds for the Central Universities","doi-asserted-by":"publisher","award":["2021053"],"award-info":[{"award-number":["2021053"]}],"id":[{"id":"10.13039\/501100012226","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100012226","name":"the Fundamental Research Funds for the Central Universities","doi-asserted-by":"publisher","award":["61872171"],"award-info":[{"award-number":["61872171"]}],"id":[{"id":"10.13039\/501100012226","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100012226","name":"the Fundamental Research Funds for the Central Universities","doi-asserted-by":"publisher","award":["B210201053"],"award-info":[{"award-number":["B210201053"]}],"id":[{"id":"10.13039\/501100012226","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100012226","name":"the Fundamental Research Funds for the Central Universities","doi-asserted-by":"publisher","award":["BK20190058"],"award-info":[{"award-number":["BK20190058"]}],"id":[{"id":"10.13039\/501100012226","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100012226","name":"the Fundamental Research Funds for the Central Universities","doi-asserted-by":"publisher","award":["FNSRFP-2021-ZD-07"],"award-info":[{"award-number":["FNSRFP-2021-ZD-07"]}],"id":[{"id":"10.13039\/501100012226","id-type":"DOI","asserted-by":"publisher"}]},{"name":"the Natural Science Foundation of Jiangsu Province","award":["2021053"],"award-info":[{"award-number":["2021053"]}]},{"name":"the Natural Science Foundation of Jiangsu Province","award":["61872171"],"award-info":[{"award-number":["61872171"]}]},{"name":"the Natural Science Foundation of Jiangsu Province","award":["B210201053"],"award-info":[{"award-number":["B210201053"]}]},{"name":"the Natural Science Foundation of Jiangsu Province","award":["BK20190058"],"award-info":[{"award-number":["BK20190058"]}]},{"name":"the Natural Science Foundation of Jiangsu Province","award":["FNSRFP-2021-ZD-07"],"award-info":[{"award-number":["FNSRFP-2021-ZD-07"]}]},{"name":"the Future Network Scientific Research Fund Project","award":["2021053"],"award-info":[{"award-number":["2021053"]}]},{"name":"the Future Network Scientific Research Fund Project","award":["61872171"],"award-info":[{"award-number":["61872171"]}]},{"name":"the Future Network Scientific Research Fund Project","award":["B210201053"],"award-info":[{"award-number":["B210201053"]}]},{"name":"the Future Network Scientific Research Fund Project","award":["BK20190058"],"award-info":[{"award-number":["BK20190058"]}]},{"name":"the Future Network Scientific Research Fund Project","award":["FNSRFP-2021-ZD-07"],"award-info":[{"award-number":["FNSRFP-2021-ZD-07"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>In wireless distributed computing systems, worker nodes connect to a master node wirelessly and perform large-scale computational tasks that are parallelized across them. However, the common phenomenon of straggling (i.e., worker nodes often experience unpredictable slowdown during computation and communication) and packet losses due to severe channel fading can significantly increase the latency of computational tasks. In this paper, we consider a heterogeneous, wireless, distributed computing system performing large-scale matrix multiplications which form the core of many machine learning applications. To address the aforementioned challenges, we first propose a random linear network coding (RLNC) approach that leverages the linearity of matrix multiplication, which has many salient properties, including ratelessness, maximum straggler tolerance and near-ideal load balancing. We then theoretically demonstrate that its latency converges to the optimum in probability when the matrix size grows to infinity. To combat the high encoding and decoding overheads of the RLNC approach, we further propose a practical variation based on batched sparse (BATS) code. The effectiveness of our proposed approaches is demonstrated by numerical simulations.<\/jats:p>","DOI":"10.3390\/e25030428","type":"journal-article","created":{"date-parts":[[2023,2,28]],"date-time":"2023-02-28T02:28:09Z","timestamp":1677551289000},"page":"428","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Network Coding Approaches for Distributed Computation over Lossy Wireless Networks"],"prefix":"10.3390","volume":"25","author":[{"given":"Bin","family":"Fan","sequence":"first","affiliation":[{"name":"Key Laboratory of Water Big Data Technology of Ministry of Water Resources, Hohai University, Nanjing 211100, China"},{"name":"School of Computer and Information, Hohai University, Nanjing 211100, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4577-8882","authenticated-orcid":false,"given":"Bin","family":"Tang","sequence":"additional","affiliation":[{"name":"Key Laboratory of Water Big Data Technology of Ministry of Water Resources, Hohai University, Nanjing 211100, China"},{"name":"School of Computer and Information, Hohai University, Nanjing 211100, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhihao","family":"Qu","sequence":"additional","affiliation":[{"name":"Key Laboratory of Water Big Data Technology of Ministry of Water Resources, Hohai University, Nanjing 211100, China"},{"name":"School of Computer and Information, Hohai University, Nanjing 211100, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Baoliu","family":"Ye","sequence":"additional","affiliation":[{"name":"Key Laboratory of Water Big Data Technology of Ministry of Water Resources, Hohai University, Nanjing 211100, China"},{"name":"School of Computer and Information, Hohai University, Nanjing 211100, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2023,2,27]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"2179","DOI":"10.1561\/2200000083","article-title":"Advances and open problems in federated learning","volume":"14","author":"Kairouz","year":"2021","journal-title":"Found. Trends Mach. Learn."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Drolia, U., Guo, K., and Narasimhan, P. (2017, January 12\u201314). Precog: Prefetching for image recognition applications at the edge. Proceedings of the Second ACM\/IEEE Symposium on Edge Computing, San Jose, CA, USA.","DOI":"10.1145\/3132211.3134456"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"144","DOI":"10.1109\/MCOM.2012.6122545","article-title":"Wireless distributed computing: A survey of research challenges","volume":"50","author":"Datla","year":"2012","journal-title":"IEEE Commun. Mag."},{"key":"ref_4","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_5","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1145\/2408776.2408794","article-title":"The tail at scale","volume":"56","author":"Dean","year":"2013","journal-title":"Commun. ACM"},{"key":"ref_6","unstructured":"Zaharia, M., Konwinski, A., Joseph, A.D., Katz, R.H., and Stoica, I. (2008, January 8\u201310). Improving MapReduce performance in heterogeneous environments. Proceedings of the 8th USENIX Symposium on Operating Systems Design and Implementation, San Diego, CA, USA."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Wang, D., Joshi, G., and Wornell, G. (2014, January 16\u201320). Efficient task replication for fast response times in parallel computation. Proceedings of the 2014 ACM International Conference on Measurement and Modeling of Computer Systems, Austin, TX, USA.","DOI":"10.1145\/2591971.2592042"},{"key":"ref_8","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_9","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":"Comm. ACM"},{"key":"ref_10","first-page":"10","article-title":"Spark: Cluster computing with working sets","volume":"10","author":"Zaharia","year":"2010","journal-title":"HotCloud"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"1514","DOI":"10.1109\/TIT.2017.2736066","article-title":"Speeding up distributed machine learning using codes","volume":"64","author":"Lee","year":"2017","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Ferdinand, N., and Draper, S.C. (2018, January 17\u201322). Hierarchical coded computation. Proceedings of the 2018 IEEE International Symposium on Information Theory, Vail, CO, USA.","DOI":"10.1109\/ISIT.2018.8437473"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Kiani, S., Ferdinand, N., and Draper, S.C. (2018, January 17\u201322). Exploitation of stragglers in coded computation. Proceedings of the 2018 IEEE International Symposium on Information Theory, Vail, CO, USA.","DOI":"10.1109\/ISIT.2018.8437871"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1145\/3524298","article-title":"Rateless codes for near-perfect load balancing in distributed matrix-vector multiplication","volume":"65","author":"Mallick","year":"2022","journal-title":"Commun. ACM"},{"key":"ref_15","unstructured":"Luby, M. (2002, January 16\u201319). LT codes. Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, Vancouver, BC, Canada."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"2551","DOI":"10.1109\/TIT.2006.874390","article-title":"Raptor codes","volume":"52","author":"Shokrollahi","year":"2006","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"8204","DOI":"10.1109\/TWC.2021.3091465","article-title":"Coded Wireless Distributed Computing With Packet Losses and Retransmissions","volume":"20","author":"Han","year":"2021","journal-title":"IEEE Trans. Wirel. Commun"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"1204","DOI":"10.1109\/18.850663","article-title":"Network information flow","volume":"46","author":"Ahlswede","year":"2000","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"4413","DOI":"10.1109\/TIT.2006.881746","article-title":"A random linear network coding approach to multicast","volume":"52","author":"Ho","year":"2006","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"5322","DOI":"10.1109\/TIT.2014.2334315","article-title":"Batched sparse codes","volume":"60","author":"Yang","year":"2014","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Park, H., Lee, K., Sohn, J.Y., Suh, C., and Moon, J. (2018, January 17\u201322). Hierarchical coding for distributed computing. Proceedings of the 2018 IEEE International Symposium on Information Theory, Vail, CO, USA.","DOI":"10.1109\/ISIT.2018.8437669"},{"key":"ref_22","unstructured":"Lin, Z., Narra, K.G., Yu, M., Avestimehr, S., and Annavaram, M. (2019). Train where the data is: A case for bandwidth efficient coded training. arXiv."},{"key":"ref_23","unstructured":"Yu, Q., Maddah-Ali, M., and Avestimehr, S. (2017, January 4\u20139). Polynomial codes: An optimal design for high-dimensional coded matrix multiplication. Proceedings of the 31st Conference on Neural Information Processing Systems (NIPS 2017), Long Beach, CA, USA."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Ramamoorthy, A., Tang, L., and Vontobel, P.O. (2019, January 7\u201312). Universally decodable matrices for distributed matrix-vector multiplication. Proceedings of the 2019 IEEE International Symposium on Information Theory (ISIT), Paris, France.","DOI":"10.1109\/ISIT.2019.8849451"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"2684","DOI":"10.1109\/TIT.2021.3137266","article-title":"Numerically stable coded matrix computations via circulant and rotation matrix embeddings","volume":"68","author":"Ramamoorthy","year":"2022","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Wu, Y. (2006, January 9\u201314). A trellis connectivity analysis of random linear network coding with buffering. Proceedings of the IEEE International Symposium on Information Theory, Seattle, WA, USA.","DOI":"10.1109\/ISIT.2006.261636"},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Motwani, R., and Raghavan, P. (1995). Randomized Algorithms, Cambridge University Press.","DOI":"10.1017\/CBO9780511814075"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1186\/s13634-015-0297-8","article-title":"Expander chunked codes","volume":"1","author":"Tang","year":"2015","journal-title":"EURASIP J. Adv. Signal Process."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"605","DOI":"10.1109\/TNET.2017.2787726","article-title":"An LDPC approach for chunked network codes","volume":"26","author":"Tang","year":"2018","journal-title":"IEEE ACM Trans. Netw."},{"key":"ref_30","unstructured":"Feizi, S., Lucani, D.E., and M\u00e9dard, M. (March, January 29). Tunable sparse network coding. Proceedings of the 22th International Zurich Seminar on Communications (IZS), Z\u00fcrich, Switzerland."},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Garrido, P., S\u00f8rensen, C.W., Lucani, D.E., and Ag\u00fcero, R. (2016, January 4\u20138). Performance and complexity of tunable sparse network coding with gradual growing tuning functions over wireless networks. Proceedings of the 2016 IEEE 27th Annual International Symposium on Personal, Indoor, and Mobile Radio Communications (PIMRC), Valencia, Spain.","DOI":"10.1109\/PIMRC.2016.7794915"},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Garrido, P., G\u00f3mez, D., Lanza, J., and Ag\u00fcero, R. (2016, January 22\u201327). Exploiting sparse coding: A sliding window enhancement of a random linear network coding scheme. Proceedings of the 2016 IEEE International Conference on Communications (ICC), Kuala Lumpur, Malaysia.","DOI":"10.1109\/ICC.2016.7510783"},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"20183","DOI":"10.1109\/ACCESS.2017.2757241","article-title":"Caterpillar RLNC (CRLNC): A practical finite sliding window RLNC approach","volume":"5","author":"Wunderlich","year":"2017","journal-title":"IEEE Access"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"410","DOI":"10.1109\/LCOMM.2019.2895867","article-title":"Design of optimized sliding-window BATS codes","volume":"23","author":"Yang","year":"2019","journal-title":"IEEE Commun. Lett."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"118","DOI":"10.1016\/j.comcom.2022.01.004","article-title":"Lightweight network-coded ARQ: An approach for ultra-reliable low latency communication","volume":"185","author":"Karetsi","year":"2022","journal-title":"Comput. Commun."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"54276","DOI":"10.1109\/ACCESS.2022.3175815","article-title":"FSW: Fulcrum sliding window coding for low-latency communication","volume":"10","author":"Tasdemir","year":"2022","journal-title":"IEEE Access"},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"929","DOI":"10.1109\/TC.2015.2435792","article-title":"Near-optimal one-sided scheduling for coded segmented network coding","volume":"65","author":"Tang","year":"2015","journal-title":"IEEE Trans. Comput."}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/25\/3\/428\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T18:43:59Z","timestamp":1760121839000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/25\/3\/428"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,2,27]]},"references-count":37,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2023,3]]}},"alternative-id":["e25030428"],"URL":"https:\/\/doi.org\/10.3390\/e25030428","relation":{},"ISSN":["1099-4300"],"issn-type":[{"value":"1099-4300","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,2,27]]}}}