A Combinatorial Design for Cascaded Coded Distributed Computing on General Networks.
Saved in:
| Title: | A Combinatorial Design for Cascaded Coded Distributed Computing on General Networks. |
|---|---|
| Authors: | Woolsey, Nicholas1 nicholas.woolsey@utah.edu, Chen, Rong-Rong1 rchen@ece.utah.edu, Ji, Mingyue1 mingyue.ji@utah.edu |
| Source: | IEEE Transactions on Communications. Sep2021, Vol. 69 Issue 9, p5686-5700. 15p. |
| Subjects: | Distributed computing, Computer systems |
| Abstract: | Coding theoretic approaches have been developed to significantly reduce the communication load in modern distributed computing system. In particular, coded distributed computing (CDC) introduced by Li et al. can efficiently trade computation resources to reduce the communication load in MapReduce like computing systems. For the more general cascaded CDC, Map computations are repeated at $r$ nodes to significantly reduce the communication load among nodes tasked with computing $Q$ Reduce functions $s$ times. In this paper, we propose a novel low-complexity combinatorial design for cascaded CDC which 1) determines both input file and output function assignments, 2) requires significantly less number of input files and output functions, and 3) operates on heterogeneous networks where nodes have varying storage and computing capabilities. We provide an analytical characterization of the computation-communication tradeoff, from which we show the proposed scheme can outperform the state-of-the-art scheme proposed by Li et al. for the homogeneous networks. Further, when the network is heterogeneous, we show that the performance of the proposed scheme can be better than its homogeneous counterpart. In addition, the proposed scheme is optimal within a constant factor of the information theoretic converse bound while fixing the input file and the output function assignments. [ABSTRACT FROM AUTHOR] |
| Copyright of IEEE Transactions on Communications is the property of IEEE and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
| FullText | Text: Availability: 0 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 153710927 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: A Combinatorial Design for Cascaded Coded Distributed Computing on General Networks. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Woolsey%2C+Nicholas%22">Woolsey, Nicholas</searchLink><relatesTo>1</relatesTo><i> nicholas.woolsey@utah.edu</i><br /><searchLink fieldCode="AR" term="%22Chen%2C+Rong-Rong%22">Chen, Rong-Rong</searchLink><relatesTo>1</relatesTo><i> rchen@ece.utah.edu</i><br /><searchLink fieldCode="AR" term="%22Ji%2C+Mingyue%22">Ji, Mingyue</searchLink><relatesTo>1</relatesTo><i> mingyue.ji@utah.edu</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22IEEE+Transactions+on+Communications%22">IEEE Transactions on Communications</searchLink>. Sep2021, Vol. 69 Issue 9, p5686-5700. 15p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Distributed+computing%22">Distributed computing</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+systems%22">Computer systems</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: Coding theoretic approaches have been developed to significantly reduce the communication load in modern distributed computing system. In particular, coded distributed computing (CDC) introduced by Li et al. can efficiently trade computation resources to reduce the communication load in MapReduce like computing systems. For the more general cascaded CDC, Map computations are repeated at $r$ nodes to significantly reduce the communication load among nodes tasked with computing $Q$ Reduce functions $s$ times. In this paper, we propose a novel low-complexity combinatorial design for cascaded CDC which 1) determines both input file and output function assignments, 2) requires significantly less number of input files and output functions, and 3) operates on heterogeneous networks where nodes have varying storage and computing capabilities. We provide an analytical characterization of the computation-communication tradeoff, from which we show the proposed scheme can outperform the state-of-the-art scheme proposed by Li et al. for the homogeneous networks. Further, when the network is heterogeneous, we show that the performance of the proposed scheme can be better than its homogeneous counterpart. In addition, the proposed scheme is optimal within a constant factor of the information theoretic converse bound while fixing the input file and the output function assignments. [ABSTRACT FROM AUTHOR] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>Copyright of IEEE Transactions on Communications is the property of IEEE and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=153710927 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1109/TCOMM.2021.3087788 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 15 StartPage: 5686 Subjects: – SubjectFull: Distributed computing Type: general – SubjectFull: Computer systems Type: general Titles: – TitleFull: A Combinatorial Design for Cascaded Coded Distributed Computing on General Networks. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Woolsey, Nicholas – PersonEntity: Name: NameFull: Chen, Rong-Rong – PersonEntity: Name: NameFull: Ji, Mingyue IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 09 Text: Sep2021 Type: published Y: 2021 Identifiers: – Type: issn-print Value: 00906778 Numbering: – Type: volume Value: 69 – Type: issue Value: 9 Titles: – TitleFull: IEEE Transactions on Communications Type: main |
| ResultId | 1 |
