Erasure Correction of Scalar Codes
in the Presence of Stragglers
Netanel Raviv⋆, Yuval Cassuto†, Rami Cohen†, and Moshe Schwartz‡
⋆

Department of Electrical Engineering, California Institute of Technology, Pasadena 91125, CA, USA
Faculty of Electrical Engineering, Technion - Israel Institute of Technology, Haifa 3200003, Israel
‡
Electrical and Computer Engineering, Ben-Gurion University of the Negev, Beer Sheva 8410501, Israel
netanel.raviv@gmail.com, ycassuto@ee.technion.ac.il, rc@technion.ac.il, schwartz@ee.bgu.ac.il

arXiv:1802.02265v1 [cs.IT] 6 Feb 2018

†

Abstract—Recent advances in coding for distributed storage
systems have reignited the interest in scalar codes over extension
fields. In parallel, the rise of large-scale distributed systems has
motivated the study of computing in the presence of stragglers,
i.e., servers that are slow to respond or unavailable.
This paper addresses storage systems that employ linear
codes over extension fields. A common task in such systems
is the reconstruction of the entire dataset using sequential
symbol transmissions from multiple servers, which are received
concurrently at a central data collector. However, a key bottleneck in the reconstruction process is the possible presence of
stragglers, which may result in excessive latency. To mitigate the
straggler effect, the reconstruction should be possible given any
sufficiently large set of sequentially received symbols, regardless
of their source. In what follows, an algebraic framework for
this scenario is given, and a number of explicit constructions
are provided. Our main result is a construction that uses a
recursive composition of generalized Reed-Solomon codes over
smaller fields. In addition, we show links of this problem to
Gabidulin codes and to universally decodable matrices.

I. I NTRODUCTION
Scalar codes over extension fields are prevalent in many
real-world distributed storage systems as a means to combat
node failures. However, even when no node failures occur,
distributed systems are prone to the detrimental effect of
stragglers, i.e., nodes that are slow to respond. In this paper,
we provide a mathematical modeling for the straggler effect
in systems which employ scalar codes, and suggest several
code constructions to mitigate this effect.
For a prime power q let Fq be a field with q elements,
and for an integer α let Fqα be its algebraic extension of
degree α. Assume that a dataset x ∈ Fkqα is coded across n
storage nodes by using a (scalar) linear code over Fqα , where
each node contains a symbol in Fqα .
Upon the reconstruction of x, each node transmits its
content to the data collector sequentially, i.e., one q-ary
symbol after the other1 . The data collector receives these
transmissions concurrently, and wishes to reconstruct the
dataset as soon as possible without having to wait for all
transmissions to complete. Note that due to the stochastic
nature of the system and the nodes’ workload, the amount
of downloadable bits from each node is unknown a priori
neither to the nodes nor to the data collector. Our objective
in this paper is to construct scalar codes that minimize this
reconstruction time.
To this end, consider an ordered basis ω , (ω1 , . . . , ωα )
of Fqα over Fq , where each element of Fqα is identified by the
The work of Netanel Raviv was supported in part by the postdoctoral
fellowship of the Center for the Mathematics of Information (CMI), Caltech,
and in part by the Lester-Deutsch postdoctoral fellowship. This research was
supported in part by the Israel Science Foundation under grant no. 130/14,
1676/14 and the US-Israel Binational Science Foundation.
1 In the underlying system q-ary symbols may be generally mapped to bits.

