Multi-layer Distributed Coding Solutions for Large-scale Distributed Computing

Abstract: In distributed computing models, where some helper nodes assist the master in a large-scale computation, a big challenge is when these helpers straggle. The straggling of even a single helper node can significantly increase the processing time. Therefore, coded distributed computing has been proposed as a solution in many recent studies. Unfortunately, in some scenarios, the decoding complexity at the master is so significant that it undermines the benefit of distributing the computation. To allow for distributed computing in these cases, we propose a multi-layer coding strategy that allows some helpers to assist with the decoding. In this thesis, we focus on two scenarios, (1) when an extra layer of helpers are introduced to help with the master's decoding, and (2) fitting a distributed coding scheme when the computation naturally requires multiple layers with shuffling (for example FFT). In both scenarios, we propose a fully-coded structure that tolerates straggling in each step. Moreover, using low-complexity codes such as Raptor codes to further reduce the master's decoding load is studied.