Cross Subspace Alignment Codes for Coded Distributed Batch Computation

Abstract

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. These codes unify, generalize and improve upon the state-of-art codes for distributed computing. First we introduce CSA codes for matrix multiplication, which yield LCC codes as a special case, and are shown to outperform LCC codes in general over strictly download-limited settings. Next, we introduce Generalized CSA (GCSA) codes for matrix multiplication that bridge the extremes of matrix-partitioning and batch processing approaches. Finally, we introduce $N$-CSA codes for $N$-linear distributed batch computations and multivariate batch polynomial evaluations. $N$-CSA codes include LCC codes as a special case, and are in general capable of achieving significantly lower downloads than LCC codes due to cross-subspace alignment. Generalizations of $N$-CSA codes to include $X$-secure data and $B$-byzantine servers are also obtained.

arXiv commentImproved recovery threshold for GCSA codes and added discussion of server latency constraints

References in corpus (13)

• Speeding Up Distributed Machine Learning Using Codes
• Polynomial Codes: an Optimal Design for High-Dimensional Coded Matrix Multiplication
• Private Information Retrieval from Coded Databases with Colluding Servers
• Lagrange Coded Computing: Optimal Design for Resiliency, Security and Privacy
• Coded Sparse Matrix Multiplication
• Linear Symmetric Private Information Retrieval for MDS Coded Distributed Storage with Colluding Servers
• Private Information Retrieval from MDS Coded Databases with Colluding Servers under Several Variant Models
• Fundamental Limits of Coded Linear Transform
• Rate-Efficiency and Straggler-Robustness through Partition in Distributed Two-Sided Secure Matrix Computation
• On the Capacity of Secure Distributed Batch Matrix Multiplication
• $X$-secure $T$-private Information Retrieval from MDS Coded Storage with Byzantine and Unresponsive Servers
• On the Asymptotic Capacity of $X$-Secure $T$-Private Information Retrieval with Graph Based Replicated Storage
• Coded Fourier Transform

Cited by in corpus (7)

• Minimizing Latency for Secure Coded Computing Using Secret Sharing via Staircase Codes
• Entangled Polynomial Codes for Secure, Private, and Batch Distributed Matrix Multiplication: Breaking the "Cubic" Barrier
• Double Blind $T$-Private Information Retrieval
• On the Capacity of Secure Distributed Batch Matrix Multiplication
• Bivariate Polynomial Codes for Secure Distributed Matrix Multiplication
• A locality-based approach for coded computation
• GCSA Codes with Noise Alignment for Secure Coded Multi-Party Batch Matrix Multiplication