.png){kind=icon}
.png){kind=icon}
Return
On Allocation of Systematic Blocks in Coded Distributed Computing
.png){kind=icon}
PRE
AI
DOI：10.1109/LCOMM.2021.3140100.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Coded distributed computing is used to mitigate the adverse effect of slow workers on the computation time in distributed computing systems. However, using error-correction codes results in encoding and decoding delays. In this work, we consider a systematic maximum-distance separable (MDS) coded matrix-vector multiplication problem with multi-message communication (MMC), where the master assigns multiple sub-tasks to each worker. In this setup, we show that the received systematic outputs can be used to reduce the decoding time by implementing a proper decoding algorithm. To further reduce the decoding time, we use the MMC property that sub-tasks are executed sequentially to propose an allocation of the systematic sub-tasks that significantly increases the number of received systematic outputs. Our results further demonstrate that the reduction in the decoding time is even more significant in applications that require only a partial recovery. In these applications, it suffices to complete a certain percentage of the computation, and using our approach, we show that decoding may be completely avoided.
Keywords:
Decoding
Systematics
Computational modeling
Codes
Distributed computing
Delays
Encoding
Coded distributed computation
decoding time complexity
systematic code
stragglers
partial recovery
Journal
IF:
4.4
Papers:
1.3W
Citations:
2.2W