vector of coefficients in its representation by ω. Consequently,
for any i ∈ [n] P
, {1, . . . , n}, the transmission of a codeword
α
symbol ci =
j=1 ci,j ωi ∈ Fqα to the data collector is
assumed to contain the q-ary coefficients ci,j , which arrive
free of errors and in a decreasing order of their j index. Notice
that the sequential arrival of the information bits translates to
left-justified erasures of the coefficients in the representation
of every codeword symbol by the fixed basis ω; that is, some
(possibly empty) prefix of the coefficient vector is missing
from the response of every server.
Clearly, elementary information-theoretic arguments imply
that at least αk symbols over Fq must be obtained at the
data collector for a unique reconstruction to be possible. For
a given positive integer m, we are interested in constructing
linear codes, of maximum possible dimension, such that x can
be reconstructed from any set of αn − m symbols over Fq
that arrive sequentially at the data collector.
This problem may be seen as a generalization of erasure
correction in the usual sense. For example, note that when
the erased symbols are confined to n − k servers and m =
α(n − k), then this problem reduces to ordinary (n − k)erasure correction; and clearly, this can be obtained by employing any [n, k]qα MDS code (i.e., a code of length n
and dimension k over Fqα , which attains the Singleton
bound with equality). Furthermore, it is also possible to
use an [αn, αn − m]q MDS code, which can correct any
m-erasures (i.e., not necessarily sequential). However, this
approach does not yield linear codes over Fqα , and requires
a fairly large base field size.
This paper focuses on linear [n, n − 1]qα codes that are
capable of alleviating the straggler effect (formal definitions
are given in the sequel). In cases where a code construction
remains elusive, we suggest a relaxation of the problem by
restricting the set of possible patterns of missing symbols.
Yet, we are able to prove that codes in the stronger model
exist for all parameters n and α, as long as q is sufficiently
large.
This paper is structured as follows. Previous work regarding
the use of scalar codes for distributed storage systems is
discussed in Section II, and formal definitions are given in
Section III. A code construction for n = 2, any q, and any
even α is given in Section IV, in which the existence of longer
codes is also proved. Two relaxations of the problem are
discussed in Section V, which stem from linear independence
over subfields, from generalized Reed-Solomon codes, and
from Gabidulin codes. These constructions yield codes of any
length that are resilient to more restricted types of erasure
patterns. Finally, an intriguing connection to universally decodable matrices is studied in Section VI, and open problems
are discussed in Section VII.

II. P REVIOUS WORK
Scalar codes for distributed storage, which were studied
in a series of recent works [1], [2], [5], [7], [9], [13], often
outperform their vector counterparts by utilizing the extension
field structure to speed up encoding and decoding. Yet, all of
the aforementioned works have focused on node repair (i.e.,
reconstruction of one or more codeword symbols in the case of
node failure), rather than on reconstructing the entire dataset,
and did not address the straggler effect.
The paper [10] addresses the reconstruction of an entire
dataset that is stored by a scalar MDS code. In [10], the
number of downloadable field elements from each node is
assumed to be known prior to transmission, and hence, each
node computes a function with that many output symbols.
In our paper however, the nodes compose their transmission
without any knowledge regarding its arrival, other than it
being sequential.
Hierarchical erasures (also known as partial erasures) also
emerge in the study of flash memories [3], [4]. A flash
memory cell can store 2α distinct charge levels, that are read
by applying a series of α threshold tests. It often happens
that this series of threshold tests discontinues abruptly due
to hardware failures, a scenario which clearly correspond to
a hierarchical erasure. The work of [3], [4] studies LDPC
coding under these erasures, analyzes the optimal edge-label
distributions and decoding threshold, and discusses the finite
length case. In particular, these works have laid the grounds
for the algebraic ideas that are developed hereafter.
III. P RELIMINARIES
Informally speaking, a linear code C ⊆ Fnqα is called
an m-hierarchical erasure correcting code over ω if the data
collector is capable of reconstructing every codeword c =
(c1 , . . . , cn ) ∈ C from any set of prefixes of the representations of the ci ’s according to ω, which contains at least αn−m
symbols of Fq overall.
To define this notion formally, for positive integers n and m
n
let Nm
be the set of nonnegative integer vectors of length n
n
describes the
whose sum of entries is m. An element t ∈ Nm
number of missing q-ary symbols from each of the n nodes,
and hence it is called an erasure pattern.
One of the common definitions of an (ordinary) erasure
correcting code is a linear subspace that does not contain
a codeword of small Hamming weight. The following can
be seen as a generalization of this definition to the case of
n
hierarchical erasures. To this end, for t = (t1 , . . . , tn ) ∈ Nm
,
let

n
Similarly, for T ⊆ Nm
a code C ⊆ Fnqα is T -correcting if
there exists a basis ω such that C ∩Xt (ω) = {0} for all t ∈ T .
Notice that if m = ℓα for some positive integer ℓ, then an mcorrecting code is also an ℓ-erasure correcting code in the
ordinary sense, and hence its dimension is upper bounded
by n − ℓ. In this paper we mostly focus on α-correcting codes
and T correcting codes for T ⊆ Nαn .

