Math PhD @ UIUC

I have one work on distributed computation.

Abbreviation | Title |
---|---|

PlutoCharon20 | Parity-Checked Strassen Algorithm |

PlutoCharon20 deals with distributed matrix-matrix multiplication (MMM) where the workers might crash or straggle. By MMM we mean that we want to compute $C=AB$, where $A, B$ are huge matrices. By crashing and straggling we mean that an entry multiplication, for instance $A_{12}\times A_{23}$, might be available very late, if at all.

To compensate, one needs to hire more-than-necessary workers and asks them to do redundant computations. A possibility to generate redundancy is to draw random vectors $g, h$ and then ask extra workers to compute $(gA)\times(Bh)$ on top of $A\times B$.

The contribution of PlutoCharon20 is three-fold.
One: We obverse that the computation of $A\times B$
can be carried-out by fast matrix multiplication (FMM).
This construction is named **Pluto codes**.
Two: Applying Pluto codes recursively,
we obtain a code that behaves like tensor product codes.
Three: The computation of $(gA)\times(Bh)$,
if $g, h$ are matrices, can be carried-out by FMM.
This is named **Charon construction**.