$st$-Min Cut and is in P, and $\textsc{MinCSP}(=,\Gamma_{s})$ for
$s\in\mathbb{N}$ corresponds to $s$-Edge Multiway Cut, the restriction of Edge
Multiway Cut to $s$ terminals, which for $s\geq 3$ is NP-hard but FPT.

In this sense, studying singleton expansions of equality languages allows us
to consider MinCSPs that may be intermediate between Multiway Cut and
Multicut.

Unfortunately, our main conclusion is that nothing novel occurs in this range.
Let us first provide the explicit characterization of all properties under
consideration for $\textsc{MinCSP}(\Gamma^{+})$, since these cases are
relatively manageable. Say that $\Gamma$ is _positive conjunctive_ if $\Gamma$
is both conjunctive and constant, i.e., every relation $R\in\Gamma$ is defined
as a conjunction of positive literals, and _positive conjunctive and
connected_ if it is additionally split, i.e., the literals $(x_{i}=x_{j})$ in
the definition of a relation $R(x_{1},\ldots,x_{r})\in\Gamma$, if viewed as
edges $x_{i}x_{j}$ in a graph, form a connected graph.

######  Theorem 54.

Let $\Gamma$ be an equality language. The following hold.

  * •

$\textsc{CSP}(\Gamma^{+})$ is in P if $\Gamma$ is Horn, and NP-hard otherwise

  * •

$\textsc{MinCSP}(\Gamma^{+})$ is NP-hard

  * •

$\textsc{MinCSP}(\Gamma^{+})$ has a polynomial-time constant-factor
approximation if $\Gamma$ is strictly negative or if $\Gamma$ is positive
conjunctive, and otherwise it has no constant-factor approximation under UGC

  * •

$\textsc{MinCSP}(\Gamma^{+})$ is FPT if either every relation in $\Gamma$ is
$\textnormal{\sf NEQ}_{3}$ or split, or $\Gamma$ is strictly negative,
otherwise it is W[1]-hard

  * •

$\textsc{MinCSP}(\Gamma^{+})$ has a constant-factor FPT approximation if
$\Gamma$ is negative, and otherwise it is Hitting Set-hard

The cases for $\Gamma_{c}^{+}$, $c\in\mathbb{N}$ are more involved, and
require additional definitions. Let us provide the statements in multiple
steps. Recall that $\textsc{MinCSP}(\Gamma)$ and $\textsc{MinCSP}(\Delta)$ are
_equivalent_ if there are cost-preserving reductions in between the problems
in both directions. We first observe that if $\Gamma$ implements $\neq$ and
$=$, then we can “emulate” arbitrarily many constants via auxiliary variables
(Lemma 58), and $\textsc{MinCSP}(\Gamma^{\prime})$ maps back to
$\textsc{MinCSP}(\Gamma)$ for any singleton expansion $\Gamma^{\prime}$ of
$\Gamma$. Now Theorem 14 and Lemma 16 give the following.

######  Lemma 55.

Let $\Gamma^{\prime}$ be a singleton expansion of an equality language
$\Gamma$. If $\Gamma$ is not Horn or constant, then
$\textsc{CSP}(\Gamma^{\prime})$ is NP-hard. If $\Gamma$ is Horn but not
strictly negative or constant, then $\textsc{MinCSP}(\Gamma^{\prime})$ is
equivalent to $\textsc{MinCSP}(\Gamma)$. Otherwise $\Gamma$ is strictly
negative or constant (and not both).

For strictly negative languages $\Gamma$, all the positive properties
mentioned in Theorem 54 of course translate to
$\textsc{MinCSP}(\Gamma^{\prime})$ for any singleton extension
$\Gamma^{\prime}$ of $\Gamma$.

######  Lemma 56.

Let $\Gamma^{\prime}$ be a singleton expansion of a finite strictly negative
equality language $\Gamma$. Then $\textsc{CSP}(\Gamma^{\prime})$ is in P and
$\textsc{MinCSP}(\Gamma^{\prime})$ is NP-hard, FPT, and has a constant-factor
approximation.

Finally, we assume that $\Gamma$ is constant. For $c\in\mathbb{N}$, let the
_$c$ -slice_ of $\Gamma$ be the language

$\Delta=\\{R\cap[c]^{r(R)}\mid R\in\Gamma\\}$

where $r(R)$ is the arity of $R$. For $c=2$, we will also interpret this as a
Boolean language. The language $\Delta$ is _trivial_ if for every relation
$R\in\Delta$, of arity $r$, either $R=\emptyset$ or $R=[c]^{r}$. We generalize
the notions of _positive conjunctive_ and _positive conjunctive and connected_
to $\Delta$ in the natural way. Finally, a Boolean language is _affine_ if
every relation in it can be modelled as the set of solutions to a system of
affine linear equations over GF(2). We state the remaining cases.

######  Theorem 57.

Let $\Gamma$ be a constant equality language and $c\in\mathbb{N}$. Let
$\Delta$ be the $c$-slice of $\Gamma$. If $c=1$ then
$\textsc{MinCSP}(\Gamma_{c}^{+})$ is in P. Otherwise the following hold.

  * •

If $\Gamma$ has a retraction to domain $[c]$ then
$\textsc{MinCSP}(\Gamma_{c}^{+})$ is equivalent to
$\textsc{MinCSP}(\Delta_{c}^{+})$.

  * •

If $\Gamma$ has no retraction to domain $[c]$ but is Horn, then
$\textsc{CSP}(\Gamma_{c}^{+})$ is in P but $\textsc{MinCSP}(\Gamma_{c}^{+})$
is Hitting Set-hard

  * •

Otherwise $\textsc{CSP}(\Gamma_{c}^{+})$ is NP-hard.

Furthermore, assume that $\Gamma$ has a retraction to domain $[c]$. If $c\geq
3$, then this implies that $\Delta$ is positive conjunctive. Furthermore the
following hold.

  * •

If $\Delta$ is trivial, then $\textsc{MinCSP}(\Gamma_{c}^{+})$ is in P

  * •

If $\Delta$ is non-trivial, positive conjunctive and connected, then
$\textsc{MinCSP}(\Gamma_{c}^{+})$ is in P for $c=2$, and NP-hard but FPT and
constant-factor approximable for $c\geq 3$

  * •

If $\Delta$ is positive conjunctive but not connected, then
$\textsc{MinCSP}(\Gamma_{c}^{+})$ is W[1]-hard but constant-factor
approximable

  * •

If $c=2$ and $\Delta$ is affine but not positive conjunctive, then
$\textsc{CSP}(\Gamma_{2}^{+})$ is in P but $\textsc{MinCSP}(\Gamma_{c}^{+})$
has a cost-preserving reduction from Nearest Codeword

  * •

Otherwise $c=2$ and $\textsc{CSP}(\Gamma_{2}^{+})$ is NP-hard

This theorem in particular refines Theorem 7 from Section 1.

###  7.1 The first step

Let us begin by showing that if $\Gamma$ implements $=$ and $\neq$ then the
singleton expansion over $\Gamma$ adds no additional power.

######  Lemma 58.

Let $\Gamma$ be an equality language that implements $=$ and $\neq$. Then
there is a cost-preserving reduction from $\textsc{MinCSP}(\Gamma^{+})$ to
$\textsc{MinCSP}(\Gamma)$.

###### Proof.

Let $I$ be an instance of $\textsc{MinCSP}(\Gamma^{+})$ and let
$C\subset\mathbb{N}$ be the set of constants $i$ used in assignment
constraints $v=i$ in $I$. Create a new set of variables $T=\\{t_{i}\mid i\in
C\\}$ and add a crisp constraint $t\neq t^{\prime}$ for all distinct pairs
$t,t^{\prime}\in T$. Replace every constraint $(x=i)$ in $I$ by an
implementation of $(x=t_{i})$, and keep all other constraints unchanged. Let
$I^{\prime}$ be the output instance produced. We show that this reduction is
cost-preserving. On the one hand, let $\alpha$ be an assignment to $V(I)$.
Define an assignment $\alpha^{\prime}$ to $V(I^{\prime})$ by extending
$\alpha$ by $\alpha(t_{i})=i$ for every $i\in C$. Then $\alpha$ and
$\alpha^{\prime}$ have the same cost. On the other hand, let $\alpha^{\prime}$
be an assignment to $V(I^{\prime})$ with finite cost. Since $I^{\prime}$
consists of only equality-language constraints, we may apply any bijunction
over $\mathbb{N}$ to $\alpha^{\prime}$ and retain an assignment that satisfies
the same set of constraints. In particular, since $\alpha^{\prime}$ has finite
cost it must hold that $\alpha^{\prime}(t)\neq\alpha^{\prime}(t^{\prime})$ for
every distinct pair $t,t^{\prime}\in T$. We may then apply a bijunction to
$\alpha^{\prime}$ such that $\alpha^{\prime}(t_{i})=i$ for every $i\in C$. Now
letting $\alpha$ be the restriction of $\alpha^{\prime}$ to the variables
$V(I)$ produces an assignment for $I$ of the same cost as $\alpha^{\prime}$.
Finally, assume that $I^{\prime}$ has no finite-cost solutions. Then by the
above, the same holds for $I$, as otherwise a finite-cost solution to $I$
could be transformed to a finite-cost solution to $I^{\prime}$. ∎

We may thus focus on languages that are either constant or strictly negative:
By Theorem 14, if $\Gamma$ is not constant and not Horn, then
$\textsc{CSP}(\Gamma)$ is NP-hard, and by Lemma 16, if $\Gamma$ is not
constant and not strictly negative but is Horn, then Lemma 58 applies. Recall
in particular that every strictly negative language is Horn.

Our main focus will be on languages that are constant, as they allow a richer
range of interesting behaviour, but even strictly negative equality languages
yield non-trivial problems under singleton expansion.

Let us formalize the following simple consequence.

######  Corollary 59.

If $\Gamma$ is Horn, then $\textsc{CSP}(\Gamma_{c}^{+})$ and
$\textsc{CSP}(\Gamma^{+})$ are in P for every $c$.

###### Proof.

Apply Lemma 58 to $\Gamma^{\prime}=\Gamma\cup\\{=,\neq\\}$. The cost-
preserving reduction in particular preserves satisfiability. ∎

This finishes Lemma 55.

###  7.2 Strictly negative languages

Assume that $\Gamma$ is strictly negative. We note that in this case, adding a
single unary singleton relation makes the optimization problem hard.

######  Lemma 60.

$\textsc{MinCSP}(\neq,x=1)$ is NP-hard.

###### Proof.

There is a cost-preserving reduction from Vertex Cover. Let $G$ be a graph.
Create an instance $I$ of ${\textsc{MinCSP}(\neq,x=1)}$ as follows. The
variable set is $V(G)$. For every edge $uv\in E(G)$, create a crisp constraint
$(u\neq v)$. For every vertex $v\in V(G)$, create a soft constraint $(v=1)$.
On the one hand, let $S$ be a vertex cover for $G$. Then we may assign
variables of $S$ distinct values from $2,3,\ldots$, thereby breaking the soft
constraint $(v=1)$ for every $v\in S$, but satisfying every crisp disequality
constraint. Conversely, let $\alpha$ be an assignment to $I$ of finite cost.
Let $S$ be the set of variables $v\in V(I)$ such that $\alpha(v)\neq 1$. Then
$S$ is a vertex cover of $G$. ∎

On the other hand, if $\Gamma$ is strictly negative then its singleton
expansion has both an FPT algorithm and constant-factor approximation.

######  Lemma 61.

Let $\Gamma$ be a strictly negative language. Then
$\textsc{MinCSP}(\Gamma^{+})$ is FPT and has a constant-factor approximation.

###### Proof.

Let $I$ be an instance of $\textsc{MinCSP}(\Gamma^{+})$ with parameter $k$. We
branch over obvious obstructions. First, assume there is a variable $v\in
V(I)$ that is subject to contradictory assignment constraints $(v=i)$ and
$(v=j)$, $i\neq j$. Then we recursively branch into the two cases of either
setting $\alpha(v)=i$, in which case $(v=j)$ is violated (possibly along with
further assignment constraints on $v$), or concluding that $(v=i)$ is violated
and deleting those constraints. In both branches, the parameter $k$ decreases.
Next, form a tentative assignment $\alpha$ by setting $\alpha(v)=i$ for every
variable $v$ subject to an assignment constraint $(v=i)$, and setting all
other variables to mutually distinct values, distinct from all values
occurring in assignments in $I$. If $\alpha$ satisfies $I$, then we are done.
Otherwise, let $R(x_{1},\ldots,x_{r})$ be a constraint violated by $\alpha$.
Since $R$ is strictly negative, it has a definition as a conjunction of
strictly negative clauses. Let $C$ be such a clause that is violated by
$\alpha$. Then $C$ is a disjunction over a finite number of negative literals
$(x_{i}\neq x_{j})$, and for every such literal $(x_{i}\neq x_{j})$ there are
assignment constraints $(x_{i}=a)$ and $(x_{j}=a)$ in $I$ for some shared
value $a$. Then we can branch on either $R$ being violated or an assignment
constraint $(x_{i}=a_{i})$, $i\in[r]$ being violated. This yields $r+1=O(1)$
branches, and since $k$ decreases in each branch the result is an FPT
branching algorithm.

For the approximation, similar arguments apply. Let $v$ be a variable subject
to multiple contradictory assignment constraints. Let $i\in\mathbb{N}$ be the
constant for which the number of copies of a constraint $(v=i)$ is maximized.
Let $m_{1}$ be the number of assignment constraints $(v=j)$ for $j\neq i$, and
let $m_{2}$ be the number of constraints $(v=i)$. Delete all constraints
$(v=j)$ for $j\neq i$, and delete $\min(m_{1},m_{2})$ constraints $(v=i)$. Let
$X_{1}$ be set of assignment constraints deleted in total in this phase. Then
any assignment to the instance will violate at least half of the constraints
in $X_{1}$, and in the remaining instance every variable $v$ occurs in
assignment constraints $(v=i)$ for at most one value $i$. Let $\alpha$ be as
above, selecting an assignment that satisfies all assignment constraints and
assigns unique distinct values to all variables not occurring in assignment
constraints. Then, as above, if there is a constraint $R(X)$ not satisfied by
$\alpha$ then there is an explicit contradiction between $R(X)$ and at most
$r(R)=O(1)$ assignment constraints. Since at least one of these constraints
must be violated in any assignment, we get an $O(1)$-approximation by simply
deleting both $R(X)$ and one copy of every assignment constraint with scope
intersecting $X$. Repeating this until no constradictions remain gives an
$r(\Gamma)$-approximation, where $r(\Gamma)$ is the largest arity of a
relation in $\Gamma$. ∎