IV. α- CORRECTING

CODES

A. α-correcting codes of length two
In this section we provide a construction of an α-correcting
code of length two for any q and any even α.
Theorem 1. For any q and any even α, the code
C , {c ∈ F2qα |(1, b) · c⊤ = 0}
is α-correcting, where b is a root of an irreducible quadratic
polynomial over Fq .
To prove this theorem, the following lemmas are given. In
what follows, for an element b ∈ Fqα and an even α, an
ordered basis ω = (ω1 , . . . , ωα ) of Fqα over Fq is called bsymmetric if ωα−i+1 = bωi for all i ∈ [α/2]. Further, let b ∈
Fqα be a root of an irreducible quadratic polynomial P (x) =
x2 + a1 x + a0 over Fq .
Lemma 2. For any even α and any q, there exists a bsymmetric basis of Fqα over Fq .
Proof. Denote α = 2t ℓ, where ℓ is odd and t ≥ 1. We prove
this claim by induction on t. For t = 1 let ω1 , . . . , ωℓ be a
basis of Fqℓ over Fq . Notice that P (x) remains irreducible
when seen as a polynomial over Fqℓ ; otherwise, we have
that P (x) is a minimal polynomial of some element in Fqℓ ,
whose degree does not divide ℓ, a contradiction. Hence, we
have that b ∈
/ Fqℓ , and thus (ω1 , . . . , ωℓ , bωℓ , . . . , bω1 ) is a bsymmetric basis of Fqα over Fq .
For t > 1, by the induction hypothesis we have a bsymmetric basis (ω1 , . . . , ωα/2 ) of Fqα/2 over Fq . By choosing any γ ∈ Fqα \ Fqα/2 , it is readily verified that
ω , (γω1 , ω1 , . . . , γωα/4 , ωα/4 ,
ωα/4+1 , γωα/4+1 , . . . , ωα/2 , γωα/2 )
= (γω1 , ω1 , . . . , γωα/4 , ωα/4 ,
bωα/4 , γbωα/4 , . . . , bω1 , γbω1 )
is a b-symmetric basis of Fqα over Fq , where the last equality
follows from the induction hypothesis.

Xt (ω) , {(ωi , 0, . . . , 0)}i∈[t1 ] ⊕
{(0, ωi , 0, . . . , 0)}i∈[t2 ] ⊕
···
{(0, . . . , 0, ωi )}i∈[tn ] ,

basis ω over which C is an m-hierarchical erasure correcting
code.

Lemma 3. If ω = (ωi )i∈[α] is b-symmetric, then
(1)

where each vector represented by (·) is an n-vector,
h·i denotes span over Fq , and ⊕ is the sum of subspaces that intersect trivially. For example, for n = 3,
m = 4, and t = (2, 1, 1) ∈ N43 we have Xt (ω) =
h(ω1 , 0, 0), (ω2 , 0, 0), (0, ω1 , 0), (0, 0, ω1)i. Note that each element of Xt (ω) corresponds to an Fnqα word that is mapped
to the all-0 word by an m-hierarchical erasure.
Definition 1. A code C ⊆ Fnqα is called an m-hierarchical
erasure correcting code over ω if C ∩Xt (ω) = {0} for all t ∈
n
Nm
. In addition, C is called m-correcting if there exists a

hbω1 , bω2 , . . . , bωt i = hωα , ωα−1 . . . , ωα−t+1 i
for all t ∈ [α].
Proof. If t ≤ α/2, then the claim follows from the definition
of a b-symmetric basis. If t ≥ α/2 + 1, we have that
E
E D
D
α/2
hbω1 , . . . , bωt i = {bωi }i=1 + {bωi }ti=α/2+1
E
E D
D
2
t
= {ωi }α
i=α/2+1 + {b ωα−i+1 }i=α/2+1
E
E D
D
t
= {ωi }α
i=α/2+1 + {(−a1 b − a0 )ωα−i+1 }i=α/2+1

E
E D
D
t
+
{−a
ω
−
a
ω
}
= {ωi }α
1 i
0 α−i+1 i=α/2+1
i=α/2+1
E
E D
D
α/2
α
= {ωi }i=α/2+1 + {ωi }i=α−t+1

V. T - CORRECTING

