Talk Today: Coded Iterative Computing using Substitute Decoding

[Brian DeSilva]

Hi everyone,

This talk may be of interest to anyone who is around for the summer.

Who: Yaoqing Yang (CMU)

Time:  4pm on Thursday (August 8)

Where:  Lewis 208

Title: Coded Iterative Computing using Substitute Decoding

Abstract: Coded computing is a redundancy technique that utilizes the ideas from error-correcting codes to make distributed computing systems robust against failures and slow machines. In this talk, I will first give a brief introduction to the history of coded computing, and talk about some new techniques that we obtained on coded computing for iterative algorithms. We will focus on a coded computing technique called "substitute decoding" for sparse linear systems such as PageRank.  For these sparse systems, codes with dense generator matrices can significantly increase storage costs and codes with low-density generator matrices (LDGM) are preferred. Surprisingly, we show through both theoretical analysis and simulations that when substitute decoding is used, coded iterative computing with extremely low-density codes (2 or 3 non-zeros in each row of the generator matrix) can achieve almost the same convergence rate as noiseless techniques, despite the poor error-correction ability of LDGM codes. Finally, we will show some applications of coded computing in general iterative algorithms.

If you haven't already, please remember to sign up for the new NARC mailing list here.

Future emails will be sent there rather than through the NARC google group.

Best,

Brian