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

• Author / Creator

  Yazdanialahabadi, Arash

• 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.

• Subjects / Keywords

  • cloud computing
  • decoding complexity
  • coded distributed computing
  • distributed decoding
  • heterogeneous network
  • multi-layer structure
  • computational complexity
  • error correction code
  • Fourier transform
  • distributed computing

• Graduation date

  Fall 2020

• Type of Item

  Thesis

• Degree

  Master of Science

• DOI

  https://doi.org/10.7939/r3-ad8t-en72

• License

  Permission is hereby granted to the University of Alberta Libraries to reproduce single copies of this thesis and to lend or sell such copies for private, scholarly or scientific research purposes only. Where the thesis is converted to, or otherwise made available in digital form, the University of Alberta will advise potential users of the thesis of these terms. The author reserves all other publication and other rights in association with the copyright in the thesis and, except as herein before provided, neither the thesis nor any substantial portion thereof may be printed or otherwise reproduced in any material form whatsoever without the author's prior written permission.