A. Balanced erasure patterns from subfield independence

= hωα , ωα−1 , . . . , ωα−t+1 i.

Lemma 2 and Lemma 3 imply the correctness of Theorem 1
as follows.
Proof. (of Theorem 1) Let ω be a b-symmetric basis of Fqα
over Fq , as guaranteed by Lemma 2. Assume for contradiction
that there exists t ∈ Nα2 and a nonzero codeword c =
(c1 , c2 ) ∈ C such that c ∈ Xt (ω). This readily implies that
c1 ∈ hω1 , . . . , ωt1 i,
c2 ∈ hω1 , . . . , ωt2 i, and
c1 + bc2 = 0.

CODES

(2)
(3)
(4)

Furthermore, Lemma 3 and Eq. (3) imply that bc2 is
in hωα , ωα−1 , . . . , ωα−t2 +1 i. Alongside (2), this implies
that (4) is a sum of elements from trivially intersecting
subspaces that results in zero, and hence c1 and c2 are zero
as well, a contradiction.
In the full version of this paper, the [2, 1]qα α-correcting
code in this subsection will be extended to an [n, 1]qα αcorrecting code for any even α ≥ n − 1 and any q ≥ n − 1.
Furthermore, this code is applicable for correcting partial
erasures in flash-memory LDPC codes, by assigning the edge
labels 1 and b to a check node of degree two.
B. Existence of α-correcting codes over large fields
In this subsection it is shown that for any n there exists
an [n, n − 1]qα α-correcting code, provided that q is large
enough. In what follows, let X(ω) , ∪t∈Nαn Xt (ω), and let
S , {kerFqα (x)|x ∈ X(ω)}, where
kerFqα (x) , {y ∈ Fnqα |y · x⊤ = 0}.
The proof of existence relies on the following simple lemmas,
and some of the respective proofs are omitted due to space
constraints.
 α
Lemma 4. |X(ω)| ≤ α+n−1
·q .
n−1

Lemma 5. |S| ≤ |X(ω)|/(q − 1).

Proof. Since X(ω) is a union of subspaces over Fq , it
follows that it is closed under multiplication by elements
of Fq . The claim follows since kerFqα (v) = kerFqα (λv) for
any v ∈ Fnqα and any nonzero λ ∈ Fqα , and in particular, any
nonzero λ ∈ Fq .
Fnqα

Lemma 6. The size of a set of hyperplanes in
(i.e.,
subspaces of dimension n − 1 of Fnqα ) whose union is the
entire space is at least q α + 1.

Theorem 7. If q ≥ α+n−1
+ 1 then there exists an (n − 1)n−1
dimensional α-correcting code in Fnqα .
Proof. According to Lemma 4, Lemma 5, and the bound
on q, it follows that |S| ≤ q α . Therefore, the union
of the hyperplanes in S is not the entire space Fnqα by
Lemma 6. Hence, there exists h , (h1 , . . . , hn ) ∈ Fnqα such
that h · x⊤ 6= 0 for every nonzero x ∈ X(ω). In turn, this
implies that kerFqα (h) ∩ X(ω) = {0}, and hence kerFqα (h)
in an n − 1 dimensional α-correcting code.

