We propose two coded schemes for the distributed computing problem of
multiplying a matrix by a set of vectors. The first scheme is based on
partitioning the matrix into submatrices and applying maximum distance
separable (MDS) codes to each submatrix. For this scheme, we prove that up to a
given number of partitions the communication load and the computational delay
(not including the encoding and decoding delay) are identical to those of the
scheme recently proposed by Li et al., based on a single, long MDS code.
However, due to the use of shorter MDS codes, our scheme yields a significantly
lower overall computational delay when the delay incurred by encoding and
decoding is also considered. We further propose a second coded scheme based on
Luby Transform (LT) codes under inactivation decoding. Interestingly, LT codes
may reduce the delay over the partitioned scheme at the expense of an increased
communication load. We also consider distributed computing under a deadline and
show numerically that the proposed schemes outperform other schemes in the
literature, with the LT code-based scheme yielding the best performance for the
scenarios considered.

本文介绍两种分布式计算方案：基于 MDS 代码的矩阵乘法分块编码方案和基于 Luby Transform 码的 inactivation 译码方案。数值结果表明，本文所提出的方案在截止日期内的性能优于文献中的其他方案。

用于分布式计算和滞后服务器的块对角和 LT 编码

Block-Diagonal and LT Codes for Distributed Computing With Straggling  Servers

In order to scale economically, data centers are increasingly evolving their
data storage methods from the use of simple data replication to the use of more
powerful erasure codes, which provide the same level of reliability as
replication but at a significantly lower storage cost. In particular, it is
well known that Maximum-Distance-Separable (MDS) codes, such as Reed-Solomon
codes, provide the maximum storage efficiency. While the use of codes for
providing improved reliability in archival storage systems, where the data is
less frequently accessed (or so-called "cold data"), is well understood, the
role of codes in the storage of more frequently accessed and active "hot data",
where latency is the key metric, is less clear.
In this paper, we study data storage systems based on MDS codes through the
lens of queueing theory, and term this the "MDS queue." We analytically
characterize the (average) latency performance of MDS queues, for which we
present insightful scheduling policies that form upper and lower bounds to
performance, and are observed to be quite tight. Extensive simulations are also
provided and used to validate our theoretical analysis. We also employ the
framework of the MDS queue to analyse different methods of performing so-called
degraded reads (reading of partial data) in distributed data storage.

本文研究基于 MDS 码的数据存储系统，通过队列理论分析其表现，并提供上下界的调度策略。同时，利用 MDS 队列的框架分析了分布式数据存储中不同方法执行降级读取的情况。

MDS 队列：分析纠错码的延迟性能

The MDS Queue: Analysing the Latency Performance of Erasure Codes

In distributed storage systems that employ erasure coding, the issue of
minimizing the total {\it communication} required to exactly rebuild a storage
node after a failure arises. This repair bandwidth depends on the structure of
the storage code and the repair strategies used to restore the lost data.
Designing high-rate maximum-distance separable (MDS) codes that achieve the
optimum repair communication has been a well-known open problem. In this work,
we use Hadamard matrices to construct the first explicit 2-parity MDS storage
code with optimal repair properties for all single node failures, including the
parities. Our construction relies on a novel method of achieving perfect
interference alignment over finite fields with a finite file size, or number of
extensions. We generalize this construction to design $m$-parity MDS codes that
achieve the optimum repair communication for single systematic node failures
and show that there is an interesting connection between our $m$-parity codes
and the systematic-repair optimal permutation-matrix based codes of Tamo {\it
et al.} \cite{Tamo} and Cadambe {\it et al.} \cite{PermCodes_ISIT, PermCodes}.

使用 Hadamard 矩阵构建首个具有最优恢复性能的 2 - 偶校验 MDS 存储代码，扩展到设计实现系统节点失效的 m - 奇偶校验 MDS 代码。