We summarise the properties of singleton expansions of strictly negative
languages as follows.

######  Lemma 62 (Lemma 56, repeated).

Let $\Gamma^{\prime}$ be a singleton expansion of a finite strictly negative
equality language $\Gamma$. Then $\textsc{CSP}(\Gamma^{\prime})$ is in P and
$\textsc{MinCSP}(\Gamma^{\prime})$ is NP-hard but FPT, and has a constant-
factor approximation.

###### Proof.

$\textsc{CSP}(\Gamma^{\prime})$ is in P by Cor. 59 (or indeed by Lemma 61).
For NP-hardness, we invoke Lemma 60. In particular since no proper relation is
both strictly negative and constant and $\Gamma$ contains at least one
relation by assumption, Lemma 16 implies that $\Gamma$ implements $\neq$. Then
$\textsc{MinCSP}(\Gamma_{1}^{+})$ is already NP-hard by Lemma 60, and adding
further unary singleton relations to the language clearly does not change this
fact. Finally, the FPT algorithm and constant-factor approximation of Lemma 61
also applies to $\textsc{MinCSP}(\Gamma^{\prime})$. ∎

###  7.3 Constant languages

We now assume that $\Gamma$ is constant but not strictly negative. For
studying these cases, we need to employ the algebraic machinery for studying
CSPs.

Let $R\subseteq D^{r}$ be a relation, and $f\colon D^{c}\to D$ an operation on
a domain $D$. We say that $f$ _preserves_ $R$ if, for any
$t_{1},\ldots,t_{c}\in R$ we have $f(t_{1},\ldots,t_{c})\in R$, where $f$ is
applied component-wise. Let $\Gamma$ be a constraint language over $D$. A
_polymorphism_ of $\Gamma$ is an operation over $D$ that preserves every
relation $R\in\Gamma$. A polymorphism $f\colon D^{c}\to D$ is _essentially
unary_ if there exists an index $i\in[c]$ and an operation $g\colon D\to D$
such that $f(x)=g(x_{i})$ for every $x\in D^{c}$. A polymorphism is
_essential_ if it is not essentially unary. Polymorphisms are a standard tool
in studying finite constraint languages, since they characterize the
expressive power of the language up to pp-definability. Bodirsky [3] shows
that under mild assumptions they can be used for infinite languages and
languages over infinite domains as well.

######  Theorem 63 ([3, Theorem 5.2.3]).

Let $\Gamma$ be an $\omega$-categorical structure. A relation $R$ has a pp-
definition in $\Gamma$ if and only if $R$ is preserved by all polymorphisms of
$\Gamma$.

In particular, every equality constraint language is $\omega$-categorical.
Furthermore, for any equality constraint language $\Gamma$ and any
$c\in\mathbb{N}$, the language $\Gamma_{c}^{+}$ is $\omega$-categorical (see
Section 3.1 of Bodirsky [3]). We will not need to consider any subtleties
around the language $\Gamma^{+}$ which has an infinite number of additional
relations, since all hardness claims over languages $\Gamma^{+}$ will follow
from finite subsets $\Gamma_{c}^{+}$ of $\Gamma^{+}$.

We give two simple statements for reference.

######  Lemma 64.

Let $\Gamma$ be an equality constraint language and $c\in\mathbb{N}$ a
constant, $c\geq 2$. If $\Gamma_{c}^{+}$ has no essential polymorphisms then
$\textsc{CSP}(\Gamma_{c}^{+})$ is NP-hard.

###### Proof.

Define $Q(a,b,c)$ over $\mathbb{N}$ as the relation $(a=b\lor b=c)$. As noted
by Bodirsky [3, Lemma 5.3.2], $Q$ is preserved by all essentially unary
operations but has no essential polymorphisms. As noted above,
$\Gamma_{c}^{+}$ is $\omega$-categorical, and therefore pp-defines $Q$.
However, $\textsc{CSP}(Q,x=1,x=2)$ is NP-hard: Note that $\exists
y_{1},y_{2}:(y_{1}=1)\land(y_{y}=2)\land Q(y_{1},x,y_{2})$ pp-defines the
unary relation $x\in\\{1,2\\}$. Thus it is enough that $\textsc{CSP}(Q)$ is
NP-hard as a Boolean language, which is standard (e.g., see Exercise 3.24 in
[20]). ∎

We also give a direct proof of the following implementation result. Recall
that $\textnormal{\sf ODD}_{3}\subset\mathbb{N}^{3}$ accepts any tuple that
takes either one or three distinct values.

######  Lemma 65.

Let $\Gamma$ be a constant equality language. Let
$f\colon\mathbb{N}\to\mathbb{N}$ be the retraction defined by $f(1)=1$ and
$f(x)=2$ otherwise. If $\Gamma$ is not preserved by $f$, then $\Gamma_{2}^{+}$
implements $\textnormal{\sf ODD}_{3}$.

###### Proof.

Let $R\in\Gamma$ be a relation not preserved by $f$, of arity $r$. For a tuple
$\mathbf{t}\in\mathbb{N}^{r}$, write
$f(\mathbf{t})=(f(t_{1}),\ldots,f(t_{r}))$ for the result of applying $f$ to
$\mathbf{t}$. Since $\Gamma$ is constant, $\mathbf{a}:=(1,\ldots,1)\in R$, and
since $R$ is not preserved by $f$ there is a tuple $\mathbf{c}\in R$ such that
$f(\mathbf{c})\notin R$. Note that we have a refinement order, where
$\mathbf{c}$ strictly refines $f(\mathbf{c})$ which strictly refines
$\mathbf{a}$. Let $\mathbf{c}$ be a least refined tuple in $R$ such that
$f(\mathbf{c})\notin R$, and let $r^{\prime}$ be the number of distinct values
used in $\mathbf{c}$. Without loss of generality, assume that $\mathbf{c}$
uses values $1$ through $r^{\prime}$. Note that $r^{\prime}\geq 3$. Define a
relation $R^{\prime}$ as
$R^{\prime}(x_{1},\ldots,x_{r^{\prime}})=R(x_{c_{1}},\ldots,x_{c_{r}})$. Then
$R^{\prime}$ accepts $(1,\ldots,1)$ and $(1,\ldots,r^{\prime})$, but no tuple
between these two in the refinement order. Thus
$R^{\prime\prime}(x,y,z)=\exists_{x_{4},\ldots,x_{r^{\prime}}}R^{\prime}(x,y,z,x_{4},\ldots,x_{r^{\prime}})$
is an implementation of $\textnormal{\sf ODD}_{3}$. ∎

We show that $\textsc{MinCSP}(\textnormal{\sf ODD}_{3},\Gamma_{2})$ is Hitting
Set-hard.

######  Lemma 66.

There is a cost-preserving reduction from Hitting Set to
$\textsc{MinCSP}(\textnormal{\sf ODD}_{3},\Gamma_{2})$.

###### Proof.

We give a variant of the hardness proof for $\textsc{MinCSP}(\textnormal{\sf
ODD}_{3},=,\neq)$ (Lemma 22).

######  Claim 66.1.

The language $\\{\textnormal{\sf ODD}_{3},\Gamma_{2}\\}$ pp-defines, for every
arity $\ell$, the relation $R(x_{1},\ldots,x_{\ell})$ that accepts every tuple
except $(1,\ldots,1)$ and $(2,\ldots,2)$.

Proof of claim: Create a pp-definition with local variables $z_{1}$, $z_{2}$
and $Y=\\{y_{2},\ldots,y_{\ell}\\}$ using the constraints

$(z_{1}=1)\land(z_{2}=2)\land\textnormal{\sf
ODD}_{3}(x_{1},x_{2},y_{2})\land\bigwedge_{i=2}^{\ell-1}\textnormal{\sf
ODD}_{3}(y_{i},x_{i+1},y_{i+1})\land\textnormal{\sf
ODD}_{3}(z_{1},z_{2},y_{\ell}).$

We claim that this pp-defines the relation $R$. First, assume that
$x_{1}=x_{2}=\ldots=c$ for some value $c$. Then $y_{\ell}=c$ by induction. If
$c\in\\{1,2\\}$, then the formula is unsatisfiable, otherwise the assignment
where $y=c$ for every $y\in Y$ satisfies the formula. Next, assume that
$x_{i}\neq x_{i+1}$. Then we may set $y_{i+1}$ to any free value, and by
induction we can set all variables $y_{j}$ for $j>i$ to distinct values not
equal to 1 or 2 and not used by any variable $x_{i}$. Then also the constraint
$\textnormal{\sf ODD}_{3}(z_{1},z_{2},y_{\ell})$ is satisfied. $\diamond$

Now let $I=(n,\mathcal{F},k)$ be an instance of Hitting Set (using the same
encoding as in Lemma 22). We create an instance $I^{\prime}$ of
$\textsc{MinCSP}(\textnormal{\sf ODD}_{3},\Gamma_{2})$ on variable set
$V=\\{v_{1},\ldots,v_{n}\\}$ as follows. First, create a soft constraint
$(v_{i}=1)$ for every $i\in[n]$. Next, for every set $F\in\mathcal{F}$ we
construct the relation of Claim 66.1 over the variable set $\\{v_{i}\mid i\in
F\\}$. We let every such construction consist of crisp constraints only. We
claim that this defines a cost-preserving reduction. On the one hand, let
$S\subseteq[n]$ be a hitting set for $\mathcal{F}$. Then we assign
$\alpha(v_{i})=3$ for $i\in S$ and $\alpha(v_{i})=1$ otherwise. This satisfies
every constraint of $I^{\prime}$ except the soft constraints $(v_{i}=1)$ for
$i\in S$, i.e., the cost of $\alpha$ is precisely $|S|$. On the other hand,
let $\alpha$ be an assignment to $I^{\prime}$ of some finite cost $c$, and let
$S=\\{i\in[n]\mid\alpha(v_{i})\neq 1\\}$ be the indices corresponding to
violated soft constraints in $I^{\prime}$. Then $S$ is a hitting set of
$\mathcal{F}$. ∎

With the preliminaries above in place, we can provide the main algebraic
characterization we use from previous work.

The following is a direct rephrasing of a result of Bodirsky et al. [5]. We
use the phrase _$f$ takes (at most) $k$ values_ to mean that the image of $f$
has cardinality (at most) $k$. For the definition of quasilinear operation,
see [5]; we will only need that quasilinear operations take at most two
values.

######  Theorem 67 (Theorem 8 of [5]).

Let $\Gamma$ be an equality language with at least one unary polymorphism that
is not constant or injective. If $\Gamma$ has any essential polymorphism, then
the essential polymorphisms of $\Gamma$ are described by one of the following
cases.

  1. 1.

All quasilinear operations

  2. 2.

For some $k\geq 2$, all operations which take at most $k$ different values

The remaining case looks as follows.

######  Lemma 68.

Let $\Gamma$ be a constant equality language that does not have any unary
polymorphism that is not injective or a constant. Then $\Gamma_{2}^{+}$
implements $\textnormal{\sf ODD}_{3}$. Furthermore, if $\Gamma$ has an
essential polymorphism then $\Gamma$ is Horn.

###### Proof.

The first statement follows from Lemma 65. The second statement is Theorem 15
of Bodirsky et al. [5]. ∎

####  7.3.1 At most two singletons

We first treat the case of $\Gamma_{c}^{+}$ for $c\leq 2$, since it behaves
somewhat differently from the rest. We begin with a trivial observation.

######  Proposition 69.

If $\Gamma$ is a constant equality constraint language, then
$\textsc{MinCSP}(\Gamma_{1}^{+})$ is in P.

Thus we consider the language $\Gamma_{2}^{+}$. Our main strategy will be a
reduction to a Boolean MinCSP problem, all of which have been fully
characterized [33, 13].

######  Lemma 70.

Let $\Gamma$ be a finite, constant equality language. One of the following
applies.

  * •

$\Gamma_{2}^{+}$ has a retraction to domain $\\{1,2\\}$ and
$\textsc{MinCSP}(\Gamma_{2}^{+})$ is equivalent under cost-preserving
reductions to $\textsc{MinCSP}(\Delta)$ for some Boolean language $\Delta$

  * •

$\Gamma$ is Horn and $\textsc{CSP}(\Gamma_{2}^{+})$ is in P, but
$\textsc{MinCSP}(\Gamma_{2}^{+})$ is Hitting Set-hard

  * •

$\textsc{CSP}(\Gamma_{2}^{+})$ is NP-hard

###### Proof.

First assume that $\Gamma$ is preserved by the retraction $f$ defined in Lemma
65. Define the language

$\Gamma^{\prime}=\\{R\cap\\{1,2\\}^{r(R)}\mid R\in\Gamma\\}$

