Cross Subspace Alignment Codes for Coded Distributed Batch Computation
Cross Subspace Alignment Codes for Coded Distributed Batch Computation
复制标题
DOI：
10.1109/tit.2021.3064827
复制
发表时间：
2019-09
影响因子：
2.5
通讯作者：
Zhuqing Jia;S. Jafar
中科院分区：
文献类型：
--
作者：
Zhuqing Jia;S. Jafar
编码分布式计算的目标是通过编码方案在$S$服务器上有效地分配计算任务，例如矩阵乘法，$N$线性计算或多元多项式求值，使得来自任何$R$服务器的响应（$R$被称为恢复阈值）足以让用户恢复所需的计算值。当前最先进的方法基于专门的矩阵划分（用于矩阵乘法的纠缠多项式（EP）码）或专门的批处理（用于$N$线性计算或多元多项式求值的拉格朗日编码计算（LCC））。我们提出了三个相关类别的代码，跨子空间对齐（CSA）的想法的基础上，最初介绍了安全和私人信息检索的背景下。CSA码的特征在于Cauchy-Vandermonde矩阵结构，其促进沿沿着Vandermonde项的干扰对准，而期望的计算保持沿Cauchy项的沿着可解析。这些代码的统一，推广和改进后，最先进的分布式计算代码。首先，我们介绍CSA码矩阵乘法，产生LCC码作为一个特殊的情况下，并在一般下载限制设置优于LCC码。虽然用于分布式矩阵乘法的矩阵划分方法（EP码）具有灵活的服务器计算延迟的优点，但是批处理方法（CSA、LCC）在通信成本以及每个矩阵乘法的编码和解码复杂度方面具有显著的优势。为了联合收割机的好处，这些方法，我们介绍了广义CSA（GCSA）代码矩阵乘法，桥接极端的矩阵分区和批处理方法，并表现出协同增益，由于交叉子空间对齐。最后，我们介绍了$N$ -CSA代码的$N$ -线性分布式批处理计算和多元批处理多项式的评价。$N$ -CSA码包括LCC码作为特殊情况，并且通常能够在下载约束设置中以高达$N$的因子优于LCC码。还提供了包括$X$ -安全数据和$B$ -拜占庭服务器的$N$ -CSA码的推广。
The goal of coded distributed computation is to efficiently distribute 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 state-of-art approaches are based on either exclusively matrix-partitioning (Entangled Polynomial (EP) Codes for matrix multiplication), or exclusively batch processing (Lagrange Coded Computing (LCC) for $N$ -linear computations or multivariate polynomial evaluations). We present three related classes of codes, based on the idea of Cross-Subspace Alignment (CSA) which was introduced originally in the context of secure and 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 are shown to 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 in download-limited settings. While matrix-partitioning approaches (EP codes) for distributed matrix multiplication have the advantage of flexible server computation latency, batch processing approaches (CSA, LCC) have significant advantages in communication costs as well as encoding and decoding complexity per matrix multiplication. In order to combine the benefits of these approaches, we introduce Generalized CSA (GCSA) codes for matrix multiplication that bridge the extremes of matrix-partitioning and batch processing approaches and demonstrate synergistic gains due to cross subspace alignment. 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 outperforming LCC codes in download-constrained settings by upto a factor of $N$ . Generalizations of $N$ -CSA codes to include $X$ -secure data and $B$ -byzantine servers are also provided.