Cross Subspace Alignment Codes for Coded Distributed Batch Computation

Understand

Coded distributed batch computation distributes a computation task, such as matrix multiplication, $N$-linear computation, or multivariate polynomial evaluation, across $S$ servers through a coding scheme, such that the response from any $R$ servers ($R$ is called the recovery threshold) is sufficient for the user to recover the desired computed value.

• Current approaches are based on either exclusively matrix-partitioning (Entangled Polynomial (EP) Codes for matrix multiplication), or exclusively batch processing (Lagrange Coded Computing (LCC)).
• We present three related classes of codes, based on the idea of Cross-Subspace Alignment (CSA) which was introduced originally in the context of private information retrieval.
• CSA codes are characterized by a Cauchy-Vandermonde matrix structure that facilitates interference alignment along Vandermonde terms, while the desired computations remain resolvable along the Cauchy terms.