as the slice of $\Gamma$ that only uses two values, and interpret
$\Gamma^{\prime}$ as a language over domain $\\{1,2\\}$. Let $\Delta$ be the
corresponding Boolean language, under the domain renaming $1\mapsto 0$ and
$2\mapsto 1$, with the singleton relations $(x=0)$ and $(x=1)$ added to
$\Delta$. We claim that $\textsc{MinCSP}(\Gamma_{2}^{+})$ and
$\textsc{MinCSP}(\Delta)$ are equivalent problems. Indeed, let $I$ be an
instance of $\textsc{MinCSP}(\Gamma_{2}^{)}$ and let $I^{\prime}$ be the
instance of $\textsc{MinCSP}(\Delta)$ resulting from replacing every
constraint in $I$ to the corresponding constraint over $\Delta$. Let $\varphi$
be an assignment to $V(I)$. By applying the retraction $f$ to $\varphi$
followed by the domain renaming mapping, we get an assignment
$\varphi^{\prime}\colon V(I)\to\\{0,1\\}$ which violates at most as many
constraints in $I^{\prime}$ as $\varphi$ violates in $I$. Correspondingly, any
assignment $\varphi^{\prime}\colon V(I^{\prime})\to\\{0,1\\}$ can be used
directly as an assignment to $V(I)$, and violates precisely the same set of
constraints in $I$ as $\varphi^{\prime}$ violates in $I^{\prime}$. Clearly,
the same reduction also works when interpreted as a reduction from
$\textsc{MinCSP}(\Delta)$ to $\textsc{MinCSP}(\Gamma_{2}^{+})$.

Otherwise, if $\Gamma$ is not preserved by $f$ then by Lemma 65,
$\Gamma_{2}^{+}$ implements $\textnormal{\sf ODD}_{3}$ and
$\textsc{MinCSP}(\Gamma_{2}^{+})$ is at least Hitting Set-hard by Lemma 66,
and the question is whether $\textsc{CSP}(\Gamma_{2}^{+})$ is in P. If
$\Gamma$ has no essential polymorphism, then $\textsc{CSP}(\Gamma_{2}^{+})$ is
NP-hard by Lemma 64. Hence assume that $\Gamma$ has some essential
polymorphism. If $\Gamma$ has a unary polymorphism that is not constant or an
injection, then by Theorem 67, $\Gamma$ is preserved by every quasilinear
operation. However, the retraction $f$ of Lemma 65 is quasilinear (see
Bodirsky et al. [5]), so this case is impossible. In the remaining case,
$\Gamma$ is Horn by Lemma 68 and $\textsc{CSP}(\Gamma_{2}^{+})$ is in P by
Cor. 59. ∎

Finally, the possibilities for the last case here are quite limited.

######  Lemma 71.

Let $\Gamma$ be a constant equality language such that $\Gamma_{2}^{+}$ has a
retraction to domain $\\{1,2\\}$ and let $\Delta$ be the corresponding Boolean
language. The following hold.

  * •

If $\Delta$ is positive conjunctive and connected then
$\textsc{MinCSP}(\Gamma_{2}^{+})$ is in P

  * •

If $\Delta$ is positive conjunctive but not connected, then
$\textsc{CSP}(\Gamma_{2}^{+})$ is in P and $\textsc{MinCSP}(\Gamma_{2}^{+})$
is W[1]-hard but has a constant-factor approximation

  * •

If $\Delta$ is not positive conjunctive but affine, then
$\textsc{CSP}(\Gamma_{2}^{)}$ is in P but $\textsc{MinCSP}(\Gamma_{2}^{+})$ is
Nearest Codeword-hard

  * •

Otherwise $\textsc{CSP}(\Gamma_{2}^{+})$ is NP-hard.

###### Proof.

Let $\Gamma^{\prime}$ be the intersection of $\Gamma$ with domain $\\{0,1\\}$,
interpreted as a Boolean language (as in Lemma 70). The possible cases for
such languages follow from Bonnet et al. [13] and the structure of Post’s
lattice of co-clones. Specifically, $\Gamma^{\prime}$ is 0-valid, 1-valid and
preserved by negation. If $\Gamma^{\prime}$ has no further polymorphism, then
$\textsc{CSP}(\Gamma_{2}^{+})$ is NP-hard; if $\Gamma^{\prime}$ is preserved
by the 3-ary XOR operation, then $\textsc{CSP}(\Gamma_{2}^{+})$ is in P, but
if $\Gamma^{\prime}$ has no further polymorphism then
$\textsc{MinCSP}(\Gamma_{2}^{+})$ is as hard to FPT-approximate as Nearest
Codeword; and in every remaining case, $\Gamma^{\prime}$ is positive
conjunctive [13]. Finally, if a Boolean language $\Gamma^{\prime}$ is positive
conjunctive, then either every relation in $\Gamma^{\prime}$ is connected, in
which case the relation is submodular and $\textsc{MinCSP}(\Gamma_{2}^{+})$ is
in P, or $\Gamma^{\prime}$ implements $R_{=,=}$ and
$\textsc{MinCSP}(\Gamma_{2}^{+})$ is W[1]-hard. However, as in Lemma 61 we can
split every relation $R\in\Gamma^{\prime}$ into separate equality constraints,
and reduce to st-Min Cut, up to a constant-factor approximation loss. ∎

For completion, let us provide example languages for each of the cases of
Lemma 71. If $\Gamma=\\{Q\\}$ where $Q(a,b,c)\equiv(a=b\lor b=c)$ is from
Lemma 64, then $\Gamma$ is closed under the retraction to domain $\\{1,2\\}$
but $\textsc{CSP}(\Gamma_{2}^{+})$ is NP-hard. Next, consider the relation
$R(a,b,c,d)$ which accepts any assignment where every block has even
cardinality (i.e., $R$ accepts tuples $(1,1,1,1)$, $(1,1,2,2)$, $(1,2,1,2)$
and $(1,2,2,1)$). Then $\textsc{MinCSP}(\Gamma_{2}^{+})$ corresponds to
$\textsc{MinCSP}(\Delta)$ for the Boolean language
$\Delta=\\{x=0,x=1,a+b+c+d=0\pmod{2}\\}$ which is Nearest Codeword-hard [13].
The final two cases are represented by the languages $\Gamma=\\{R_{=,=}\\}$
and $\Gamma=\\{=\\}$. As a final example, consider $\Gamma=\\{R\\}$ where
$R(a,b,c,d)$ is the 4-ary relation what accepts any tuple $(a,b,c,d)$ where
$a=b$ and $|\\{a,b,c,d\\}|\neq 3$. Then $\Gamma$ is not itself positive
conjunctive, but $\Gamma$ is constant and closed under the retraction
$f\colon\mathbb{N}\to\\{1,2\\}$ and the Boolean slice $\Gamma^{\prime}$ of
$\Gamma$ simply contains the relation $(a=b)$ with two additional irrelevant
arguments.

####  7.3.2 At least three singletons

The cases where $c\geq 3$ (and the case of $\Gamma^{+}$) are more regular.

######  Lemma 72.

Let $c\geq 3$ and let $\Gamma$ be a constant equality language. One of the
following applies.

  * •

$\textsc{MinCSP}(\Gamma_{c}^{+})$ is equivalent to
$\textsc{MinCSP}(\Delta_{c}^{+})$ where $\Delta$ is the $c$-slice of $\Gamma$,
and $\Delta$ is positive conjunctive

  * •

$\Gamma$ is Horn but the last case does not apply;
$\textsc{CSP}(\Gamma_{c}^{+})$ is in P, but $\textsc{MinCSP}(\Gamma_{c}^{+})$
is Hitting Set-hard

  * •

Neither case applies, and $\textsc{CSP}(\Gamma_{c}^{+})$ is NP-hard.

Similarly, one of the following applies.

  * •

$\Gamma$ is positive conjunctive

  * •

$\Gamma$ is Horn but not positive conjunctive; $\textsc{CSP}(\Gamma^{+})$ is
in P, but $\textsc{MinCSP}(\Gamma^{+})$ is Hitting Set-hard

  * •

Neither case applies, and $\textsc{CSP}(\Gamma^{+})$ is NP-hard.

###### Proof.

Consider the polymorphisms of $\Gamma_{c}^{+}$. They are precisely the
intersection of the polymorphisms of $\Gamma$ and of $\Gamma_{c}$, i.e., every
polymorphism $f$ of $\Gamma$ such that $f(i,\ldots,i)=i$ for every $i\in[c]$.
Then any such $f$ is an operation that takes at least $c$ values. First,
assume that $\Gamma$ has at least one unary polymorphism that is not constant
or injective, so that Theorem 67 applies. In this case, either
$\Gamma_{c}^{+}$ has no essential polymorphisms or $\Gamma$ is preserved by
every operation that takes $c$ values. In the former case,
$\textsc{CSP}(\Gamma_{c}^{+})$ is NP-hard by Lemma 64. In the latter case, it
first of all follows that $\Gamma_{c}^{+}$ is preserved by a retraction to
domain $[c]$. Furthermore, consider the resulting slice language

$\Gamma^{\prime}=\\{R\cap[c]^{r(R)}\mid R\in\Gamma\\}$

(where $r(R)$ denotes the arity of $R$) as a language over domain $[c]$. Then
every relation $R\in\Gamma^{\prime}$ is preserved by every operation over
$[c]$. The only such relations are $=$ and relations pp-defined over $=$.
Thus, the slice language $\Gamma^{\prime}$ is positive conjunctive. Otherwise,
by assumption Lemma 68 applies, so that $\Gamma_{c}^{+}$ implements
$\textnormal{\sf ODD}_{3}$ and $\textsc{MinCSP}(\Gamma_{c}^{+})$ is Hitting
Set-hard by Lemma 66. Furthermore, either $\Gamma$ has no essential
polymorphisms or $\Gamma$ is Horn. In the former case
$\textsc{CSP}(\Gamma_{c}^{+})$ is NP-hard by Lemma 64; in the latter case
$\textsc{CSP}(\Gamma_{c}^{+})$ is in P by Cor. 59.

The case of $\Gamma^{+}$ is similar. Clearly the hardness cases for
$\Gamma_{c}^{+}$, $c\geq 3$ carry over to $\Gamma^{+}$. Hence if $\Gamma$ is
not Horn then $\textsc{CSP}(\Gamma^{+})$ is NP-hard. Furthermore, let
$R\in\Gamma$ be any relation not preserved by all operations. Then every tuple
of $R$ uses at most $r(R)$ distinct values, and $R\cap[r(R)]^{r(R)}$ is not
preserved by all operations. Hence $\Gamma_{r(R)}^{+}$ is already Hitting Set-
hard by the above. The only remaining case is that $\Gamma$ itself is pp-
definable over $\\{=\\}$, i.e., positive conjunctive. ∎

We also observe the tractable cases for positive conjunctive languages.

######  Lemma 73.

Let $\Gamma$ be a finite, positive conjunctive equality language, possibly
trivial, and let $\Gamma^{\prime}$ be a singleton expansion of $\Gamma$ with
at least three singleton relations. Then $\textsc{CSP}(\Gamma^{\prime})$ is in
P and $\textsc{MinCSP}(\Gamma^{\prime})$ has a constant-factor approximation.
Furthermore the following hold.

  1. 1.

If $\Gamma$ is trivial, then $\textsc{MinCSP}(\Gamma^{\prime})$ is in P

  2. 2.

If $\Gamma$ is connected but not trivial, then
$\textsc{MinCSP}(\Gamma^{\prime})$ is NP-hard but FPT

  3. 3.

If $\Gamma$ is not connected, then $\textsc{MinCSP}(\Gamma^{\prime})$ is
W[1]-hard.

###### Proof.

Since every conjunctive language is Horn, $\textsc{CSP}(\Gamma^{\prime})$ is
in P by Cor. 59. If $\Gamma$ is trivial, then instances of
$\textsc{MinCSP}(\Gamma^{\prime})$ consist of trivial constraints (always
satisfied, or never satisfied) which can be discarded, and unary constraints
$(x=i)$. An optimal assignment to such an instance can be computed easily with
a greedy algorithm. Otherwise, let $R\in\Gamma$ be non-trivial. Since $R$ is
positive conjunctive, $R$ is Horn and not strictly negative and $R$ implements
$=$ by Lemma 16. Since $\textsc{MinCSP}(=,\Gamma_{3})$ captures Edge Multiway
Cut with three terminals, which is NP-hard, it follows that
$\textsc{MinCSP}(\Gamma^{\prime})$ is NP-hard. If $\Gamma$ is positive
conjunctive and connected, then $\Gamma\cup\\{=,\neq\\}$ is split, hence
$\textsc{MinCSP}(\Gamma^{\prime},=,\neq)$ is FPT by Theorem 20 and Lemma 58.
Finally, let $R\in\Gamma$ be a relation that is positive conjunctive but not
connected. Then $R$ is defined by a conjunction of positive literals
$(x_{i}=y_{i})$, and the graph induced over its arguments has at least two
non-trivial connected components since otherwise $R$ is split. Then $R$
implements the relation
$R^{\prime}(x_{1},y_{1},x_{2},y_{2})\equiv(x_{1}=y_{1})\land(x_{2}=y_{2})$
using existential quantification over irrelevant variables and
$\textsc{MinCSP}(\Gamma^{\prime})$ is W[1]-hard by a simple reduction from
Split Paired Cut (see Section 4.2).

For approximation, since $\Gamma$ is finite there is a finite bound
$d\in\mathbb{N}$ such that every relation $R\in\Gamma$ is a conjunction of at
most $d$ terms. Then we can split every constraint

$R(x_{1},\ldots,x_{r})=(x_{i_{1}}=x_{j_{1}})\land\ldots\land(x_{i_{d}}=x_{j_{d}})$

in an instance of $\textsc{MinCSP}(\Gamma^{\prime})$ into the $d$ separate
constraints $(x_{i_{p}}=x_{j_{p}})$, $p\in[d]$. This increases the cost of the
instance at most by a factor $d$. Now we have an instance with just equality
and assignments, which reduces to Edge Multiway Cut which has a constant-
factor approximation [18]. ∎

##  8 Discussion

We classify the parameterized complexity of $\textsc{MinCSP}(\Gamma)$ for all
finite equality constraint languages $\Gamma$ and their singleton expansions.
In particular, we show that for an equality language $\Gamma$,
$\textsc{MinCSP}(\Gamma)$ is in FPT if $\Gamma$ only contains split relations
and $\textnormal{\sf NEQ}_{3}$, it is W[1]-hard and fpt-approximable within a
constant factor if $\Gamma$ is negative but contains a relation that is
neither split nor $\textnormal{\sf NEQ}_{3}$, and is Hitting Set-hard
otherwise. We also show that the complications introduced by singleton
expansion can be handled by well-known fpt algorithms.

