Coded Parallel Transmission for Half-Duplex Distributed Computing
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...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Published: |
Multidisciplinary Digital Publishing Institute
2022
|
| Online Access: | https://hdl.handle.net/1721.1/144037 |
| _version_ | 1826190969826967552 |
|---|---|
| author | Zai, Qixuan Yuan, Kai Wu, Youlong |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Zai, Qixuan Yuan, Kai Wu, Youlong |
| author_sort | Zai, Qixuan |
| collection | MIT |
| description | 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 <i>K</i>. Moreover, the communication delay of CDC is a monotonically increasing function of <i>K</i>, while the communication delay of our scheme decreases as <i>K</i> increases, indicating that the proposed scheme can make better use of the computing resources. |
| first_indexed | 2024-09-23T08:48:05Z |
| format | Article |
| id | mit-1721.1/144037 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T08:48:05Z |
| publishDate | 2022 |
| publisher | Multidisciplinary Digital Publishing Institute |
| record_format | dspace |
| spelling | mit-1721.1/1440372023-01-24T21:42:24Z Coded Parallel Transmission for Half-Duplex Distributed Computing Zai, Qixuan Yuan, Kai Wu, Youlong Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science 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 <i>K</i>. Moreover, the communication delay of CDC is a monotonically increasing function of <i>K</i>, while the communication delay of our scheme decreases as <i>K</i> increases, indicating that the proposed scheme can make better use of the computing resources. 2022-07-25T18:47:40Z 2022-07-25T18:47:40Z 2022-07-15 2022-07-25T16:32:23Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/144037 Information 13 (7): 342 (2022) PUBLISHER_CC http://dx.doi.org/10.3390/info13070342 Creative Commons Attribution https://creativecommons.org/licenses/by/4.0/ application/pdf Multidisciplinary Digital Publishing Institute Multidisciplinary Digital Publishing Institute |
| spellingShingle | Zai, Qixuan Yuan, Kai Wu, Youlong Coded Parallel Transmission for Half-Duplex Distributed Computing |
| title | Coded Parallel Transmission for Half-Duplex Distributed Computing |
| title_full | Coded Parallel Transmission for Half-Duplex Distributed Computing |
| title_fullStr | Coded Parallel Transmission for Half-Duplex Distributed Computing |
| title_full_unstemmed | Coded Parallel Transmission for Half-Duplex Distributed Computing |
| title_short | Coded Parallel Transmission for Half-Duplex Distributed Computing |
| title_sort | coded parallel transmission for half duplex distributed computing |
| url | https://hdl.handle.net/1721.1/144037 |
| work_keys_str_mv | AT zaiqixuan codedparalleltransmissionforhalfduplexdistributedcomputing AT yuankai codedparalleltransmissionforhalfduplexdistributedcomputing AT wuyoulong codedparalleltransmissionforhalfduplexdistributedcomputing |