In this subsection, we restrict our attention to α = 2β for
some positive integer2 β and to balanced erasure patterns.
An erasure pattern t ∈ Nαn is called balanced if there exists
an integer 0 ≤ i ≤ min{β, log n}, where the logarithm is
to base 2, and a set J ⊆ [n] with |J| = 2i , such that for
all j ∈ [n]
(
α
j ∈ J,
i
tj = 2
0 otherwise.
For example, if n = 4 then the erasure patterns
(α/2, 0, α/2, 0) and (α/4, α/4, α/4, α/4) are balanced,
whereas (α/2, α/4, α/4, 0) is not. The set of all balanced
erasure patterns is denoted by TB .
We consider bases ω = (ω1 , . . . , ωα ) of Fqα over Fq that
we call recursive, i.e., bases such that ω1 , . . . , ωα/2i =
Fqα/2i for all 0 ≤ i ≤ β. For a vector h = (h1 , . . . , hn ) ∈ Fnqα
and a code C , kerFqα (h), imposing these restrictions reduces
the problem to one of linear independence of subsets of
the hi ’s over certain subfields of Fqα , as we now show.
Lemma 8. The code C is TB -correcting over a recursive
basis ω if and only if for every 1 ≤ i ≤ min{β, log n}, any 2i subset of {hj }j∈[n] is a linearly independent set over Fqα/2i .
Proof. Assume that every 2i -subset of {hj }nj=1 is linearly
independent over Fqα/2i for every 0 ≤ i ≤ min{β, log n}.
If C is not TB -correcting, then there exists a nonzero c =
(c1 , c2 , . . . , cn ) in C and an erasure pattern t ∈ TB such
that c ∈ C ∩ Xt . By the definition of TB , it follows that
there exists an integer i and a set J ⊆ [n] of size 2i such
that tj = α/2i if j ∈ J, and zero otherwise. Hence, we have
that
cj ∈ ω1 , . . . , ωα/2i = Fqα/2i for all j ∈ J,
P
which implies that j∈J hj cj = 0. However, this sum is a
linear combination of a 2i -subset of {hj }j∈[n] over Fqα/2i , a
contradiction. The proof of the inverse direction is similar.
In what follows we construct an [n, n − 1]qα TB -correcting
code, for any n and any α over a base field Fq with q ≥ n−1.
To this end, let {bi }i∈[β] ⊆ Fqα such that Fqα/2i−1 =
Fqα/2i (bi ) for all i ∈ [β], i.e., we consider each subfield Fqα/2i−1 as a vector space of dimension two over Fqα/2i
by fixing the basis {1, bi }.
For 0 ≤ i ≤ β and a 2i × n matrix M over Fqα/2i , let
Hi (M ) , UH(M ) + bi LH(M ),
where UH and LH denote the upper and lower halves
of M , respectively. Further, for an integer 1 ≤ i ≤ β
and an α × n matrix M over Fq let H(i) (M ) ,
Hβ−i+1 (· · · (Hβ−1 (Hβ (M )))), and let H(0) (M ) = M .
Finally, we say that a matrix V is a generalized Vandermonde (GV) matrix if V = M · diag(d) for some
Vandermonde matrix M and some vector d = (d1 , . . . , dn )
with nonzero entries. Note that a GV matrix V ∈ Fr×s
for
q
some integers s ≥ r is also an MDS matrix, i.e., all its r × r
submatrices are invertible.
2 In fact, any α of the form ℓ2β can be treated similarly, by applying the
′
same techniques on (q ′ )α , where q ′ , q ℓ and α′ , 2β .

Theorem 9. For an integer α which is a power of two and
an integer n, let q be a prime power such that q ≥ n − 1,
and let V ∈ Fα×n
be a Vandermonde matrix. Then, for
q
h = (h1 , h2 , . . . , hn ) , H(β) (V ), the code C , kerFqα (h) is
a TB -correcting code.
The proof of this theorem requires the following lemma.
Lemma 10. For all 1 ≤ i ≤ β, the matrix H(i) (V ) is a GV
matrix over Fq2i .
Proof. We prove this claim by induction, in which the base
(α/2i )×n
case i = 0 is clear. Assume that Vi , H(i) (V ) ∈ Fq2i
is
a GV matrix, and let Ui and Li be its lower and upper halves,
respectively. Since Vi is a GV matrix, there exists a Vander(α/2i )×n
and a vector d ∈ (F∗q2i )n
monde matrix M ∈ F 2i
q
such that Vi = M diag(d). Hence, it follows that Ui =
UH(M ) diag(d) and Li = LH(M ) diag(d), and therefore
Vi+i = H(i+1) (V ) = Hβ−i (Vi )
= Ui + bβ−i Li
= UH(M ) diag(d) + bβ−i LH(M ) diag(d).
Now, since M is a Vandermonde matrix, it follows
that LH(M ) = UH(M ) diag(x) for some x = (x1 , . . . , xn )
in (F∗q2i )n , and thus
Vi+i = UH(M ) diag(d) + bβ−i UH(M ) diag(x) diag(d)
= UH(M ) (diag(d) + bβ−i diag(x) diag(d))
= UH(M ) diag((1 + bβ−i x) ⊙ diag(d)),
where ⊙ denotes the pointwise product of vectors (also called
Hadamard product), and 1 is the all 1’s vector. Since UH(M )
is a Vandermonde matrix, to finish the proof we are only left
to show the entries of (1 + bβ−i x) ⊙ diag(d) are nonzero.
Assuming otherwise, it follows that (1 + bβ−i xj )dj = 0 for
some j ∈ [n]; and since dj 6= 0 and xj 6= 0, we have
−1
that bβ−i = −x−1
∈ Fq2i and bβ−i ∈
/
j . However, −xj
α
= Fq2i , a contradiction.
F 2β−i
q

The recursive basis which is used to prove Theorem 9 is
the one which is induced by the {bi }i∈[β] ; that is, the basis
is ω , Wβ , where W0 , (1) and Wi+1 , Wi |(bβ−i+1 · Wi ),
and | denotes concatenation.
Proof. (of Theorem 9) According to Lemma 8, it suffices to
show that for any 1 ≤ i ≤ min{log n, β}, any 2i -subset
of {hj }j∈[n] is linearly independent over Fqα/2i . For any
i

i

×2
such i, let J ⊆ [n] be a subset of size 2i , and let HJ ∈ Fq2α/2
i
be the matrix whose columns are the representations of all
elements in {hj }j∈J over the (ordered) basis Wi . Notice
that {hj }j∈J is a linearly independent set over Fqα/2i if and
only if HJ is invertible. However, HJ is a 2i × 2i submatrix
i
×n
of H(β−i) (V ) ∈ F2qα/2
i , which is a GV matrix by Lemma 10,
and hence also an MDS matrix. Thus, HJ is invertible, and
the claim follows.

Remark 1. The following is a corollary to the definition
of {hj }j∈[n] in Theorem 9.
hj =

β 
Y

i=1

α/2i

1 + b i aj



Remark 2. The construction in this section is closely related to a classical coding theoretic notion called alternant
codes [8, Sec. 5.5]. An [n, k]q Generalized Reed-Solomon
(GRS) code is a linear code whose parity check matrix is
an (n − k) × n GV matrix over Fq . An alternant code Calt is
defined as C ∩ F n , where C is an [n, k]q GRS code and F is
a subfield of Fq .
Let α < n, and for any 0 ≤ i ≤ β let Ci be the right kernel
of H(i) (V ) over Fq2i . Notice that Lemma 10 shows that Ci
is an [n, n − α/2i ]q2i GRS code. Furthermore, it is readily
verified that Cj is an alternant code of Ci whenever j ≤ i.
Lemma 10 also implies that the codes we construct here have
the property that all the alternant codes in the hierarchy are
of maximum distance, and in cases where q is prime, these
are all possible alternant codes.
B. Bounded erasure patterns from Gabidulin codes
In this section we restrict our attention to n ≤ α and to
erasure patterns we call bounded, but allow more than α
erasures overall. For positive integers r and m, an erasure
pattern t ∈ Nnm is called r-bounded if tj ≤ r for all j ∈ [n],
and let Tr ⊆ Nnm be the set of r-bounded erasures. Note that
bounded erasure patterns are more restrictive than balanced
ones, since balanced patterns allow in particular a full symbol
erasure. In what follows it is shown that Gabidulin codes
are Tr -correcting, and the size of the resulting codes is in
correspondence with r.
For the next theorem, recall that a linearized polynomial
is a polynomial over Fqα in which all nonzero coefficients
i
correspond to monomials of the form xq for some nonnegative integer i. For a linearized polynomial f , let its qdegree be degq (f ) , logq (deg f ). It is widely known that
any function from Fqα to itself, which is linear over Fq ,
corresponds to a linearized polynomial.
Theorem 11. For nonnegative integers ℓ, n, and α such
that n ≤ α and r < n, the code
Gab[n, n − r] , {(f (ω1 ), . . . , f (ωn ))|
f is linearized and degq (f ) < n − r}.
is Tr -correcting.
Proof. We show that Gab[n, n−r]∩Xt = {0} for all t ∈ Tr .
Assuming otherwise, we have a pattern t ∈ Tr and a nonzero
linearized polynomial f of q-degree less than n − r such that
f (ωj ) ∈ ω1 , . . . , ωtj , for all j ∈ [n].

Since f is a linearized polynomial and since t ∈ Tr , Eq. (5)
implies that f (hω1 , . . . , ωn i) ⊆ hω1 , . . . , ωr i, which in turn
implies that dim ker(f ) ≥ n − r. Thus, f has more roots than
its degree, which is a contradiction.
Note that n ≤ α is necessary to have n linearly independent
evaluation points for Gab[n, n − r]. Further, the dimension
of Gab[n, n − r] over Fqα is n − r, and hence, for this
construction to be nontrivial we must have that r < n.
Moreover, since every t ∈ Tr sums to m, the necessary
condition m ≤ n(n − 1) is inevitable. Finally, we emphasize
that this construction applies to any q.
VI. U NIVERSALLY

for all j ∈ [n],

where a1 , . . . , an are distinct elements in Fq .

(5)

DECODABLE MATRICES

The problems addressed in this paper are intimately related
to universally decodable matrices (UDMs) [6], [12], which are
a useful tool in error correction of slow-fading channels [11].

Definition 2 ([6, Def. 1]). The matrices A1 , . . . , An ∈ Fα×α
q
are called Universally Decodable Matrices (UDMs) if for
every t = (t1 , . . . , tn ) ∈ Nαn the following condition is
satisfied: the α×α matrix composed of the first t1 rows of A1 ,
the first t2 rows of A2 , ..., the first tα rows of Aα has full
rank.
In the following theorem let Jα be the α × α matrix which
contains 1’s in its anti-diagonal, and zero elsewhere.
Theorem 12 ([12, Prop. 14]). Let n, m, and α be positive
integers, let q be a prime power such that q ≥ n−1, and let γ
be a primitive element in Fq . Then, the following are α × m
UDMs over Fq
A0 , Iα , A1 , Jα , A2 , . . . , An−1 where
 
b i(b−a)
(Ai+2 )a,b =
γ
for (i, a, b) ∈ [n − 2] × [α] × [m].
a
UDMs can be used to obtain codes with hierarchical erasure
correction capabilities that are not necessarily linear over Fqα .
It is fairly easy to show that if {Ai }i∈[n] are α × m UDMs,
then

(j)

let Ai be the matrix such that Ai is the expansion of hi ωj
Pα
(j)
over the basis ω, i.e., hi ωj =
ℓ=1 (Ai )ℓ ωℓ . Assuming
for contradiction that A1 , . . . , An are not UDMs, we have an
element t = (t1 , . . . , tn ) ∈ Nαn and a nonzero vector v ∈ Fα
q
such that
 (1:t ) 
A1 1
 (1:t2 ) 

 A2

v·
 ..  = 0.
 . 
(1:tn )

An

Partition v to n consecutive parts v1 , v2 , . . . , vn of
sizes t1 , . . . , tn , respectively, let ci , vi · (ω1 , . . . , ωti ) for
all i ∈ [n], and let c , (c1 , . . . , cn ). Hence, it is readily
verified that c is a nonzero codeword in C∩Xt , a contradiction
to C being an α-correcting code.
Finally, we note that Theorem 1 can alternatively be proved
by a direct application of Theorem 13, and the details are left
to the curious reader.

Proof. Let A1 , . . . , An ∈ Fqα×α be UDMs with eigenvalues h1 , . . . , hn ∈ Fqα , respectively, all of which correspond
to the eigenvector ω, i.e.,

VII. D ISCUSSION
In this paper an algebraic framework was given for erasure
correction of scalar codes in distributed systems under the
straggler effect. In the general case, a construction of a code of
length two was given, and the existence of longer codes was
proved. In more restricted settings, two code constructions
were given which apply to any code length. Further results
will be given in the full version of this paper.
Many natural questions remain widely open. Aside of
finding a general construction of a kα-correcting [n, n − k]qα
code for k > 1, an intriguing research direction is studying
this question without the assumption that the non-erased bits
are error free, and finding the respective error-correction
radius. Another challenging direction is to find scalar codes
that are capable of mitigating the straggler effect during node
repair.

Ai ω = hi ω for all i ∈ [n].

R EFERENCES

n
⊤
⊤
⊤
C , {x ∈ (Fα
q ) |(A0 , A1 , . . . , An−1 ) · x = 0},

is an m-correcting code that is not necessarily linear over Fqα ,
and hence suffers from higher encoding complexity3.
For the case m = α, there exists an intriguing connection
between UDMs and α-correcting codes.
Theorem 13. For h1 , . . . , hn ∈ Fqα , a code C ⊆ {c ∈
Fnqα |(h1 , . . . , hn ) · c⊤ = 0} is an α-correcting code if and
only if there exists a set A1 , . . . , An of UDMs over Fq such
that for any i ∈ [n], the element hi is an eigenvalue of Ai
with a corresponding eigenvector ω , (ω1 , . . . , ωα )⊤ .

(6)

If C is not α-correcting, it follows that there exist t ∈ Nαn and
a nonzero codeword c = (c1 , c2 , . . . , cn ) ∈ C such that ci ∈
hω1 , . . . , ωti i for all i ∈ [n], and therefore

(j)

hi ci ∈ hhi ω1 , . . . , hi ωti i
E
D
(6)
(t )
(1)
= Ai ω, . . . , Ai i ω ,

where Ai denotes the j-th row of Ai . In turn, this implies
that for all i ∈ [n] there exists a nonzero vector vi ∈ Ftqi
(1:t )
such that vi Ai i = hi ci , where for any positive integers r
(s:r)
stands for the submatrix of Ai
and s, the notation Ai
which consists of rows s through r. Thus, we have a nonzero
vector v , v1 |v2 | . . . |vn ∈ Fα
q that satisfies
 (1:t ) 
A1 1
 (1:t2 ) 
X
 X
 A2
(t )

hi ci = 0,
(7)
vi Ai i =
v·
 ..  =
 .  i∈[n]
i∈[n]
(1:t )
An n
which is a contradiction to {Ai }ni=1 being UDMs.
Conversely, assume that C is α-correcting, and define
matrices A1 , . . . , An ∈ Fα×α
as follows. For every i ∈ [n],
q
3 Assuming

that multiplication in Fqα requires O(α log α) field operations.

[1] B. Bartan and M. Wootters, “Repairing multiple failures for scalar MDS
codes,” arXiv:1707.02241 [cs.IT], 2017.
[2] A. Chowdhury and A. Vardy, “Improved schemes for asymptotically
optimal repair of MDS codes,” arXiv:1710.01867 [cs.IT], 2017.
[3] R. Cohen and Y. Cassuto, “Iterative decoding of LDPC codes over the
q-ary partial erasure channel,” IEEE Trans. on Inf. Th. vol. 62, no. 5,
pp. 2658–2672, 2016.
[4] R. Cohen, N. Raviv, and Y. Cassuto, “LDPC codes over the q-ary multibit channel,” arXiv:1706.09146 [cs.IT], 2017.
[5] S. H. Dau, I. M. Duursma, H. M. Kiah, and O. Milenkovic, “Repairing
Reed-Solomon codes with multiple erasures,” arXiv:1612.01361 [cs.IT],
2016.
[6] A. Ganesan and P. O. Vontobel, “On the existence of universally
decodable matrices,” IEEE Trans. on Inf. Th., vol. 53, no. 7, pp. 2572–
2575, 2007.
[7] V. Guruswami and M. Wootters, “Repairing Reed-Solomon codes,”
IEEE Trans. on Inf. Th., vol. 63, no. 9, pp. 5684–5698, 2017.
[8] R. Roth, Introduction to coding theory, Cambridge University Press,
2006.
[9] I. Tamo, M. Ye, and A. Barg, “Optimal repair of Reed-Solomon codes:
achieving the cut-set bound,” IEEE Ann. Symp. on Found. of Comp. Sci.
(FOCS), pp. 216–227, 2017.
[10] ——, “Fractional decoding: Error correction from partial information,”
IEEE Intl. Symp. on Inf. Th. (ISIT), pp. 998–1002, 2017.
[11] S. Tavildar and P. Viswanath, “Approximately universal codes over
slow-fading channels,” IEEE Trans. on Inf. Th., vol. 52, no. 7, pp. 3233–
3258, 2006.
[12] P. O. Vontobel and A. Ganesan, “On universally decodable matrices for
spacetime coding,” Designs, Codes, and Cryptography, vol. 41, no. 3,
pp. 325–342, 2006.
[13] M. Ye and A. Barg, “Repairing Reed-Solomon codes: Universally achieving the cut-set bound for any number of erasures,”
arXiv:1710.07216 [cs.IT], 2017.