Note that singleton expansion is distinct from adding constants to the
underlying structure $(\mathbb{N},=)$, as the latter creates a much more
powerful language. For example, just adding a single constant to the structure
allows first-order reducts to implement arbitrary Boolean relations (using,
e.g., $v=0$ and $v\neq 0$ as the two domain values). Hence, studying
$\textsc{MinCSP}(\Gamma)$ for reducts of the structure $(\mathbb{N},=)$ with
any finite number of constants added generalizes the task of producing a
parameterized dichotomy for $\textsc{MinCSP}(\Gamma)$ over all finite-domain
language $\Gamma$, which is a highly challenging task. There is a CSP
dichotomy for this setting [11], but it explicitly reduces back to the CSP
dichotomy for finite-domain languages, and no such result is known for
parameterized complexity. The complexity of $\textsc{MinCSP}(\Gamma)$ for the
reducts of $(\mathbb{N},=)$ extended with finitely many constants is therefore
an interesting but challenging question as it generalizes
$\textsc{MinCSP}(\Gamma)$ for all finite-domain constraint languages $\Gamma$.
We note that this question is open even for the case of $(\mathbb{N},=)$ plus
a single constant, as mentioned above.

The natural next step is to study _temporal constraint languages_ where the
relations are first-order definable over $(\mathbb{Q};<)$. Note that relations
$\leq$ and $\neq$ belong to this class, and $\textsc{MinCSP}(\leq,\neq)$ is
equivalent to Symmetric Directed Multicut, an important open problem on
digraphs [27, 35]. One way forward would be to study _constant-factor fpt
approximation_ instead since there the classes of tractable languages are
preserved by (equality-free) pp-definitions, and thus one can employ powerful
tools from the algebraic approach to CSP.

## References

  * [1] Libor Barto, Andrei A. Krokhin, and Ross Willard.  Polymorphisms, and how to use them.  In The Constraint Satisfaction Problem, volume 7 of Dagstuhl Follow-Ups, pages 1–44. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.
  * [2] Arnab Bhattacharyya, Édouard Bonnet, László Egri, Suprovat Ghoshal, Karthik C. S., Bingkai Lin, Pasin Manurangsi, and Dániel Marx.  Parameterized intractability of even set and shortest vector problem.  J. ACM, 68(3):16:1–16:40, 2021.
  * [3] Manuel Bodirsky.  Constraint satisfaction with infinite domains.  PhD thesis, Humboldt University of Berlin, Unter den Linden, Germany, 2004\.
  * [4] Manuel Bodirsky.  Complexity of Infinite-Domain Constraint Satisfaction.  Lecture Notes in Logic (LNL). Cambridge University Press, 2021.  doi:10.1017/9781107337534.
  * [5] Manuel Bodirsky, Hubie Chen, and Michael Pinsker.  The reducts of equality up to primitive positive interdefinability.  J. Symb. Log., 75(4):1249–1292, 2010.
  * [6] Manuel Bodirsky and Martin Grohe.  Non-dichotomies in constraint satisfaction complexity.  In ICALP (2), volume 5126 of Lecture Notes in Computer Science, pages 184–196. Springer, 2008.
  * [7] Manuel Bodirsky and Jan Kára.  The complexity of equality constraint languages.  Theory of Computing Systems, 43(2):136–158, 2008.
  * [8] Manuel Bodirsky and Jan Kára.  The complexity of temporal constraint satisfaction problems.  J. ACM, 57(2):9:1–9:41, 2010.
  * [9] Manuel Bodirsky and Marcello Mamino.  Constraint satisfaction problems over numeric domains.  In The Constraint Satisfaction Problem, volume 7 of Dagstuhl Follow-Ups, pages 79–111. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.
  * [10] Manuel Bodirsky, Barnaby Martin, and Antoine Mottet.  Discrete temporal constraint satisfaction problems.  J. ACM, 65(2):9:1–9:41, 2018.
  * [11] Manuel Bodirsky and Antoine Mottet.  A dichotomy for first-order reducts of unary structures.  Log. Methods Comput. Sci., 14(2), 2018.
  * [12] Manuel Bodirsky and Michael Pinsker.  Schaefer’s theorem for graphs.  J. ACM, 62(3):19:1–19:52, 2015.
  * [13] Édouard Bonnet, László Egri, and Dániel Marx.  Fixed-parameter approximability of Boolean MinCSPs.  In 24th Annual European Symposium on Algorithms (ESA 2016), pages 18:1–18:18, 2016.
  * [14] Édouard Bonnet, László Egri, Bingkai Lin, and Dániel Marx.  Fixed-parameter approximability of boolean MinCSPs, 2018.  URL: https://arxiv.org/abs/1601.04935v2, doi:10.48550/ARXIV.1601.04935.
  * [15] Nicolas Bousquet, Jean Daligault, and Stéphan Thomassé.  Multicut is FPT.  SIAM J. Comput., 47(1):166–207, 2018.  doi:10.1137/140961808.
  * [16] Karl Bringmann, Danny Hermelin, Matthias Mnich, and Erik Jan Van Leeuwen.  Parameterized complexity dichotomy for Steiner multicut.  Journal of Computer and System Sciences, 82(6):1020–1043, 2016\.
  * [17] Andrei A. Bulatov.  A dichotomy theorem for nonuniform CSPs.  In FOCS, pages 319–330. IEEE Computer Society, 2017.
  * [18] Gruia Călinescu, Howard J. Karloff, and Yuval Rabani.  An improved approximation algorithm for MULTIWAY CUT.  J. Comput. Syst. Sci., 60(3):564–574, 2000.
  * [19] Shuchi Chawla, Robert Krauthgamer, Ravi Kumar, Yuval Rabani, and D Sivakumar.  On the hardness of approximating multicut and sparsest-cut.  Computational Complexity, 15(2):94–114, 2006.
  * [20] Hubie Chen.  A rendezvous of logic, complexity, and algebra.  ACM SIGACT News, 37(4):85–114, 2006.
  * [21] Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva.  Maximum flow and minimum-cost flow in almost-linear time.  In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 - November 3, 2022, pages 612–623. IEEE, 2022.  doi:10.1109/FOCS54457.2022.00064.
  * [22] Rajesh Chitnis, Marek Cygan, Mohammataghi Hajiaghayi, and Dániel Marx.  Directed subset feedback vertex set is fixed-parameter tractable.  ACM Transactions on Algorithms (TALG), 11(4):1–28, 2015.
  * [23] Christophe Crespelle, Pål Grønås Drange, Fedor V. Fomin, and Petr A. Golovach.  A survey of parameterized algorithms and the complexity of edge modification, 2020.  arXiv:2001.06867.
  * [24] Marek Cygan, Fedor V Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh.  Parameterized algorithms.  Springer, 2015.
  * [25] Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, and Jakub Onufry Wojtaszczyk.  On multiway cut parameterized above lower bounds.  ACM Transactions on Computation Theory (TOCT), 5(1):1–11, 2013\.
  * [26] Konrad K Dabrowski, Peter Jonsson, Sebastian Ordyniak, George Osipov, and Magnus Wahlström.  Almost consistent systems of linear equations.  In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3179–3217. SIAM, 2023.
  * [27] Eduard Eiben, Clément Rambaud, and Magnus Wahlström.  On the parameterized complexity of symmetric directed multicut.  In IPEC, LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.
  * [28] Andreas Emil Feldmann, Karthik C. S., Euiwoong Lee, and Pasin Manurangsi.  A survey on approximation in parameterized complexity: Hardness and algorithms.  Algorithms, 13(6):146, 2020.
  * [29] Peter Jonsson.  Constants and finite unary relations in qualitative constraint reasoning.  Artif. Intell., 257:1–23, 2018.
  * [30] Karthik C. S. and Subhash Khot.  Almost polynomial factor inapproximability for parameterized k-clique.  In CCC, volume 234 of LIPIcs, pages 6:1–6:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.
  * [31] Subhash Khot.  On the power of unique 2-prover 1-round games.  In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pages 767–775, 2002.
  * [32] Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, and Magnus Wahlström.  Solving hard cut problems via flow-augmentation.  arXiv e-prints, pages arXiv–2007, 2020.
  * [33] Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, and Magnus Wahlström.  Flow-augmentation III: complexity dichotomy for boolean CSPs parameterized by the number of unsatisfied constraints.  In SODA, pages 3218–3228. SIAM, 2023.
  * [34] Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, and Magnus Wahlström.  Flow-augmentation III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints.  arXiv preprint arXiv:2207.07422, 2023.
  * [35] Eun Jung Kim, Marcin Pilipczuk, Roohani Sharma, and Magnus Wahlström.  On weighted graph separation problems and flow-augmentation.  arXiv preprint arXiv:2208.14841, 2022.
  * [36] Vladimir Kolmogorov, Andrei A. Krokhin, and Michal Rolínek.  The complexity of general-valued CSPs.  SIAM J. Comput., 46(3):1087–1110, 2017.
  * [37] Stefan Kratsch and Magnus Wahlström.  Representative sets and irrelevant vertices: New tools for kernelization.  Journal of the ACM (JACM), 67(3):1–50, 2020.
  * [38] Jason Li and Debmalya Panigrahi.  Deterministic min-cut in poly-logarithmic max-flows.  In Sandy Irani, editor, 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 85–92. IEEE, 2020.  doi:10.1109/FOCS46700.2020.00017.
  * [39] Bingkai Lin, Xuandi Ren, Yican Sun, and Xiuhan Wang.  Constant approximating parameterized $k$-setcover is W[2]-hard.  arXiv preprint arXiv:2202.04377, 2022.
  * [40] Bingkai Lin, Xuandi Ren, Yican Sun, and Xiuhan Wang.  Constant approximating parameterized $k$-SETCOVER is W[2]-hard.  In SODA, pages 3305–3316. SIAM, 2023.
  * [41] Daniel Lokshtanov, Pranabendu Misra, MS Ramanujan, Saket Saurabh, and Meirav Zehavi.  FPT-approximation for FPT problems.  In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 199–218. SIAM, 2021.
  * [42] Dániel Marx.  Parameterized graph separation problems.  Theor. Comput. Sci., 351(3):394–406, 2006.  doi:10.1016/j.tcs.2005.10.007.
  * [43] Daniel Marx and Igor Razgon.  Fixed-parameter tractability of multicut parameterized by the size of the cutset.  SIAM Journal on Computing, 43(2):355, 2014.
  * [44] Johan Thapper and Stanislav Živný.  The complexity of finite-valued CSPs.  J. ACM, 63(4):37:1–37:33, 2016.
  * [45] Magnus Wahlström.  Quasipolynomial multicut-mimicking networks and kernels for multiway cut problems.  ACM Trans. Algorithms, 18(2):15:1–15:19, 2022.
  * [46] Dmitriy Zhuk.  A proof of the CSP dichotomy conjecture.  J. ACM, 67(5):30:1–30:78, 2020.


