Entangled Polynomial Codes for Secure, Private, and Batch Distributed Matrix Multiplication: Breaking the "Cubic" Barrier

Abstract

In distributed matrix multiplication, a common scenario is to assign each worker a fraction of the multiplication task, by partitioning the input matrices into smaller submatrices. In particular, by dividing two input matrices into $m$-by-$p$ and $p$-by-$n$ subblocks, a single multiplication task can be viewed as computing linear combinations of $pmn$ submatrix products, which can be assigned to $pmn$ workers. Such block-partitioning based designs have been widely studied under the topics of secure, private, and batch computation, where the state of the arts all require computing at least "cubic" ($pmn$) number of submatrix multiplications. Entangled polynomial codes, first presented for straggler mitigation, provides a powerful method for breaking the cubic barrier. It achieves a subcubic recovery threshold, meaning that the final product can be recovered from \emph{any} subset of multiplication results with a size order-wise smaller than $pmn$. In this work, we show that entangled polynomial codes can be further extended to also include these three important settings, and provide a unified framework that order-wise reduces the total computational costs upon the state of the arts by achieving subcubic recovery thresholds.

arXiv commentTo appear in ISIT 2020

References in corpus (14)

• Speeding Up Distributed Machine Learning Using Codes
• A family of optimal locally recoverable codes
• Polynomial Codes: an Optimal Design for High-Dimensional Coded Matrix Multiplication
• Lagrange Coded Computing: Optimal Design for Resiliency, Security and Privacy
• CodedPrivateML: A Fast and Privacy-Preserving Framework for Distributed Machine Learning
• Rate-Efficiency and Straggler-Robustness through Partition in Distributed Two-Sided Secure Matrix Computation
• On the Capacity of Secure Distributed Matrix Multiplication
• Cross Subspace Alignment Codes for Coded Distributed Batch Computation
• On the Upload versus Download Cost for Secure and Private Matrix Multiplication
• On the Capacity of Secure Distributed Batch Matrix Multiplication
• Secure Coded Multi-Party Computation for Massive Matrix Operations
• Uplink-Downlink Tradeoff in Secure Distributed Matrix Multiplication
• Private Secure Coded Computation
• Coded FFT and Its Communication Overhead

Cited by in corpus (5)

• A locality-based approach for coded computation
• Rateless Codes for Private Distributed Matrix-Matrix Multiplication
• Improved Constructions for Secure Multi-Party Batch Matrix Multiplication
• GCSA Codes with Noise Alignment for Secure Coded Multi-Party Batch Matrix Multiplication
• Field Trace Polynomial Codes for Secure Distributed Matrix Multiplication