Sökning: id:"swepub:oai:research.chalmers.se:3562c763-d206-4822-9c8d-ad9b1899b26e" >
Block-Diagonal and ...
Block-Diagonal and LT Codes for Distributed Computing With Straggling Servers
-
- Severinson, Albin, 1993 (författare)
- Chalmers tekniska högskola,Chalmers University of Technology,Simula UiB
-
- Graell i Amat, Alexandre, 1976 (författare)
- Chalmers tekniska högskola,Chalmers University of Technology
-
- Rosnes, Eirik, 1975 (författare)
- Simula UiB
-
(creator_code:org_t)
- 2019
- 2019
- Engelska.
-
Ingår i: IEEE Transactions on Communications. - 0090-6778 .- 1558-0857. ; 67:3, s. 1739-1753
- Relaterad länk:
-
https://research.cha... (primary) (free)
-
visa fler...
-
https://research.cha...
-
https://research.cha...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- We propose two coded schemes for the distributed computing problem of multiplying a matrix by a set of vectors. The first scheme is based on partitioning the matrix into submatrices and applying maximum distance separable (MDS) codes to each submatrix. For this scheme, we prove that up to a given number of partitions the communication load and the computational delay (not including the encoding and decoding delay) are identical to those of the scheme recently proposed by Li et al., based on a single, long MDS code. However, due to the use of shorter MDS codes, our scheme yields a significantly lower overall computational delay when the delay incurred by encoding and decoding is also considered. We further propose a second coded scheme based on Luby Transform (LT) codes under inactivation decoding. Interestingly, LT codes may reduce the delay over the partitioned scheme at the expense of an increased communication load. We also consider distributed computing under a deadline and show numerically that the proposed schemes outperform other schemes in the literature, with the LT code-based scheme yielding the best performance.
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences (hsv//eng)
- TEKNIK OCH TEKNOLOGIER -- Elektroteknik och elektronik -- Telekommunikation (hsv//swe)
- ENGINEERING AND TECHNOLOGY -- Electrical Engineering, Electronic Engineering, Information Engineering -- Telecommunications (hsv//eng)
- TEKNIK OCH TEKNOLOGIER -- Elektroteknik och elektronik -- Kommunikationssystem (hsv//swe)
- ENGINEERING AND TECHNOLOGY -- Electrical Engineering, Electronic Engineering, Information Engineering -- Communication Systems (hsv//eng)
Nyckelord
- Block-diagonal coding
- maximum distance separable codes
- distributed computing
- straggling servers.
- machine learning algorithms
- computational delay
- Luby Transform codes
- decoding delay
Publikations- och innehållstyp
- art (ämneskategori)
- ref (ämneskategori)
Hitta via bibliotek
Till lärosätets databas