# Practical Considerations in
Repairing Reed-Solomon Codes ††thanks:  T. X. Dinh, L. J. Mohan, and S. H. Dau
are with the School of Computing Technologies, RMIT University, Australia.
Emails: {S3880660<EMAIL_ADDRESS>T. X. Dinh is also with the
Department of Mathematics, Faculty of Natural Science and Technology, Tay
Nguyen University, Vietnam. L. Y. N. Nguyen was an intern at RMIT Univesity
when this work was done. Tran Thi Luong is with the Department of Information
Security, Academy of Cryptography Techniques, Hanoi, Vietnam. Email:
<EMAIL_ADDRESS>
Thi Xinh Dinh†, Luu Y Nhi Nguyen†, Lakshmi J. Mohan†, Serdar Boztas†, Tran Thi
Luong‡, and Son Hoang Dau†
†RMIT University, ‡Academy of Cryptographic Technique, Hanoi, Vietnam

###### Abstract

The issue of repairing Reed-Solomon codes currently employed in industry has
been sporadically discussed in the literature. In this work we carry out a
systematic study of these codes and investigate important aspects of repairing
them under the trace repair framework, including which evaluation points to
select and how to implement a trace repair scheme efficiently. In particular,
we employ different heuristic algorithms to search for low-bandwidth repair
schemes for codes of short lengths with typical redundancies and establish
three tables of current best repair schemes for $[n,k]$ Reed-Solomon codes
over $\text{GF}(256)$ with $4\leq n\leq 16$ and $r=n-k\in\\{2,3,4\\}$. The
tables cover most known codes currently used in the distributed storage
industry.

##  I Introduction

Reed-Solomon codes [1], invented more than 60 years ago, still constitute the
most widely used family of erasure codes in distributed storage systems to
date (see Table I). Due to their popularity in practice as well as their
fundamental role in the development of classical coding theory, a significant
amount of research has been conducted in recent years to improve their repair
bandwidth and I/O cost required in recovering a single or multiple erasures
[2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22,
23, 24, 25, 26]. In the context of distributed storage systems, the repair
bandwidth of an erasure code refers to the amount of data downloaded from the
helper nodes by a recovery node to reconstruct its lost content, while the I/O
cost is the total amount of data read from the local disks of the helper
nodes.

TABLE I: A table of Reed-Solomon codes employed in major distributed storage
systems - an updated version of [18, Table I].

Despite the growing literature, the treatment of short-length Reed-Solomon
codes used in (or relevant to) practical storage systems has been sporadic and
rather limited: RS(14,10) (used in Facebook’s f4) has received the most
attention [2, 3, 4, 10, 12, 23], while RS(5,3) and RS(6,4) were investigated
in [2], and RS(11,8) and RS(12,8) were discussed in [23]. Apart from [10] and
[23], in which they were studied as the main topic of interest, these codes
were mostly used as examples to demonstrate the inefficiency of the naive
repair and the improvements in repair bandwidths that a carefully designed
repair scheme can bring. We address this gap in the literature by providing a
systematic investigation of low-bandwidth repair schemes for short-length
Reed-Solomon codes that are relevant for the data storage industry and discuss
several practical aspects including the selection of the evaluation points and
implementation.

We first revisit four constructions of Reed-Solomon codes in existing
implementations, observing that all but one are the same as the classical
construction using polynomial evaluations (Section III). Next, we discuss
heuristic algorithms that can be used for construction of repair schemes for
such codes and as a result, establish three tables of current-best repair
schemes for codes of length $n\leq 16$ and redundancy $r\leq 4$ (Section IV).
We also study in this section the impact of the evaluation points on repair
bandwidths, demonstrating with an example that codes having the same $n$ and
$k$ but using different lists of evaluation points may end up having different
repair bandwidths. Finally, we propose an efficient way to implement (in C) a
trace repair scheme for Reed-Solomon code based on lookup tables and fast
bitwise operations [27] on top of the state-of-the-art Intel Intelligent
Storage Acceleration Library (ISA-L) (Section V).

##  II Definitions and Notations

Let $[n]\triangleq\\{1,2,\ldots,n\\}$ and
$[m,n]\triangleq\\{m,m+1,\ldots,n\\}$. Let $\mathbb{F}_{q}$ be the finite
field of $q$ elements and $\mathbb{F}_{q^{\ell}}$ be its extension field of
degree $\ell$, where $q$ is a prime power. In this work we only consider the
case $q^{\ell}=256$. The field ${\mathbb{F}}_{256}$ can also be viewed as a
vector space over its subfields, i.e.,
${\mathbb{F}}_{256}\cong{\mathbb{F}}_{16}^{2}\cong{\mathbb{F}}_{4}^{4}\cong\mathbb{F}_{2}^{8}$.
Each element ${\bm{b}}$ of ${\mathbb{F}}_{256}$ can be represented as one
byte, i.e., a vector of eight bits $(b_{1},b_{2},\ldots,b_{8})$, or an integer
in $[0,255]$. For instance, $6=2^{2}+2$ is represented by the vector
$00000110$ and corresponds to ${\bm{b}}={\bm{z}}^{2}+{\bm{z}}$, where
${\bm{z}}=2$ is a primitive element of ${\mathbb{F}}_{256}$. To accelerate the
computation over ${\mathbb{F}}_{256}$, additions between integers representing
finite field elements are performed bitwise while multiplications are based on
table lookups. Bitwise operators in C including XOR ‘^’, AND ‘&’, and bit-
shift ‘$\ll$’ are heavily used in code optimization.

We use $\mathsf{span}_{\mathbb{F}_{q}}(U)$ to denote the
$\mathbb{F}_{q}$-subspace of $\mathbb{F}_{q^{\ell}}$ spanned by a subset
$U\subseteq\mathbb{F}_{q^{\ell}}$. We use $\dim_{\mathbb{F}_{q}}(\cdot)$ and
$\mathsf{rank}_{\mathbb{F}_{q}}(\cdot)$ to denote the dimension of a subspace
and the rank of a set of vectors over $\mathbb{F}_{q}$. The (field) trace of
an element ${\bm{b}}\in\mathbb{F}_{q^{\ell}}$ over $\mathbb{F}_{q}$ is
$\mathsf{Tr}_{\mathbb{F}_{q^{\ell}}/\mathbb{F}_{q}}({\bm{b}})\triangleq\sum_{i=0}^{\ell-1}{\bm{b}}^{q^{i}}$.
Given an $\mathbb{F}_{q}$-subspace $W$ of $\mathbb{F}_{q^{\ell}}$, the
polynomial $L_{W}(x)=\prod_{w\in W}(x-w)$ is called the subspace polynomial
corresponding to $W$.

A _linear $[n,k]$ code_ ${\mathcal{C}}$ over $\mathbb{F}_{q^{\ell}}$ is an
$\mathbb{F}_{q^{\ell}}$-subspace of $\mathbb{F}_{q^{\ell}}^{n}$ of dimension
$k$. Each element
$\vec{\bm{c}}=({\bm{c}}_{1},{\bm{c}}_{2},\ldots,{\bm{c}}_{n})\in{\mathcal{C}}$
is referred to as a _codeword_ and each component ${\bm{c}}_{j}$ is called a
codeword symbol. The _dual_ $\mathcal{C}^{\perp}$ of a code ${\mathcal{C}}$ is
the orthogonal complement of ${\mathcal{C}}$ in $\mathbb{F}_{q^{\ell}}^{n}$
and has dimension $r=n-k$. The elements of $\mathcal{C}^{\perp}$ are called
dual codewords. We call $r$ the _redundancy_ of the code. A matrix
${\bm{G}}\in\mathbb{F}_{q^{\ell}}^{k\times n}$ of rank $k$ over
$\mathbb{F}_{q^{\ell}}$ whose rows are codewords of ${\mathcal{C}}$ is called
a generator matrix of the code. Given a generator matrix ${\bm{G}}$, a message
$\vec{\bm{u}}=({\bm{u}}_{1},\ldots,{\bm{u}}_{k})$ is transformed into a
codeword $\vec{\bm{c}}=\vec{\bm{u}}{\bm{G}}$. A parity check matrix of
${\mathcal{C}}$ is simply a generator matrix ${\bm{H}}$ of the dual code
$\mathcal{C}^{\perp}$.

##  III Existing Constructions of Reed-Solomon Codes

###  III-A Classical Construction by Reed and Solomon

The following construction of Reed-Solomon codes is the original one proposed
by Reed and Solomon in [1].

######  Definition 1.

Let $\mathbb{F}_{q^{\ell}}[x]$ denote the ring of polynomials over
$\mathbb{F}_{q^{\ell}}$. A Reed-Solomon code
$\text{RS}(A,k)\subseteq\mathbb{F}_{q^{\ell}}^{n}$ of dimension $k$ with
evaluation points
$A=\\{\bm{\alpha}_{j}\\}_{j=1}^{n}\subseteq\mathbb{F}_{q^{\ell}}$ is defined
as

$\text{RS}(A,k)=\Big{\\{}\big{(}f(\bm{\alpha}_{1}),\ldots,f(\bm{\alpha}_{n})\big{)}\colon
f\in\mathbb{F}_{q^{\ell}}[x],\ \deg(f)<k\Big{\\}}.\vspace{-5pt}$

We also use the notation RS$(n,k)$, ignoring the evaluation points. Clearly, a
generator matrix of this code is the Vandermonde matrix
$\text{Vand}(\bm{\alpha}_{1},\ldots,\bm{\alpha}_{n})\triangleq\left(\bm{\alpha}_{j}^{i-1}\right)_{1\leq
i\leq k,1\leq j\leq n}$.

A _generalized_ Reed-Solomon code, $\text{GRS}(A,k,\vec{\bm{\lambda}})$, where
$\vec{\bm{\lambda}}=(\bm{\lambda}_{1},\ldots,\bm{\lambda}_{n})\in\mathbb{F}_{q^{\ell}}^{n}$,
is defined similarly to a Reed-Solomon code, except that the codeword
corresponding to a polynomial $f$ is defined as
$\big{(}\bm{\lambda}_{1}f(\bm{\alpha}_{1}),\ldots,\bm{\lambda}_{n}f(\bm{\alpha}_{n})\big{)}$,
where $\bm{\lambda}_{j}\neq 0$ for all $j\in[n]$. It is well known that the
dual of a Reed-Solomon code $\text{RS}(A,k)$ is a generalized Reed-Solomon
code $\text{GRS}(A,n-k,\vec{\bm{\lambda}})$, for some multiplier vector
$\vec{\bm{\lambda}}$ ([28, Chp. 10]). We sometimes use the notation
GRS$(n,k)$, ignoring $A$ and $\vec{\bm{\lambda}}$.

We often use $f(x)$ to denote a polynomial of degree at most $k-1$, which
corresponds to a codeword of the Reed-Solomon code
${\mathcal{C}}=\text{RS}(A,k)$, and $g(x)$ to denote a polynomial of degree at
most $r-1=n-k-1$, which corresponds to a codeword of the dual code
$\mathcal{C}^{\perp}$. Since
$\sum_{j=1}^{n}g(\bm{\alpha}_{j})(\bm{\lambda}_{j}f(\bm{\alpha}_{j}))=0,$ we
also refer to the polynomial $g(x)$ as a check polynomial for ${\mathcal{C}}$.

Next, we discuss four main constructions of Reed-Solomon codes found in
practical systems, three of which are equivalent to the original construction
and one is invalid. All are over ${\mathbb{F}}_{256}$.

###  III-B Constructions in Intelligent Storage Acceleration Library

Both implementations of Reed-Solomon codes provided by ISA-L are systematics
[29]. The first one, also found in the Quantcast File System [30], uses the
generator matrix ${\bm{G}}=[{\bm{I}}_{k}\mid\bm{V}]$ in which $\bm{V}$ is a
$k\times(n-k)$ Vandermonde matrix: $\bm{V}=({\bm{x}}_{j}^{i-1})$, $i\in[1,k]$,
$j\in[1,n]$, where ${\bm{x}}_{j}={\bm{z}}^{j-1}$ and ${\bm{z}}=2$ is a
primitive element of ${\mathbb{F}}_{256}$. This is not a construction of a
Reed-Solomon code, not even an MDS code (i.e., achieving the Singleton bound
[28]). Indeed, it is known that ${\bm{G}}=[{\bm{I}}_{k}\mid\bm{V}]$ generates
an MDS code only if every square submatrix of $\bm{V}$ is invertible ([28, Ch.
11, Thm. 8]), which is not true for a Vandermonde matrix in general. Although
when $n=9$ and $k=6$, as in the Quantcast File System [31], the code is still
MDS, we ignore this construction as it is incorrect in general.

We focus on the second construction, which uses the generator matrix
${\bm{G}}=[{\bm{I}}_{k}\mid{\bm{C}}]$ in which ${\bm{C}}$ is a $k\times(n-k)$
Cauchy matrix:
${\bm{C}}=\left(c_{i,j}=\frac{1}{{\bm{x}}_{i}+{\bm{y}}_{j}}\right)$,
$i\in[1,k]$, $j\in[1,n-k]$, where ${\bm{x}}_{i}=i-1$ and ${\bm{y}}_{j}=k+j-1$.
Note that ${\bm{x}}_{i}$ and ${\bm{y}}_{j}$ are written using the integer
representations of elements of ${\mathbb{F}}_{256}$ and
${\bm{x}}_{i}+{\bm{y}}_{j}$ refers to the (bitwise) addition of two field
elements. According to [32, Thm. 1], this code is the same as
$\text{GRS}(A,k,\vec{\bm{\lambda}})$ with
$A=[\vec{\bm{x}}\mid\vec{\bm{y}}]=[0,n-1]$ and
$\vec{\bm{\lambda}}=(\bm{\lambda}_{1},\ldots,\bm{\lambda}_{n})$ defined as

$\bm{\lambda}_{j}=\begin{cases}1/\prod_{s=1,s\neq
j}^{k}({\bm{x}}_{s}+{\bm{x}}_{j}),&1\leq j\leq k,\\\
1/\prod_{s=1}^{k}({\bm{x}}_{s}+{\bm{y}}_{j-k}),&k+1\leq j\leq
n.\end{cases}\vspace{1pt}$

For example, for $n=9,k=6$, the Cauchy-based construction of RS(9,6) code, or
more precisely, a GRS(9,6), uses $\vec{\bm{x}}=(0,1,2,3,4,5)$ and
$\vec{\bm{y}}=(6,7,8)$ and has a generator matrix

${\bm{G}}=\begin{pmatrix}{\bm{I}}_{6}&\vline&\begin{matrix}122&186&173\\\
186&122&157\\\ 71&167&221\\\ 167&71&152\\\ 142&244&61\\\
244&142&170\end{matrix}\end{pmatrix}=\begin{pmatrix}{\bm{I}}_{6}&\vline&\begin{matrix}{\bm{z}}^{229}&{\bm{z}}^{57}&{\bm{z}}^{252}\\\
{\bm{z}}^{57}&{\bm{z}}^{229}&{\bm{z}}^{32}\\\
{\bm{z}}^{253}&{\bm{z}}^{205}&{\bm{z}}^{204}\\\
{\bm{z}}^{205}&{\bm{z}}^{253}&{\bm{z}}^{17}\\\
{\bm{z}}^{254}&{\bm{z}}^{230}&{\bm{z}}^{228}\\\
{\bm{z}}^{230}&{\bm{z}}^{254}&{\bm{z}}^{151}\end{matrix}\end{pmatrix},$

where ${\bm{z}}=2$ is a primitive element of ${\mathbb{F}}_{256}$ satisfying
${\bm{z}}^{8}+{\bm{z}}^{4}+{\bm{z}}^{3}+{\bm{z}}^{2}+{\bm{z}}^{0}=0$ (see the
list of Conway polynomials [33]). Note that we are using both the integer
representation and the exponent representation of a finite field element. For
instance, $122$ has the binary representation $01111010$, corresponding to
${\bm{z}}^{6}+{\bm{z}}^{5}+{\bm{z}}^{4}+{\bm{z}}^{3}+{\bm{z}}={\bm{z}}^{229}$.
This is a $\text{GRS}(A,6,\vec{\bm{\lambda}})$ with
$A=[0,8]=\\{0,1,{\bm{z}},{\bm{z}}^{25}=1~{}+~{}{\bm{z}},{\bm{z}}^{2},{\bm{z}}^{50}={\bm{z}}^{2}+{\bm{z}}^{0},{\bm{z}}^{26}={\bm{z}}^{2}+{\bm{z}},{\bm{z}}^{198}={\bm{z}}^{2}+{\bm{z}}~{}+~{}1,{\bm{z}}^{3}\\}$
and
$\vec{\bm{\lambda}}=({\bm{z}}^{177},{\bm{z}}^{177},{\bm{z}}^{5},{\bm{z}}^{5},{\bm{z}}^{234},{\bm{z}}^{234},{\bm{z}}^{208},{\bm{z}}^{208},{\bm{z}}^{119})$.
Using [28, Ch. 10, Thm. 4], we can deduce that the dual of this
$\text{GRS}(A,6,\vec{\bm{\lambda}})$ is an
$\text{GRS}(A,3,\vec{\bm{\gamma}})$, where
$\vec{\bm{\gamma}}=({\bm{z}}^{47},{\bm{z}}^{82},{\bm{z}}^{171},{\bm{z}}^{239},{\bm{z}}^{221},{\bm{z}}^{144},{\bm{z}}^{75},{\bm{z}}^{199},1)$.
We believe that the selection of $A$ as the first $n$ nonegative integers in
ISA-L is purely for the convenience of the for-loops in its C code and has no
significant reasons behind.

###  III-C Code Construction in Backblaze Vaults

Backblaze Vaults ([34, 35]) uses a systematic generator matrix
${\bm{G}}=[{\bm{I}}_{k}\mid\bm{V}_{1}^{-1}\bm{V}_{2}]=\bm{V}_{1}^{-1}\bm{V}$,
where $\bm{V}=[\bm{V}_{1}\mid\bm{V}_{2}]$ is the $k\times n$ Vandermonde
matrix created by the finite field elements corresponding to $0,1,\ldots,n-1$.
In other words, this is a standard $\text{RS}(A,k)$ in which $A=[0,n-1]$, the
same set of evaluation points as in the $\text{GRS}(A,k,\vec{\bm{\lambda}})$
of ISA-L.

###  III-D Code Construction in Facebook’s f4

The GRS(14,10) used in Facebook’s f4 storage system [36] has been used
repeatedly in the literature to demonstrate either the inefficiency of Reed-
Solomon code’s naive repair scheme or improvements from it. At the moment we
could no longer locate the official source of the implementation of this code.
However, from the previous studies [2, 3, 4, 10] and from our own copy of the
code, GRS(14,10) in f4 was constructed via the generator polynomial (see [28,
Chp. 7]) $g(x)=(x-1)(x-{\bm{z}})(x-{\bm{z}}^{2})(x-{\bm{z}}^{3})$. In general,
the generator polynomial is $g(x)=\prod_{i=0}^{r-1}(x-{\bm{z}}^{i})$ and the
codewords correspond to vectors of coefficients of all polynomials
$c(x)=\sum_{i=0}^{n-1}{\bm{c}}_{i}x^{i}\in{\mathbb{F}}_{256}[x]$ that admit
$1,{\bm{z}},{\bm{z}}^{2},\ldots,{\bm{z}}^{r-1}$ as roots, where $r=n-k$.
Equivalently, the code has a parity check matrix
${\bm{H}}=\text{Vand}(1,{\bm{z}},{\bm{z}}^{2},\ldots,{\bm{z}}^{n-1})$, and
hence, it is the dual of an $\text{RS}(A,k)$ with
$A=\\{1,{\bm{z}},{\bm{z}}^{2},\ldots,{\bm{z}}^{n-1}\\}$.

To summarize, all (valid) constructions of (generalized) Reed-Solomon codes in
industry available to us, although may look different, are still the same as
the original one provided in Section III-A. This is good news because we can
focus on just the original construction. Although straightforward, this
section serves as a one-stop reference for future studies in this direction.

##  IV Heuristic Search for Low-Bandwidth Schemes

###  IV-A Trace Repair Framework

Following the framework developed in [3, 4], a (linear) trace repair scheme
for the component ${\bm{c}}_{j^{*}}$ of a codeword $\vec{\bm{c}}$ of a linear
$[n,k]$ code ${\mathcal{C}}$ over $\mathbb{F}_{q^{\ell}}$ corresponds to a set
of $\ell$ dual codewords
$\left\\{{\vec{\bm{g}}^{(i)}}\right\\}_{i\in[\ell]}\subset\mathcal{C}^{\perp}$,
${\vec{\bm{g}}^{(i)}}=\left({\vec{\bm{g}}^{(i)}}_{1},\ldots,{\vec{\bm{g}}^{(i)}}_{n}\right)$,
satisfying the Full-Rank Condition:
$\mathsf{rank}_{\mathbb{F}_{q}}\big{\\{}{\vec{\bm{g}}^{(i)}_{j^{*}}}\colon
i\in[\ell]\big{\\}}=\ell$. Such a repair scheme is denoted
${\mathcal{R}}\left(\\{{\vec{\bm{g}}^{(i)}}\\}_{i\in[\ell]}\right)$, which can
be viewed as an $\ell\times n$ repair matrix with ${\vec{\bm{g}}^{(i)}_{j}}$
as its $(i,j)\text{-entry}$. As established in [3, 4], the repair bandwidth of
such a repair scheme (in bits) is
$b({\mathcal{R}})=\sum_{j\in[n]\setminus\\{j^{*}\\}}r_{j}$, where
$r_{j}\triangleq\mathsf{rank}_{\mathbb{F}_{q}}\left(\left\\{{\vec{\bm{g}}^{(i)}_{j}}\colon
i\in[\ell]\right\\}\right)$. To repair all $n$ components of $\vec{\bm{c}}$,
we need $n$ such repair schemes (possibly with repetition). See, e.g., [22],
for a detailed explanation of why the above scheme works with an example. We
describe an implementation of this repair scheme later in Section V.

Note that as the dual of a (generalized) Reed-Solomon code is another
generalized Reed-Solomon code, searching for a set of dual codewords is
equivalent to searching for a set of polynomials $\left\\{g_{i}(x)\colon
i\in[\ell]\right\\}\subset\mathbb{F}_{q^{\ell}}[x]$ of degree at most $r-1$.
Using the notation above, we have
${\vec{\bm{g}}^{(i)}_{j}}=\bm{\lambda}_{j}g_{i}(\bm{\alpha}_{j})$. As
$\bm{\lambda}_{j}$’s do not affect the repair bandwidth, we usually ignore
them.

###  IV-B Heuristic Search for Low-Bandwidth Repair Schemes

As discussed in Section III and Section IV-A, to construct low-bandwidth
repair schemes for Reed-Solomon codes over ${\mathbb{F}}_{256}$, one must find
sets of eight check polynomials
$\left\\{g_{i}(x)\right\\}_{i\in[8]}\subset{\mathbb{F}}_{256}[x]$ that satisfy
the Full-Rank Condition while incurring low repair bandwidths.

There are two main types of check polynomials applicable for Reed-Solomon
codes over ${\mathbb{F}}_{256}$: the algebraic ones are based on algebraic
structures such as subfields and subspaces [3, 4, 9, 22, 15, 23] or cosets of
subfields [11, 12], while the others are found by a computer search [3, 10].
In some special cases, for example when $r=4$ and $n\geq 12$ (e.g., GRS(14,10)
or GRS(12,8)), the algebraic constructions generate the lowest known repair
bandwidths [23]. But for many other cases, an algebraic construction only
yields an insignificant reduction from the naive bandwidth, e.g., $6\%$ when
$r=3$ and $n=11$, whereas a computer search can produce a scheme achieving a
much higher reduction, e.g., $28\%$ in this case (see Table III).

Note that there are many different RS$(n,k)$’s depending on which set of
evaluation points $A$ is chosen (we will show later that different $A$’s may
lead to different (optimal) repair bandwidths). In this work, we examine two
types of codes:

  * •

ISAL-codes: $A=[0,n-1]\subseteq{\mathbb{F}}_{256}$, $n\leq 256$,

  * •

${\mathbb{F}}_{16}$-based codes:
$A=\\{0,1,{\bm{z}}_{16},\ldots,{\bm{z}}_{16}^{n-2}\\}\subseteq{\mathbb{F}}_{16}$,
$n\leq 16$, where ${\bm{z}}_{16}$ is a primitive element of
${\mathbb{F}}_{16}$ satisfying ${\bm{z}}_{16}^{4}+{\bm{z}}_{16}+1=0$ (see the
list of Conway polynomials [33]).

Searching for good repair schemes for ISAL-codes is much harder because of the
very large search space (over ${\mathbb{F}}_{256}$). For
${\mathbb{F}}_{16}$-based codes, the search complexity is lower, which allows
us to locate good schemes within a reasonable amount of time. The “lifting”
technique, which previously has been employed only in the context of algebraic
constructions [13, 14, 11, 12, 23], is now used in our heuristic algorithms to
transform a repair scheme for codes over ${\mathbb{F}}_{16}$ to a repair
scheme for codes over ${\mathbb{F}}_{256}$ (Proposition 2). We observe that
the current-best repair bandwidths of ${\mathbb{F}}_{16}$-based codes are
always at least as low as those of ISAL-codes and in many cases are smaller.
Showing that this is true in general for Reed-Solomon codes over
${\mathbb{F}}_{256}$ (or finding a counterexample) is an interesting open
problem.

To find the lowest-bandwidth repair scheme, in general, we need to examine
$\binom{P}{\ell}$ different sets of $\ell$ polynomials each, where $P$ is the
number of candidate check polynomials. This number is huge even for very
modest parameters. To reduce the search complexity, one needs to reduce $P$
and/or $\ell$. We discuss different ways to achieve complexity reduction
below.

To reduce $P$, the number of candidate check polynomials, we make the
following simplifying assumptions (see also [10]).

  * •

(A1) $\deg(g_{i})=r-1$: we prove in Proposition 1 that this assumption does
not lead to suboptimal solutions, and

  * •

(A2) $g_{i}(x)$ has $r-1$ (possibly repeated) roots in $A$: this is based on
the (unproven) intuition that more zeros in the repair matrix ${\mathcal{R}}$
may lead to a low repair bandwidth. This has been confirmed empirically in our
various experiments.

######  Proposition 1.

Let $\left\\{g_{i}(x)\right\\}_{i\in[\ell]}$ be a set of check polynomials of
degree at most $r-1$ corresponding to a repair scheme for ${\bm{c}}_{j^{*}}$
of an $\text{RS}(A,k)$ over $\mathbb{F}_{q^{\ell}}$. Then there exists another
set of check polynomials $\left\\{h_{i}(x)\right\\}_{i\in[\ell]}$ of degree
exactly $r-1$ that can repair ${\bm{c}}_{j^{*}}$ with the same or smaller
bandwidth.

###### Proof.

Case 1. If one polynomial has degree exactly $r-1$, e.g., $\deg(g_{1})=r-1$,
then we set

$h_{i}(x)=\begin{cases}g_{i}(x),&\text{ if }\deg(g_{i})=r-1,\\\
g_{i}(x)+g_{1}(x),&\text{ if }\deg(g_{i})<r-1.\end{cases}\vspace{-3pt}$

Then $\deg(h_{i})=r-1$ for every $i$ and moreover,

$\mathsf{span}_{\mathbb{F}_{q}}\left(\\{h_{i}(\bm{\alpha})\\}_{i\in[\ell]}\right)=\mathsf{span}_{\mathbb{F}_{q}}\left(\\{g_{i}(\bm{\alpha})\\}_{i\in[\ell]}\right),$

for every $\bm{\alpha}\in A$. Thus, $\left\\{h_{i}(x)\right\\}_{i\in[\ell]}$
is another repair scheme for ${\bm{c}}_{j^{*}}$ and has the same bandwidth as
$\left\\{g_{i}(x)\right\\}_{i\in[\ell]}$.

Case 2. If $\deg(g_{i})<r-1$ for every $i\in[\ell]$ then we select an
$\overline{\bm{\alpha}}\in A\setminus\\{\bm{\alpha}_{j^{*}}\\}$ and set
$h_{i}(x)=g_{i}(x)(x-\overline{\bm{\alpha}})^{r-1-\max_{t}\\{\deg(g_{t})\\}}$.
Then $\left\\{h_{i}(x)\right\\}_{i\in[\ell]}$ is another repair scheme for
${\bm{c}}_{j^{*}}$ and has the same or smaller bandwidth. Moreover, at least
one $h_{i}$ has degree exactly $r-1$, which reduces this case to Case 1. ∎

To reduce $\ell$, the number of polynomials needed in a search, we use the
well-known lifting and extension techniques. The lifting technique allows us,
for instance, to transform a repair scheme for a Reed-Solomon code constructed
in ${\mathbb{F}}_{16}$ to a repair scheme for another Reed-Solomon code
constructed in ${\mathbb{F}}_{256}$ using the same set of evaluation points
while doubling the bandwidth. The extension technique allows us, for example,
to transform a repair scheme of a Reed-Solomon code over ${\mathbb{F}}_{256}$
with the base field ${\mathbb{F}}_{4}$ into a repair scheme with base field
$\mathbb{F}_{2}$. For completeness, we formalize these techniques below.

######  Proposition 2 (Lifting).

Suppose that $m\mid\ell$ and
$\\{g_{i}(x)\\}_{i\in[m]}\subset\mathbb{F}_{q^{m}}[x]$ corresponds to a repair
scheme with bandwidth $b$ (measured in elements in $\mathbb{F}_{q}$) for the
$j^{*}$-th component of an $\text{RS}(A,k)$ over $\mathbb{F}_{q^{m}}$. Then
$\\{\bm{\beta}_{j}g_{i}(x)\\}_{i\in[m],j\in[\ell/m]}$, where
$\\{\bm{\beta}_{j}\\}_{j\in[\ell/m]}$ is an $\mathbb{F}_{q^{m}}$-basis of
$\mathbb{F}_{q^{\ell}}$, corresponds to a repair scheme with bandwidth
$\frac{\ell}{m}b$ for the $j^{*}$-component of the $\text{RS}(A,k)$ with the
same evaluations points $A$ but constructed over $\mathbb{F}_{q^{\ell}}$.

######  Proposition 3 (Extension).

Suppose that $m$ divides $\ell$ and the set
$\\{g_{i}(x)\\}_{i\in[\ell/m]}\subset\mathbb{F}_{q^{\ell}}[x]$ corresponds to
a repair scheme with bandwidth $b$ (measured in elements in
$\mathbb{F}_{q^{m}}$) for the component ${\bm{c}}_{j^{*}}$ of an
$\text{RS}(A,k)$ over $\mathbb{F}_{q^{\ell}}$, treating $\mathbb{F}_{q^{m}}$
as the base field. Then the set
$\\{\bm{\gamma}_{j}g_{i}(x)\\}_{i\in[\ell/m],j\in[m]}$, where
$\\{\bm{\gamma}_{j}\\}_{j\in[m]}$ is an $\mathbb{F}_{q}$-basis of
$\mathbb{F}_{q^{m}}$, corresponds to a repair scheme with bandwidth $bm$
(measured in elements in $\mathbb{F}_{q}$) for the ${\bm{c}}_{j^{*}}$ of the
same code.

Applying the above complexity reduction assumptions and techniques, we
construct low-bandwidth repair schemes for ISAL-codes and
${\mathbb{F}}_{16}$-codes utilizing the following algorithms.

  * •

Algorithm 1: (degree-four repair) Introduced in [10] to tackle GRS(14,10) over
${\mathbb{F}}_{256}$, this algorithm first constructs a list of pairs of
polynomials in $\mathbb{F}_{q^{\ell}}[x]$ (treating $\mathbb{F}_{q^{\ell/2}}$
as the base field) that has bandwidth at most a threshold $\theta_{2}$, and
then search for sets of four polynomials (treating $\mathbb{F}_{q^{\ell/4}}$
as the base field) consisting of two pairs from that list (keeping the first
pair unchanged while adding a multiplicative factor to the second) that has
bandwidth at most $\theta_{4}$ $(\theta_{4}<\theta_{2})$. Various thresholds
$\theta_{2}$ and $\theta_{4}$ were tested to produce the lowest bandwidth.

  * •

Algorithm 2: (exhaustive search) For $r=2,3$, we can also apply a direct
exhaustive search for sets of polynomials with low-bandwidths. Note that we do
not have to wait for the algorithm to finish (which would take too long). We
can retrieve the currently found bandwidths for all codeword components and
stop if find them satisfactory or see that there is little chance to improve
further.

Note that both algorithms go through each valid set of polynomials once and
check which codeword components could be repaired by the set. Algorithm 1
terminates if repair schemes of bandwidth not exceeding the specified
threshold have been found for all codeword components. Best found bandwidths
for codes with $4\leq n\leq 16$ and $2\leq r\leq 4$ are reported in Table II,
Table III, and Table IV. Column “${\mathbb{F}}_{16}$-based algebraic” refers
to repair schemes using subspace polynomials and lifting [12, 22].
${\mathbb{F}}_{16}$-based heuristic always finds the best bandwidths, which
could also be due to the fact that it is cheaper to search over
${\mathbb{F}}_{16}$ than ${\mathbb{F}}_{256}$. We maintain a web page [37] to
keep track of the best bandwidths and the corresponding repair schemes.

Redundancy $r=2$ |  Default |  ISA-L heuristic |  $\mathbb{F}_{16}$-based algebraic |  $\mathbb{F}_{16}$-based heuristic
---|---|---|---|---
$n=4$ |  16 |  12 (-25%) |  18 (+12.5%) |  12 (-25%)
$n=5$ |  24 |  18 (-25%) |  24 (-0%) |  18 (-25%)
$n=6$ |  32 |  24 (-25%) |  30 (-6.3%) |  24 (-25%)
$n=7$ |  40 |  32 (-20%) |  36 (-10%) |  30 (-25%)
$n=8$ |  48 |  38 (-20.8%) |  42 (-12.5%) |  38 (-20.8%)
$n=9$ |  56 |  44 (-21.4%) |  48 (-14.3%) |  44 (-21.4%)
$n=10$ |  64 |  50(-21.9%) |  54 (-15.6%) |  50 (-21.9%)
$n=11$ |  72 |  58 (-19.4%) |  60 (-16.7%) |  56 (-22.2%)
$n=12$ |  80 |  64 (-20%) |  66 (-17.5%) |  64 (-20%)
$n=13$ |  88 |  72 (-18.2%) |  72 (-18.2%) |  70 (-20.5%)
$n=14$ |  96 |  80 (-16.7%) |  78 (-18.8%) |  76 (-20.8%)
$n=15$ |  104 |  84 (-19.2%) |  84 (-19.2%) |  84 (-19.2%)
$n=16$ |  112 |  90 (-19.6%) |  90 (-19.6%) |  90 (-19.6%)
TABLE II: Current-best repair bandwidths (measured in bits) for Reed-Solomon codes with $4\leq n\leq 16$ and $r=2$. Redundancy $r=3$ |  Default |  ISA-L heuristic |  $\mathbb{F}_{16}$-based algebraic |  $\mathbb{F}_{16}$-based heuristic
---|---|---|---|---
$n=4$ |  8 |  8 (-0%) |  18(+100%) |  8 (-0%)
$n=5$ |  16 |  12 (-25%) |  24 (+50%) |  12 (-25%)
$n=6$ |  24 |  16 (-33.3%) |  30 (+25%) |  16 (-33.3%)
$n=7$ |  32 |  22 (-31.3%) |  36 (+12.5%) |  22 (-31.3%)
$n=8$ |  40 |  28 (-30%) |  42 (+5%) |  28 (-30%)
$n=9$ |  48 |  34 (-29.2%) |  48 (0%) |  32 (-33.3%)
$n=10$ |  56 |  40 (-28,6%) |  54 (-3.6%) |  40 (-28,6%)
$n=11$ |  64 |  46 (-28.1%) |  60 (-6.3%) |  46 (-28.1%)
$n=12$ |  72 |  52 (-27.8%) |  66 (-8.3%) |  52 (-27.8%)
$n=13$ |  80 |  58 (-27.5%) |  72 (-10%) |  58 (-27.5%)
$n=14$ |  88 |  66 (-25%) |  78 (-11.4%) |  64 (-27.3%)
$n=15$ |  96 |  72 (-25%) |  84(-12.5%) |  70 (-27.1%)
$n=16$ |  104 |  78 (-25%) |  90 (-13.5%) |  76 (-26.9%)
TABLE III: Current-best repair bandwidths (measured in bits) for Reed-Solomon codes with $4\leq n\leq 16$ and $r=3$. Redundancy $r=4$ |  Default |  ISA-L heuristic |  $\mathbb{F}_{16}$-based algebraic |  $\mathbb{F}_{16}$-based heuristic
---|---|---|---|---
$n=5$ |  8 |  8 (-0%) |  16 (+100%) |  8 (-0%)
$n=6$ |  16 |  12 (-25%) |  20 (+25%) |  12 (-25%)
$n=7$ |  24 |  16 (-33.3%) |  24 (0%) |  16 (-33.3%)
$n=8$ |  32 |  22 (-31.3%) |  28 (-12.5%) |  22 (-31.3%)
$n=9$ |  40 |  28 (-30%) |  32 (-20%) |  26 (-35%)
$n=10$ |  48 |  36 (-25%) |  36 (-25%) |  32 (-33.3%)
$n=11$ |  56 |  42 (-25%) |  40 (-28.6%) |  38 (-32.1%)
$n=12$ |  64 |  48 (-25%) |  44 (-31.3%) |  44 (-31.3%)
$n=13$ |  72 |  54 (-25%) |  48 (-33.3%) |  48 (-33.3%)
$n=14$ |  80 |  62 (-22.5%) |  52 (-35%) |  52 (-35%)
$n=15$ |  88 |  68 (-22.7%) |  56 (-36.4%) |  56 (-36.4%)
$n=16$ |  96 |  60 (-37.5%) |  60 (-37.5%) |  60 (-37.5%)
TABLE IV: Current-best repair bandwidths (measured in bits) for Reed-Solomon
codes with $5\leq n\leq 16$ and $r=4$.

######  Definition 2 (Bandwidth profile).

Given $n>0$ and $\ell>0$, a bandwidth profile
$\vec{b}=(b_{1},b_{2},\ldots,b_{n})$, $b_{j}\in[\ell]$, is feasible for an
$\text{RS}(A,k)$, where $A\subseteq\mathbb{F}_{q^{\ell}}$, $|A|=n$, if there
exists a collection of $n$ repair schemes that require bandwidth $b_{j}$ for
the $j$-th components of its codeword, $j\in[n]$. A bandwidth profile
$\vec{b}^{*}$ is optimal if for every $j\in[\ell]$, $b^{*}_{j}$ is the lowest
bandwidth possible to (linearly) repair the $j$-th codeword component of the
code.

Note that in Table II, Table III, and Table IV, we report
$\max\big{(}\vec{b}\big{)}\triangleq\max\\{b_{j}\colon j\in[\ell]\\}$, where
$\vec{b}$ is a feasible bandwidth profile. Individual components may require
lower bandwidths. Visit our web page [37] for the most updated bandwidths.

###  IV-C The Impact of Evaluation Points

In this section we discuss important issues regarding the selection of the
evaluation points in Reed-Solomon codes. In particular, we demonstrate via an
example that different sets of evaluation points may lead to different repair
bandwidths.

######  Proposition 4.

Translating and dilating the set of evaluation points of a Reed-Solomon code
do not affect its optimal bandwidth profile. In other words, $\text{RS}(A,k)$
and $\text{RS}(\bm{\beta}A+\bm{\gamma},k)$, where
$\bm{\beta},\bm{\gamma}\in\mathbb{F}_{q^{\ell}}$, $\bm{\beta}\neq 0$, have the
same optimal bandwidth profile (up to a permutation).

###### Proof.

Suppose that $\\{g_{i}(x)\\}_{i\in[\ell]}$ is a repair scheme for
$\text{RS}(A,k)$, which can be used to repair $f(\bm{\alpha}_{j})$,
$\bm{\alpha}_{j}\in A$, and has bandwidth $b$. We set $h_{i}(x)\triangleq
g_{i}\left((x-\bm{\gamma})/\bm{\beta}\right)$, $i\in[\ell]$. Then
$h_{i}(\bm{\beta}\bm{\alpha}+\bm{\gamma})=g_{i}(\bm{\alpha})$ for every
$\bm{\alpha}\in A$. Therefore, $\\{h_{i}(x)\\}_{i\in[\ell]}$ can be used to
repair $\bm{\beta}\bm{\alpha}_{j}+\bm{\gamma}\in\bm{\beta}A+\bm{\gamma}$ with
bandwidth $b$. Hence,
$\bm{\beta}\bm{\alpha}+\bm{\gamma}\in\bm{\beta}A+\bm{\gamma}$ can be repaired
in $\text{RS}(\bm{\beta}A+\bm{\gamma},k)$ with a bandwidth not exceeding that
for $\bm{\alpha}\in A$ in $\text{RS}(A,k)$. Since
$A=\bm{\beta}^{-1}(\bm{\beta}A+\bm{\gamma})-\bm{\beta}^{-1}\bm{\gamma}$, the
same argument proves that the reverse conclusion is also true. Thus, these two
codes have the same optimal repair bandwidth for their corresponding codeword
components ($f(\bm{\alpha})$ and $f(\bm{\beta}\bm{\alpha}+\bm{\gamma})$). ∎

As a corollary of Proposition 4, although there are $\binom{q^{\ell}}{n}$
different RS$(n,k)$ codes over $\mathbb{F}_{q^{\ell}}$, we can divide them
into classes of codes that have evaluation points obtained from each other by
translations and dilations. Each class can have at most $q^{\ell}(q^{\ell}-1)$
members with the same optimal bandwidth profile (up to permutations).
Identifying other transformations of $A$ that preserve the optimal bandwidth
profile is an open problem.

To examine the impact of evaluation points on repair bandwidths, we consider
RS(5,3) codes over ${\mathbb{F}}_{16}$, which have small $r$ and field size
and hence allow us to determine their optimal bandwidth profiles. An RS(5,3)
(with a given generator matrix) was first investigated in [2]. We searched
through all 524,160 different arrangements of five elements in
${\mathbb{F}}_{16}$ and found 240 different $A$’s (orders of elements are
important) giving rise to the same code, e.g.,
$A=\\{0,1,{\bm{z}}_{16}^{14},{\bm{z}}_{16}^{8},{\bm{z}}_{16}^{12}\\}$, where
${\bm{z}}_{16}$ is a primitive element of ${\mathbb{F}}_{16}$ satisfying
${\bm{z}}_{16}^{4}+{\bm{z}}_{16}+1=0$. It was shown in [2] that the optimal
repair bandwidth for each systematic component $(j=1,2,3)$ is 10 bits. On the
other hand, from Table II and [37], we know that 9 bits are sufficient to
repair other RS(5,3) codes. This shows that different sets of evaluation
points can lead to different repair bandwidths.

In fact, we have obtained a complete picture of the bandwidth profiles of all
RS$(n,n-2)$ codes, $4\leq n\leq 16$, over ${\mathbb{F}}_{16}$. First, from the
list of $16$ monic polynomials of degree one over ${\mathbb{F}}_{16}$, we
created a list of $6,142,500=\binom{16}{4}15^{3}$ sets of four check
polynomials (keeping the first monic while adding arbitrary nonzero
coefficients to others). We then generate a rank profile $\vec{{\sf
r}}=(r_{1},r_{2},\ldots,r_{16})$ for each polynomials set and remove those
whose components are all smaller than 4, which took our GAP program 10 hours
to complete. More than six millions sets of polynomials remain as potential
repair schemes. For each $A\subseteq{\mathbb{F}}_{16}$, we determine the
optimal repair bandwidth for each codeword component of $\text{RS}(A,k)$ by
going through all the rank profiles, restricting to the positions in $A$. For
instance, when $n=5$ and $k=3$, among $4368=\binom{16}{5}$ different 5-subsets
$A\subset{\mathbb{F}}_{16}$, 2880 have bandwidth profile $(9,9,9,9,8)$, 1440
have bandwidth profile $(9,9,9,9,9)$, while only 48 have bandwidth profile
$(10,10,10,10,10)$. It turns out that the RS(5,3) examined in [2] is
accidentally among the minority that require 10 bits. Most others need only 9
bits.

##  V An Implementation of Trace Repair Schemes in C

We implemented a trace repair scheme [27] on top of the existing C code in the
ISA-L [29]. As the bandwidth reduction is known, we focus on minimizing the
computational complexity. Following our notation in the C code, Node $j$ aims
to recovers ${\bm{c}}_{j}$ by downloading relevant data from Nodes $i$, $i\in
I\subseteq[n]\setminus\\{j\\}$. In ISA-L $|I|=k$ while in our implementation
$|I|=n-1$. The code implemented in ISA-L is systematic, i.e., the first $k$
components are data and the last $n-k$ components of each codeword are
parities. Finite field elements over ${\mathbb{F}}_{256}$ are represented as
integers in $[0,255]$ (see Section II).

###  V-A ISA-L Implementation

ISA-L uses the naive scheme to repair the generalized Reed-Solomon codes,
which means that each helper Node $i$ simply reads and sends ${\bm{c}}_{i}$
without performing any computation. Node $j$, after receiving data from $k$
nodes, can recover ${\bm{c}}_{j}$ as follows. A lost parity component can be
repaired by downloading the data components (systematic part) and performing
encoding. A missing data component, however, requires more work: Node $j$
performs first a matrix inversion to obtain $({\bm{G}}[I])^{-1}$, where
${\bm{G}}[I]$ denotes the submatrix of ${\bm{G}}$ consisting of columns of
${\bm{G}}$ indexed by $I$, and then multiply this matrix with the vector
consisting of ${\bm{c}}_{i},i\in I$. This procedure is repeated for $T$
different codewords, where $T$ is a large number representing the number of
codewords to be repaired. For instance, if the encoded file has size 60 MB,
and an RS(9,6) is used, then $T$ is roughly ten million. Note that the matrix
inversion is done only once.

###  V-B Our Implementation

In a trace repair scheme, as opposed to ISA-L, both senders and receiver
perform computations. As a large number of codewords are being repaired, say,
millions, it is crucial to identify parts of the computation that could be
precomputed and stored for fast access. We convert the $n$ repair schemes (for
$n$ components) into three lookup tables: $H$ (helper) allows the helper nodes
to create the repair traces (bits) while $R$ (recover) and $D$ (dual basis)
allow the receiver node to process the repair traces and recover the lost
component. Please refer to [22] for undefined terminologies. A frequently used
operation is the XOR-sum of the bits of an integer. Hence, we precompute an
array called ${\sf{Parity}}$ that store these values for all $m\in[0,255]$. We
describe below the computation for one codeword.

Sender side. Node $i$ extracts the number of traces to be sent
$r_{i}=H[i][j][0]$, and uses $r_{i}$ numbers $H[i][j][1]$ to $H[i][j][r_{i}]$
to compute $r_{i}$ repair traces. Table $H$ is defined in a way that the
$s$-th trace from Node $i$ is the inner product of $H[i][j][s]$ and
${\bm{c}}_{i}$,

${\sf{RepairTrace}}_{i}[s]={\sf{Parity}}\big{[}H[i][j][s]\ \&\
{\bm{c}}_{i}\big{]},\quad s\in[1,r_{i}].\vspace{-3pt}$

Node $i$ then sends ${\sf{RepairTrace}}_{i}$ to Node $j$.

Receiver side. Node $j$ uses ${\sf{RepairTrace}}_{i}$,
$i\in[n]\setminus\\{j\\}$, $R$, and $D$ to recover ${\bm{c}}_{j}$ as follows.
For each $i$, it generates eight column traces ${\sf{ColumnTrace}}_{i}[s]$,
$s\in[8]$, using the formula

${\sf{ColumnTrace}}_{i}[s]={\sf{Parity}}\big{[}R[i][j][s]\ \&\
{\sf{Dec}}({\sf{RepairTrace}}_{i})\big{]},\vspace{-3pt}$

where ${\sf{Dec}}({\sf{RepairTrace}}_{i})$ turns the $r_{i}$ bits in
${\sf{RepairTrace}}_{i}$ into a decimal number, ready for bitwise operations.
${\sf{Dec}()}$ is also implemented using bit-shift and XOR operations.
Finally,

${\bm{c}}_{j}=\oplus_{s=1}^{8}\big{(}\big{(}\oplus_{i\in[n]\setminus\\{j\\}}{\sf{ColumnTrace}}_{i}[s]\big{)}\times
D[s]\big{)}.$

| Senders | Receiver | Total
---|---|---|---
ISA-L (naive) | 0 (sec) | 0.57 (sec) | 0.57 (sec)
Trace repair | 0.2 (sec) | 1.4 (sec) | 1.6 (sec)
TABLE V: The running times of the naive repair (ISA-L) and trace repair for an
RS(9,6) over ten millions codewords and (random) single erasures (on a Linux
server: Intel(R) Xeon(R) CPU E5-2690 v2 @ 3.00GHz with 792 GB RAM). For
senders, the maximum running time among all helpers was used.

In our implementation [27], we further optimize the code by joining the above
steps at the receiver to save time. For RS(9,6), our implementation is 2.8x
slower than ISA-L (Table V). For other codes such as RS(11,8), RS(16,13),
RS(12,8), RS(14,10), RS(16,12), the gap is 1.8x-2.4x. Despite being a negative
result, the small gaps are encouraging because trace repair is inherently more
complicated. Further optimizations may also reduce the gaps. As shown in [38,
Fig. 1], the network transfer time is much larger than the computation time
(say, 40 times) in naive repair. Hence, the reduction in bandwidth can well
compensate the computation time and make trace repair faster. For example, a
combination of 33% reduction in bandwidth and 200% increase in computation
time could still lead to a 1.25x speed-up compared to naive repair.
Implementing trace repairs on Hadoop 3 to verify this observation is a future
work.

## Acknowledgement

This work has been supported by the 210124 ARC DECRA Grant DE180100768. We
thank Nguyen Dinh Quang Minh and Dau Trung Dung for their help in the
implementation.

## References

  * [1] I. S. Reed and G. Solomon, “Polynomial codes over certain finite fields,” _J. Soc. Ind. Appl. Math._ , vol. 8, no. 2, pp. 300–304, 1960.
  * [2] K. Shanmugam, D. S. Papailiopoulos, A. G. Dimakis, and G. Caire, “A repair framework for scalar MDS codes,” _IEEE J. Selected Areas Comm. (JSAC)_ , vol. 32, no. 5, pp. 998–1007, 2014.
  * [3] V. Guruswami and M. Wootters, “Repairing Reed-Solomon codes,” in _Proc. Annu. Symp. Theory Comput. (STOC)_ , 2016.
  * [4] ——, “Repairing Reed-Solomon codes,” _IEEE Trans. Inform. Theory_ , vol. 63, no. 9, pp. 5684–5698, 2017.
  * [5] M. Ye and A. Barg, “Explicit constructions of MDS array codes and RS codes with optimal repair bandwidth,” in _Proc. IEEE Int. Symp. Inform. Theory (ISIT)_ , 2016, pp. 1202–1206.
  * [6] ——, “Explicit constructions of high-rate MDS array codes with optimal repair bandwidth,” _IEEE Trans. Inform. Theory_ , vol. 63, no. 4, pp. 2001–2014, 2017.
  * [7] A. Chowdhury and A. Vardy, “Improved schemes for asymptotically optimal repair of MDS codes,” in _Proc. 55th Annual Allerton Conf. Comm Control Comput. (Allerton)_ , 2017.
  * [8] ——, “Improved schemes for asymptotically optimal repair of MDS codes,” _IEEE Trans. Inform. Theory_ , vol. 67, no. 8, pp. 5051–5068, 2021.
  * [9] H. Dau and O. Milenkovic, “Optimal repair schemes for some families of Reed-Solomon codes,” in _Proc. IEEE Int. Symp. Inform. Theory (ISIT)_ , 2017, pp. 346–350.
  * [10] I. Duursma and H. Dau, “Low bandwidth repair of the RS(10,4) Reed-Solomon code,” in _Proc. Inform. Theory Applicat. Workshop (ITA)_ , 2017.
  * [11] W. Li, Z. Wang, and H. Jafarkhani, “A tradeoff between the sub-packetization size and the repair bandwidth for Reed-Solomon code,” in _Proc. 55th Annual Allerton Conf. Comm. Control Comput. (Allerton)_ , 2017, pp. 942–949.
  * [12] ——, “On the sub-packetization size and the repair bandwidth of Reed-Solomon codes,” _IEEE Trans. Inform. Theory_ , vol. 65, no. 9, pp. 5484–5502, 2019.
  * [13] I. Tamo, M. Ye, and A. Barg, “Optimal repair of Reed-Solomon codes: Achieving the cut-set bound,” in _Proc. 58th Annual IEEE Symp. Foundations Computer Sci. (FOCS)_ , 2017.
  * [14] ——, “The repair problem for Reed-Solomon codes: Optimal repair of single and multiple erasures with almost optimal node size,” _IEEE Trans. Inform. Theory_ , vol. 65, no. 5, pp. 2673–2695, 2018.
  * [15] A. Berman, S. Buzaglo, A. Dor, Y. Shany, and I. Tamo, “Repairing Reed–Solomon codes evaluated on subspaces,” in _Proc. IEEE Int. Symp. Inform. Theory (ISIT)_ , 2021, pp. 867–871.
  * [16] R. Con and I. Tamo, “Nonlinear repair schemes of Reed-Solomon codes,” 2021. [Online]. Available: https://arxiv.org/abs/2104.01652
  * [17] H. Dau, I. Duursma, H. M. Kiah, and O. Milenkovic, “Repairing Reed-Solomon codes with two erasures,” in _Proc. IEEE Int. Symp. Inform. Theory (ISIT)_ , 2017, pp. 351–355.
  * [18] ——, “Repairing Reed-Solomon codes with multiple erasures,” _IEEE Trans. Inform. Theory_ , vol. 54, no. 10, pp. 6567–6582, 2018.
  * [19] B. Bartan and M. Wootters, “Repairing multiple failures for scalar MDS codes,” in _Proc. 55th Annual Allerton Conf. Comm Control Comput. (Allerton)_ , 2017.
  * [20] J. Mardia, B. Bartan, and M. Wootters, “Repairing multiple failures for scalar MDS codes,” _IEEE Trans. Inform. Theory_ , vol. 65, no. 5, pp. 2661–2672, 2018.
  * [21] Y. Zhang and Z. Zhang, “An improved cooperative repair scheme for Reed-Solomon codes,” in _Proc. 19th Int. Symp. Comm. Inform. Tech. (ISCIT)_ , 2019, pp. 525–530.
  * [22] S. H. Dau, T. X. Dinh, H. M. Kiah, T. T. Luong, and O. Milenkovic, “Repairing Reed-Solomon codes via subspace polynomials,” _IEEE Trans. Inform. Theory_ , vol. 67, no. 10, pp. 6395–6407, 2021.
  * [23] W. Li, Z. Wang, and H. Jafarkhani, “Repairing Reed-Solomon Codes Over $GF(2^{\ell})$,” _IEEE Comm. Lett._ , vol. 24, no. 1, pp. 34–37, 2020.
  * [24] H. Dau, I. Duursma, and H. Chu, “On the I/O costs of some repair schemes for full-length Reed-Solomon codes,” in _Proc. IEEE Int. Symp. Inform. Theory (ISIT)_ , 2018, pp. 1700–1704.
  * [25] H. Dau and E. Viterbo, “Repair schemes with optimal I/O costs for full-length Reed-Solomon codes with two parities,” in _Proc. IEEE Inform. Theory Workshop (ITW)_ , 2018, pp. 590–594.
  * [26] W. Li, H. Dau, Z. Wang, H. Jafarkhani, and E. Viterbo, “On the I/O costs in repairing short-length Reed-Solomon codes,” in _Proc. IEEE Int. Symp. Inform. Theory (ISIT)_ , 2019, pp. 1087–1091.
  * [27] “An implementation of trace repair for Reed-Solomon codes on top of ISA-L,” https://github.com/dausonhoang/tracerepair.
  * [28] F. J. MacWilliams and N. J. A. Sloane, _The Theory of Error-Correcting Codes_. Amsterdam: North-Holland, 1977\.
  * [29] “Intel(R) Intelligent Storage Acceleration Library (ISA-L)’s Reed-Solomon codes,” available at https://github.com/intel/isa-l/blob/master/erasure_code/ec_base.c.
  * [30] “Quantcast File System’s Reed-Solomon code,” available at https://github.com/quantcast/qfs/blob/master/src/cc/qcrs/encode.c.
  * [31] M. Ovsiannikov, S. Rus, D. Reeves, P. Sutter, S. Rao, and J. Kelly, “The Quantcast File System,” _Proc. VLDB Endow._ , vol. 6, no. 11, p. 1092–1101, 2013.
  * [32] R. Roth and G. Seroussi, “On generator matrices of MDS codes,” _IEEE Trans. Inform. Theory_ , vol. 31, no. 6, pp. 826–830, 1985.
  * [33] “Frank Luebeck’s list of Conway polynomials,” available at http://www.math.rwth-aachen.de/~Frank.Luebeck/data/ConwayPol/CP2.html.
  * [34] “Backblaze Vaults’ Reed-Solomon codes,” available at https://www.backblaze.com/blog/reed-solomon/.
  * [35] “Backblaze Vaults’ Reed-Solomon codes source codes,” available at https://github.com/Backblaze/JavaReedSolomon/blob/master/src/main/java/com/backblaze/erasure/ReedSolomon.java.
  * [36] S. Muralidhar, W. Lloyd, S. Roy, C. Hill, E. Lin, W. Liu, S. Pan, S. Shankar, V. Sivakumar, L. Tang, , and S. Kumar, “f4: Facebook’s warm BLOB storage system,” in _Proc. 11th ACM/USENIX Symp. Oper. Syst. Des. Implementation (OSDI)_ , 2014, pp. 383–398.
  * [37] “Records of the current-best repair bandwidths found for short-length Reed-Solomon codes,” https://dausonhoang.github.io/rsbandwidth, backup link https://rsbandwidth.herokuapp.com.
  * [38] S. Mitra, R. Panta, M.-R. Ra, and S. Bagchi, “Partial-parallel-repair (PPR): a distributed technique for repairing erasure coded storage,” in _Proc. European Conf. Computer Syst. (EuroSys)_ , 2016, article No. 30.