Coded Distributed Computing With Partial Recovery

DOI10.1109/TIT.2021.3133791zbMATH Open1495.68020arXiv2007.02191OpenAlexW4206267449MaRDI QIDQ5080036

Emre Ozfatura, Sennur Ulukus, Deniz Gunduz

Publication date: 30 May 2022

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: Coded computation techniques provide robustness against straggling workers in distributed computing. However, most of the existing schemes require exact provisioning of the straggling behaviour and ignore the computations carried out by straggling workers. Moreover, these schemes are typically designed to recover the desired computation results accurately, while in many machine learning and iterative optimization algorithms, faster approximate solutions are known to result in an improvement in the overall convergence time. In this paper, we first introduce a novel coded matrix-vector multiplication scheme, called coded computation with partial recovery (CCPR), which benefits from the advantages of both coded and uncoded computation schemes, and reduces both the computation time and the decoding complexity by allowing a trade-off between the accuracy and the speed of computation. We then extend this approach to distributed implementation of more general computation tasks by proposing a coded communication scheme with partial recovery, where the results of subtasks computed by the workers are coded before being communicated. Numerical simulations on a large linear regression task confirm the benefits of the proposed distributed computation scheme with partial recovery in terms of the trade-off between the computation accuracy and latency.

Full work available at URL: https://arxiv.org/abs/2007.02191

zbMATH Keywords

coded communication scheme with partial recoverycoded computation with partial recovery

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Distributed systems (68M14)

Related Items (3)

Coded Computing: Mitigating Fundamental Bottlenecks in Large-Scale Distributed Computing and Machine Learning ⋮ Constructing Better KEMs with Partial Message Recovery ⋮ A coding theorem for distributed computation

This page was built for publication: Coded Distributed Computing With Partial Recovery

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5080036)