text:
\begin{document}

\newcommand{\bfl}{\begin{flushleft}}
\newcommand{\efl}{\end{flushleft}}
\newcommand{\bit}{\begin{itemize}}
\newcommand{\eit}{\end{itemize}}
\newcommand{\ben}{\begin{enumerate}}
\newcommand{\een}{\end{enumerate}}
\newcommand{\bc}{\begin{center}}
\newcommand{\ec}{\end{center}}
\newcommand{\bfr}{\begin{flushright}}

\newtheorem{definition}{Definition}
\newtheorem{example}{Example}
\newtheorem{defn}{Definition}
\newtheorem{thm}{Theorem}[section]
\newtheorem{cor}[thm]{Corollary}
\newtheorem{prop}{Proposition}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{conj}[thm]{Conjecture}
\newtheorem{constr}[thm]{Construction}
\newtheorem{note}{Remark}
\newtheorem{rem}[thm]{Remark}
\newtheorem{eg}{Example}
\newtheorem{property}{Property}
\newtheorem{open}{Open Problems}
\newcommand{\bcor}{\begin{cor}}
	\newcommand{\ecor}{\end{cor}}
\newcommand{\beq}{\begin{equation}}
\newcommand{\eeq}{\end{equation}}
\newcommand{\beqn}{\begin{equation*}}
\newcommand{\eeqn}{\end{equation*}}
\newcommand{\bea}{\begin{eqnarray}}
\newcommand{\eea}{\end{eqnarray}}
\newcommand{\bean}{\begin{eqnarray*}}
	\newcommand{\eean}{\end{eqnarray*}}
\newcommand{\bdefn}{\begin{defn}}
	\newcommand{\edefn}{\end{defn}}
\newcommand{\bnote}{\begin{note}}
	\newcommand{\enote}{\end{note}}
\newcommand{\bprop}{\begin{prop}}
	\newcommand{\eprop}{\end{prop}}
\newcommand{\blem}{\begin{lem}}
	\newcommand{\elem}{\end{lem}}
\newcommand{\bthm}{\begin{thm}}
	\newcommand{\ethm}{\end{thm}}
\newcommand{\bconj}{\begin{conj}}
	\newcommand{\econj}{\end{conj}}
\newcommand{\bconstr}{\begin{constr}}
	\newcommand{\econstr}{\end{constr}}
\newcommand{\bpf}{\begin{proof}}
	\newcommand{\epf}{\end{proof}}
\newcommand\inlineeqno{\stepcounter{equation}\ (\theequation)}

\newcommand{\fq}{\mbox{$\mathbb{F}_q$}}
\newcommand{\fqalpha}{\mbox{$\mathbb{F}_q^{\alpha}$}}
\newcommand{\fqbeta}{\mbox{$\mathbb{F}_q^{\beta}$}}
\newcommand{\fqB}{\mbox{$\mathbb{F}_q^B$}}
\newcommand{\fqstar}{\mbox{$\mathbb{F}_q^{*}$}}
\newcommand{\calc}{\mbox{${\cal C} $}}
\newcommand{\uc}{\mbox{$\underline{c}$}}
\newcommand{\uu}{\mbox{$\underline{u}$}}
\newcommand{\ug}{\mbox{$\underline{g}$}}
\newcommand{\ua}{\mbox{$\underline{a}$}}
\newcommand{\uz}{\mbox{$\underline{z}$}}
\newcommand{\ue}{\mbox{$\underline{e}$}}
\newcommand{\Zs}{\mbox{$\mathbb{Z}_s$}}
\newcommand{\Zt}{\mbox{$\mathbb{Z}_t$}}
\newcommand{\Zst}{\mbox{$\mathbb{Z}_s^t$}}
\newcommand{\Zsn}{\mbox{$\mathbb{Z}_s^n$}}
\newcommand{\calu}{\mbox{${\cal U}$}}
\newcommand{\cale}{\mbox{${\cal E}$}}
\newcommand{\gmds}{\mbox{$G_{\text{\tiny MDS}}$}}
\newcommand{\gpyr}{\mbox{$G_{\text{\tiny PYR}}$}}
\newcommand{\cmds}{\mbox{$C_{\text{\tiny MDS}}$}}
\newcommand{\cpyr}{\mbox{$C_{\text{\tiny PYR}}$}}

\newcommand{\pvk}{\color{blue} }
\newcommand{\pvknew}{\color{cyan} }

\title{Erasure Coding for Distributed Storage: An Overview}
\author{
	\IEEEauthorblockN{ S. B. Balaji, M. Nikhil Krishnan, Myna Vajha, Vinayak Ramkumar, }\\
	\IEEEauthorblockN{ Birenjith Sasidharan and P. Vijay Kumar}\\ \ \\
	\IEEEauthorblockA{Department of Electrical Communication Engineering,\\ Indian Institute of Science, Bangalore.\\

	}
	\thanks{ This survey article will appear in Science China Information Sciences (SCIS) journal.

	M. N. Krishnan and M. Vajha would like to acknowledge the support of Visvesvaraya PhD Scheme for Electronics \& IT awarded by DEITY, Govt. of India. B. Sasidharan presently works as Assistant Professor in the department of Electronics and Communication Engineering in Government Engineering College Barton Hill at Thiruvananthapuram, Kerala, India. P. V. Kumar is also a Visiting Professor at the University of Southern California.  His research is supported in part by the National Science Foundation under Grant No. 1421848 and in part by the joint UGC-ISF research program.}
}
\maketitle

\begin{abstract}
	In a distributed storage system, code symbols are dispersed across space in nodes or storage units as opposed to time. In settings such as that of a large data center, an important consideration is the efficient repair of a failed node.  Efficient repair calls for erasure codes that in the face of node failure, are efficient in terms of minimizing the amount of repair data transferred over the network, the amount of data accessed at a helper node as well as the number of helper nodes contacted. Coding theory has evolved to handle these challenges by introducing two new classes of erasure codes, namely regenerating codes and locally recoverable codes as well as by coming up with novel ways to repair the ubiquitous Reed-Solomon code.
	This survey provides an overview of the efforts in this direction that have taken place over the past decade.
\end{abstract}

\section{Introduction}
This survey article deals with the use of erasure coding for the reliable and efficient storage of large amounts of data in settings such as that of a data center.  The amount of data stored in a single data center can run into tens or hundreds of petabytes.   Reliability of data storage is ensured in part by introducing redundancy in some form, ranging from simple replication to the use of more sophisticated erasure-coding schemes such as Reed-Solomon codes.  Minimizing the storage overhead that comes with ensuring reliability is a key consideration in the choice of erasure-coding scheme.  More recently a second problem has surfaced, namely, that of node repair.

In \cite{RashmiShahGuKuang}, \cite{SathiaAstPap_Xorbas} the authors study the Facebook warehouse cluster and analyze the frequency of node failures as well as the resultant network traffic relating to node repair. It was observed in \cite{RashmiShahGuKuang} that a median of $50$ nodes are unavailable per day and that a median of $180$TB of cross-rack traffic is generated as a result of node unavailability. It was also reported that $98.08\%$ of the cases have exactly one block missing in a stripe. The erasure code that was deployed in this instance was an $[n=14,k=10]$ Reed Solomon (RS) code.   Here $n$ denotes the block length of the code and $k$ the dimension. The conventional repair of an $[n,k]$ RS code is inefficient in that the repair of a single node, calls for contacting $k$ other (helper) nodes and downloading $k$ times the amount of data stored in the failed node, which is clearly inefficient.  Thus there is significant practical interest in the design of erasure-coding techniques that offer both low overhead and which can also be repaired efficiently.

Coding theorists have responded to this need by coming up with two new classes of codes, namely ReGenerating (RG) and Locally Recoverable (LR) codes.  The focus in a RG code is on minimizing the amount of data download needed to repair a failed node, termed the {\em repair bandwidth} while LR codes seek to minimize the number of helper nodes contacted for node repair, termed the {\em repair degree}. In a different direction, coding theorists have also re-examined the problem of node repair in RS codes and have come up with new and more efficient repair techniques.  This survey provides an overview of these recent developments.   An outline of the survey itself appears in Fig.~\ref{fig:chapter_outline}.

RG codes are discussed in Section \ref{sec:regenerating_codes}.  The two principal classes of RG codes, namely Minimum Bandwidth Regenerating (MBR) and Minimum Storage Regeneration (MSR) appear in the two sections that follow.   These two classes of codes are at the two extreme ends of a tradeoff known as the storage-repair bandwidth (S-RB) tradeoff. A discussion on codes that correspond to the interior points of this tradeoff appears in Section~\ref{sec:on-srb}.  The theory of regenerating codes has been extended in several directions and these are explored in Section~\ref{sec:variations}.
Section~\ref{sec:lrc} examines LR codes.  There have been several approaches at extending the theory of LR codes to handle multiple erasures and these are dealt with in Section~\ref{sec:multiple_erasures}.  A class of codes known as Locally ReGenerating (LRG) codes that offer both low repair bandwidth and low repair degree within a single erasure code is discussed in Section~\ref{sec:lrgc}.   This is followed by Section~\ref{sec:rs_repair} that discusses recent advances in the repair of Reed-Solomon codes.   A brief description of a different approach based on capacity considerations and leading to the development of a {\em liquid cloud storage} system appears in Section~\ref{sec:liquid}. The final section, discusses practical evaluations and implementations.

{\em Disclaimer:} This survey is presented from the perspective of the authors and is biased in this respect.  Given the explosion of research activity in this area, the survey also does not claim to be comprehensive and we offer our apologies to the authors whose work has inadvertently or for lack of space, not been appropriately cited. We direct the interested reader to some of the excellent surveys of codes on distributed storage contained in the literature including \cite{DimRamWuSuhSurvey}, \cite{DattaOggSurvey}, \cite{LiLiSurvey} and \cite{liuOggSurvey}.

\begin{figure}[h!]
\centering
\includegraphics[width=6.2in]{chapter_outline.pdf}
\caption{An overview of the different classes of codes for distributed storage discussed in this survey article.} \label{fig:chapter_outline}
\end{figure}

\section{Regenerating Codes{\label{sec:regenerating_codes}}}
\begin{figure}[ht!]
		\begin{center}
			Parameters: $(\ (n,k,d), \ (\alpha, \beta), \ B, \ \mathbb{F}_q \ )$
		\end{center}

		\begin{center}
			\begin{minipage}{3.0in}
				\begin{center}
					\includegraphics[trim= 0in  0in 0in 0in, width=1.8in]{data_collection.pdf}
				\end{center}

			\end{minipage}
			\begin{minipage}{3.0in}
				\begin{center}
					\includegraphics[trim= 0in  0in 0in 0in, width=1.6in]{node_repair.pdf}
				\end{center}
			\end{minipage}
		\end{center}
		\caption{An illustration of the data collection and node repair properties of a regenerating code.} \label{fig:rgc}
\end{figure}

\begin{defn}[\cite{DimGodWuWaiRam}]
	Let \fq\ denote a finite field of size $q$. Then a regenerating (RG) code  \calc\ over \fq\ having integer parameter set $((n,k,d), (\alpha, \beta), B)$ where $1\le k \le n-1$, $k \le d \le n-1$, $\beta \le \alpha$, maps a file $\uu \in \fqB$ on to a collection $\{\uc_i\}_{i=1}^n$ of $n$ $\alpha$-tuples over $\mathbb{F}_q$ using an encoding map
	\bean
	E(\uu) = [\uc_1^T, \uc_2^T, \cdots, \uc_n^T]^T
	\eean
	with the $\alpha$ components of $\uc_i$ stored on the $i$-th node in such a way that the following two properties (see Fig.~\ref{fig:rgc}) are satisfied:
	{\em Data Collection: }The message \uu\ can be uniquely recovered from the contents $\{c_{i_j}\}_{j=1}^k$ of any $k$ nodes.\\
	{\em Node Repair: } If the $f$-th node storing $\uc_f$ fails, then a replacement node can
	\ben
	\item contact any subset $D \subseteq [n] \setminus \{f\}$ of the remaining $(n-1)$ nodes of size $|D| = d$,
	\item map the $\alpha$ contents $\uc_{h}$ of each helper node $h \in D$ on to a collection of $\beta$ repair symbols $\ua_{h,f}^D \in \fqbeta$,
	\item pool together the $d\beta$ repair symbols thus computed to use them to create a replacement vector $\hat{\uc}_f \in \fqalpha$ whose $\alpha$ components are stored in the replacement node, in such a way that the contents of the resultant nodes, with the replacement node replacing the failed node, once again forms a regenerating code. \\
	\een
	\edefn

	A regenerating code is said to be {\em exact-repair} (ER) regenerating code if the contents of the replacement node are exactly same as that of the failed node, ie., $\hat{\uc}_f = \uc_f$. Else the code is said to be {\em functional-repair} (FR) regenerating code. A regenerating code is said to be linear if
	\ben
	\item $E(\uu_1 + \theta \uu_2) = E(\uu_1) + \theta E(\uu_2)$, $\uu_1, \uu_2 \in \fqB, \theta \in \fq$ and
	\item the map mapping the contents $\uc_h$ of the $h$-th helper node on to the corresponding $\beta$ repair symbols $\ua_{h,f}^D$ is linear over \fq.
	\een

	Thus a regenerating code is a code over a vector alphabet \fqalpha\ and the quantity $\alpha$ is termed the {\em sub-packetization level} of the regenerating code. The total number $d\beta$ of \fq\ symbols to be transferred for repair of failure node is called the {\em repair bandwidth} of the regenerating code. The rate of the regenerating code is given by $R = \frac{B}{n\alpha}$. Its reciprocal $\frac{n\alpha}{B}$ is the {\em storage overhead}.

	\subsection{Cut-Set Bound}

	\begin{figure}[ht!]
		\begin{center}
		\includegraphics[trim= 0in  0in 0in 0in, width=4.5in]{cut_set_bound.pdf}
		\end{center}
		\caption{The graph behind the cut-set file size bound.\label{fig:cutsetbound}}
	\end{figure}

	Let us assume that \calc\ is a functional-repair regenerating code having parameter set: $((n,k,d),$ $(\alpha, \beta), B)$. Since an exact-repair regenerating code is also a functional-repair code, this subsumes the case when \calc\ is an exact-repair regenerating code. Over time, nodes will undergo failures and every failed node will be replaced by a replacement node. Let us assume to begin with, that we are only interested in the behavior of the regenerating code over a finite-but-large number $N >> n$ of node repairs. For simplicity, we assume that repair is carried out instantaneously. Then at any given time instant $t$, there are $n$ functioning nodes whose contents taken together comprise a regenerating code. At this time instant, a data collector could connect to $k$ nodes, download all of their contents and decode to recover underlying message vector $\uu$. Thus in all, there are at most $N{n \choose k}$ distinct data collectors which are distinguished based on the particular set of $k$ nodes to which the data collector connects.

	Next, we create a source node that possesses the $B$ message symbols $\{u_i\}_{i=1}^B$, and draw edges connecting the source to the initial set of $n$ nodes. We also draw edges between the $d$ helper nodes that assist a replacement node and the replacement node itself as well as edges connecting each data collector with the corresponding set of $k$ nodes from which the data collector downloads data. All edges are directed in the direction of information flow. We associate a capacity $\beta$ with edges emanating from a helper node to a replacement node and an $\infty$ capacity with all other edges. Each node can only store $\alpha$ symbols over $\fq$. We take this constraint into account using a standard graph-theory construct, in which a node is replaced by $2$ nodes separated by a directed edge (leading towards a data collector) of capacity $\alpha$. We have in this way, arrived at a graph (see Fig.\ref{fig:cutsetbound}) in which there is one source $S$ and at most $N{n \choose k}$ sinks $\{T_i\}$.

	Each sink $T_i$ would like to be able to reconstruct all the $B$ source symbols $\{u_i\}$ from the symbols it receives. This is precisely the multicast setting of network coding. A principal result in network coding tells us that in a multicast setting,  one can transmit messages along the edges of the graph in such a way that each sink $T_i$ is able to reconstruct the source data, provided that the minimum capacity of a cut separating $S$ from $T_i$ is $\ge B$.   A cut separating $S$ from $T_i$ is simply a partition of the nodes of the network into $2$ sets: $A_i$ containing $S$ and $A_i^c$ containing $T_i$. The capacity of the cut is the sum of capacities of the edges leading from a node in $A_i$ to a node in $A_i^c$. A careful examination of the graph will reveal that the minimum capacity $Q$ of a cut separating a sink $T_i$ from source $S$ is given by $
	Q = \sum\limits_{i=0}^{k-1} \min \{\alpha, (d-i)\beta\}
	$
	(Fig.~\ref{fig:cutsetbound} shows an example cut separating source from sink). This leads to the following upper bound on file size \cite{DimGodWuWaiRam}:
	\bea
	\label{eq:cutsetbound}
	B &\le& \sum\limits_{i=0}^{k-1} \min \{\alpha, (d-i)\beta\}.
	\eea
	Network coding also tells us that when only a finite number of regenerations take place, this bound is achievable and furthermore achievable using linear network coding, i.e., using only linear operations at each node in the network when the size $q$ of the finite field \fq\ is sufficiently large.

	In a subsequent result \cite{Wu}, Wu established using the specific structure of the graph, that even in the case when the number of sinks is infinite, the upper bound in \eqref{eq:cutsetbound} continues to be achievable using linear network coding.

	In summary, by drawing upon network coding, we have been able to characterize the maximum file size of a regenerating code given parameters $\{k, d, \alpha, \beta\}$ for the case of functional repair when there is constraint placed on the size $q$ of the finite field $\fq$. Note interestingly, that the upper bound on file size is independent of $n$. Quite possibly, the role played by $n$ is that of determining the smallest value of field size $q$ for which a linear network code can be found having file size $B$ satisfying \eqref{eq:cutsetbound}.
	A functional regenerating code having parameters: $((n, \ k, \ d), \ (\alpha, \ \beta), \ B)$ is said to be optimal provided (a) the file size $B$ achieves the bound in \eqref{eq:cutsetbound} with equality and (b) reducing either $\alpha$ or $\beta$ will cause the bound in \eqref{eq:cutsetbound} to be violated.

	\subsection{Storage-Repair Bandwidth Tradeoff}

	We have thus far, specified code parameters $(k,d) (\alpha, \beta)$ and asked what is the largest possible value of file size $B$. If however, we fix parameters $(n,k,d,B)$ and ask instead what are the smallest values of $(\alpha, \beta)$ for which one can hope to achieve \eqref{eq:cutsetbound}, it turns out, as might be evident from the form of the summands on the RHS of \eqref{eq:cutsetbound}, that there are several pairs $(\alpha, \beta)$ for which equality holds in \eqref{eq:cutsetbound}.  In other words, there are different flavors of optimality.
		\begin{figure}[ht!]
			\bc
			\includegraphics[width=3.5in]{frtradeoff.eps}
			\caption{Storage-repair bandwidth tradeoff. Here, $(n = 60, k = 51, d=58, B = 33660)$.\label{fig:srb_tradeoff}}
			\ec
		\end{figure}
	For a given file size $B$, the storage overhead and normalized repair bandwidth are given respectively by $\frac{n\alpha}{B}$ and $\frac{d\beta}{B}$. Thus $\alpha$ reflects the amount of storage overhead while $\beta$ determines the normalized repair bandwidth. The several pairs $(\alpha, \beta)$ for which equality holds in \eqref{eq:cutsetbound}, represent a tradeoff between storage overhead on the one hand and normalized repair bandwidth on the other as can be seen from the example plot in Fig.~\ref{fig:srb_tradeoff}.  Clearly, the smallest value of $\alpha$ for which the equality can hold in \eqref{eq:cutsetbound} is given by $\alpha = \frac{B}{k}$. Given $\alpha = \frac{B}{k}$, the smallest permissible value of $\beta$ is given by $\beta = \frac{\alpha}{d-k+1}$. This represents the minimum storage regeneration point and codes achieving \eqref{eq:cutsetbound} with $\alpha = \frac{B}{k}$ and $\beta = \frac{\alpha}{d-k+1}$ are known as minimum storage regenerating (MSR) codes.  At the other end of the tradeoff, we have the minimum bandwidth regenerating (MBR) code whose associated $(\alpha, \beta)$ values are given by $\beta = \frac{B}{dk-{k \choose 2}}$, $\alpha = d\beta$.
	\begin{note}
		Since a regenerating code can tolerate $(n-k)$ erasures by the data collection property, it follows that the minimum Hamming weight $d_{\min}$ of a regenerating code must satisfy $d_{\min} \ge (n-k+1)$.  By the Singleton bound, the largest size $M$ of a code of block length $n$ and minimum distance $d_{\min}$ is given by $M \le Q^{n - d_{\min} + 1} \le Q^k$, where $Q$ is the size of alphabet of the code. Since $Q = q^{\alpha}$ in the case of regenerating code, it follows that the size $M$ of a regenerating code must satisfy $M \le q^{k\alpha}$, or equivalently $q^B \le q^{k\alpha}$, i.e., $B \le k\alpha$. But $B=k\alpha$ in the case of an MSR code and it follows that an MSR code is an MDS code over a vector alphabet. Such codes also go by the name MDS array code.
	\end{note}

	From a practical perspective, exact-repair regenerating codes are easier to implement as the contents of the $n$ nodes in operation do not change with time. Partly for this reason and partly for reasons of tractability, with few exceptions, most constructions of regenerating codes belong to the class of exact-repair regenerating codes. Examples of functional-repair regenerating code include the $d=(k+1)$ construction in \cite{ShaRasKumRam_ia} as well as the construction in \cite{HuChenLee_NCcloud}.

	Early constructions of regenerating codes focused on the two extreme points of the storage-repair bandwidth (S-RB) tradeoff, namely the MSR and MBR points. The various constructions of MBR and MSR codes are described in Sections \ref{sec:mbr}, \ref{sec:msr}. Not surprisingly, given the vast amount of data stored, the storage industry places a premium on low storage overhead. In this connection, we note that the maximum rate of an MBR code is given by:
	\bean
	R_{\text{MBR}} = \frac{B}{n\alpha} = \frac{(dk - {k \choose 2})\beta}{n d\beta} = \frac{dk-{k \choose 2}}{nd},
	\eean
	which can be shown to be upper bounded by $R_{\text{MBR}} \le \frac{1}{2}$ and is achieved when $k=d=(n-1)$.  In the case of MSR codes, there is no such limitation and MSR codes can have rates approaching $1$.

	An RG code is said to be a a {\em Help-By-Transfer} (HBT) RG code if repair of a failed node can be accomplished without incurring any computation at a helper node.  If no computation is required at either helper node or at the replacement node, then the code is termed a {\em Repair-by-Transfer} (RBT) RG code. Clearly, an RBT RG code is also an HBT RG code.

\section{MBR Codes\label{sec:mbr}}

\begin{rem}
	If the $B$ message symbols are drawn randomly with uniform distribution from $\mathbb{F}_q^B$, it can be shown that in any regenerating code achieving the cut-set bound, the contents of each node correspond to a random variable that is uniform over $\mathbb{F}_q^{\alpha}$.  In an MBR code, repair is accomplished by downloading a total of just $\alpha$ symbols which clearly, is the minimum possible.  \end{rem}

\begin{rem}
	Let $\mathcal{C}$ be an MBR code. If $\mathcal{C}$ has the RBT property, it trivially follows that all scalar code-symbols of $\mathcal{C}$ are replicated at least twice. In \cite{KrishKumMBRRep16}, it is shown that for an MBR code it is not possible to have even a single scalar code-symbol replicated more than twice.  Thus the RBT property implies that the collection of $n\alpha$ scalar code-symbols associated with a codeword represent a set of $\frac{n\alpha}{2}$ distinct code symbols, each repeated twice.  The converse is not true in general. However when $d=(n-1)$, it can be shown that the two properties are equivalent.
\end{rem}
\begin{rem}
	In \cite{ShahHBTNonexistence13}, it is shown that for $d<(n-1)$, it is not possible to construct an MBR code that has the HBT property.
\end{rem}

\subsection{Polygonal MBR Codes}

\begin{figure}[ht!]
	\bc
	\includegraphics[width=2.2in]{fig_rbt_mbr_v3.pdf}
	\caption{An example RBT MBR code for the parameters $n=5, k=3, d=4$. Here file size is $9$.  }
	\label{fig:pentagon_code}
	\ec
\end{figure}
In the following, we describe with the help of an example, one of the first explicit families of MBR codes \cite{RasShaKumRam_allerton09}. We term these codes as {\it polygonal MBR codes}. The construction holds for parameters $k\leq d=n-1,\beta=1$ and the constructed MBR codes possess the RBT property.
\begin{eg}
	Consider the parameters $n=5,k=3,d=4$ and $\beta=1$. Thus $B=kd\beta-{k\choose 2}\beta=9$. First construct a complete graph with $n=5$ vertices and $N={5\choose 2}=10$ edges. The nine message symbols are then encoded using a $[10,9]$ MDS code to produce ten code-symbols. Each code-symbol is then uniquely assigned an edge. Each node of the MBR code stores the code-symbols corresponding to the edges incident on that node (see Fig. \ref{fig:pentagon_code}). The data collection property follows as any collection of $k=3$ nodes yields nine distinct (MDS) code-symbols. If a node fails, the replacement node can download from each of the remaining four nodes, the code-symbol corresponding to the edge it shares with the failed node. Hence repair is accomplished by merely transferring the data without any computation (RBT).
\end{eg}

\begin{rem}
	For the general construction, in order to construct an $[n,k,d=n-1],\beta=1$ MBR code, one first forms the complete graph on $n$ vertices. Each edge is then mapped to a code-symbol of an $[N,B]$ MDS code, where $N={n\choose 2}$ and $B$ is the file size parameter. An $O(n^2)$ field-size requirement is thus imposed by the underlying scalar MDS code.
\end{rem}
\subsection{Product-Matrix (PM) MBR codes}
A second, general construction for MBR codes is the PM construction~\cite{RasShaKum_pm11} which derives its name from the fact that the contents of $n$ nodes can be expressed in the form of a product of two matrices.  The two matrices are respectively an encoding matrix and a second, message matrix containing the message symbols.  This construction yields MBR codes for all feasible parameters $k\leq d\leq n-1$, $\beta=1$, with an $O(n)$ field-size requirement.   The $(n\times d)$ encoding matrix $\psi$ is of the form: $\psi\  = \left[ \begin{array}{cc}
\phi & \Delta
\end{array} \right]$, where $\phi$, $\Delta$ are $(n \times k)$, $(n \times (d-k))$ matrices respectively. Let the $i$-th row of $\psi$ be denoted by $\psi_i^T$. The sub-matrices $\phi$ and $\Delta$ are here chosen such that any $d$ rows of $\psi$ and any $k$ rows of $\phi$ are linearly independent. The $(d\times d)$ symmetric message matrix $M$ is derived from the $B=kd-{k\choose 2}$ message symbols as follows:
\bean
M\  = \left[ \begin{array}{cc}
	S & V \\
	V^T & 0
\end{array} \right], \ \ \text{where $S$ is a symmetric $(k\times k)$ matrix and $V$ a $(k \times (d-k))$ matrix.}
\eean
The $i$-th node, under the PM-MBR construction, stores the matrix product $\psi_i^TM$.  The repair data passed on by helper node $j$ to replacement node $i$ is given by $\psi_j^TM\psi_i$.

\subsection{Other Work}

In \cite{LinChungNovelRBTMBR14}, the authors introduce a family of RBT MBR codes for $d=n-1$, that are constructed based on a congruent transformation applied to a skew-symmetric matrix of message symbols. In comparison with the $O(n^2)$ field requirement of polygonal MBR codes, in this construction, a field-size of $O(n)$ suffices.

In \cite{HanPaiZhengVarshUpdateEfficientPM15}, the authors stay within the PM framework, but provide a different set of encoding matrices for MSR and MBR codes that have least-possible update complexity within the PM framework. The authors of \cite{HanPaiZhengVarshUpdateEfficientPM15} also analyze the codes for their ability to correct errors and provide corresponding decoding algorithms.   The paper \cite{ShahHBTNonexistence13} proves the non-existence of HBT MBR codes with $d<(n-1)$.  The paper also provides PM-based constructions for two relaxations, namely (i) any failed node which is a part of a collection of systematic nodes can be recovered in HBT fashion from any $d$ other nodes  and (ii) for every failed node, there exists a corresponding set of $d$ helper nodes which permit HBT repair. The paper \cite{KrishKumMBRRep16} provides binary MBR constructions for the parameters $(k=d=n-2)$, $(k+1=d=n-2)$ and studies the existence of MBR codes with inherent double replication, for all parameters. In \cite{Raviv2AsymptOptAnyFieldMSRMBR17}, the authors provide regenerating-code constructions that asymptotically achieve the MSR or MBR point as $k$ increases and these codes can be constructed over any field, provided the file size is large enough. In \cite{MahdKhisMohajBWAdaptiveMBR17}, the authors introduce some extensions to the classical MBR framework by permitting the presence of a certain number of error-prone nodes during repair/reconstruction and by introducing flexibility in choosing the parameter $d$ during node repair.

\begin{open}
	Determine the smallest possible field size $q$ of an MBR code for given $\{(n,k,d), (\alpha,\beta)\}$.
\end{open}

\section{MSR Codes\label{sec:msr}}
Among the class of RG codes, MSR codes have received the greatest attention, and the reasons include: the fact that (a) the storage overhead of an MSR code can be made as small as desired, (b)  MSR codes are MDS codes and (c) MSR codes have been challenging to construct.
\subsection{Introduction\label{sec:intro_msr}}
As noted previously, an MSR code with parameters $(n,k,d, \alpha)$ has file size $B = k\alpha$ and $\beta = \frac{\alpha}{d-k+1}$. Although MSR codes are vector MDS codes that have optimum repair-bandwidth of $d\beta$ for the repair of any node among the $n$ nodes, there are papers in the literature that refer to a code as an MSR code even if optimal repair holds only for the systematic nodes. In the current paper, we refer to such codes as {\em systematic} MSR codes. While only $\beta$ symbols are sent by each of the $d$ helper nodes, the number of symbols accessed by the helper node in order to generate these $\beta$ symbols could be $> \beta$. The class of MSR codes that access at each helper node, only as many symbols as are transferred, are termed {\em optimal-access} MSR codes. MSR codes that alter a minimum number of parity symbols while updating a single, systematic symbol, are called {\em update-optimal} MSR codes.

There are several exact-repair (ER) MSR constructions available in the literature. In \cite{ShaRasKumRam_ia}, Shah et al. show that {\em interference alignment} (IA) is necessarily present in every exact-repair MSR code, and use IA techniques to construct systematic MSR codes, known as MISER codes, for $d=n-1 \ge 2k-1$. The IA condition in the context of MSR codes (observed earlier in \cite{WuDim}) demands that the interference components in the data passed by helper nodes must be aligned so that they can be cancelled at the replacement node by data received from the systematic helper nodes. In \cite{SuhRam}, Suh et al. build on \cite{ShaRasKumRam_ia} to construct MSR codes for $d \ge 2k-1$ with optimal repair bandwidth for all nodes, under the condition that the helper-node set necessarily includes systematic nodes. In \cite{RasShaKum_pm}, the well-known Product Matrix (PM) framework is introduced to provide MSR constructions for $d \geq 2k-1$, thereby settling the problem of MSR code construction in the low-rate regime, $k/n \leq 0.5$. While the method adopted in \cite{RasShaKum_pm} to provide a construction for $d > 2k-1$ is to suitably shorten a code for $d=2k-1$, an extension of the PM framework that yields constructions for any $d \geq 2k-1$ in a single step is provided in \cite{LinChungHanAl}. Apart from a few notable constructions such as the Hadamard-design-based code \cite{PapDimCad} for $(k+2,k)$ and its generalization for $(n-k) >2$ for systematic node-repair, the problem of high-rate constructions (i.e., $k/n \geq 0.5$) for all-node repair remained open. The first major result in this direction, is due to Cadambe et al. \cite{CadJafMalRamSuh} where the authors apply the notion of {\em symbol extension in interference alignment} where multiple symbols are grouped together to form a single vector symbol, to jointly achieve interference alignment.  The symbol-extension viewpoint is then used to show that ER MSR codes exist for all $(n,k,d)$, as $B$ goes to infinity. The second major development was the zigzag code construction \cite{TamWanBru,WangTamoBruck}, the first non-asymptotic high-rate MSR code construction with $d=(n-1)$ permitting rates as close as $1$ as desired, with additional desirable properties such as optimal access and optimal update.  Zigzag codes however, require a sub-packetization level ($\alpha$) that grows  exponentially with $k$ and a very large finite field size, while the earlier PM codes for the low-rate regime, have $\alpha = (k+1)$ and field-size that is linear in $n$. In a subsequent work~\cite{CadHuaLiMeh}, the authors present a systematic MSR construction having $\alpha = \frac{k^2}{4}$ and rate $R = 2/3$.  A second systematic MSR code with $\alpha = r^{\frac{k}{r+1}}$ is presented in \cite{WanTamBru_long}. A lower bound on sub-packetization level $\alpha$ of a general MSR code is derived in \cite{TamWanBru_access_tit}.  The same paper shows that $\alpha \geq r^{\frac{k-1}{r}}$ in the case of an optimal-access MSR code.  An improved lower bound for general MSR codes

\bea
2\log_2 \alpha (\log_{\left(\frac{r}{r-1}\right)} \alpha +1) + 1 & \geq & k,
\eea
appears in \cite{GopTamCal}. These developments made it clear that the ultimate goal in MSR code construction was to construct a high-rate MSR code that simultaneously had low sub-packetization level $\alpha$, low field-size $q$, arbitrary repair degree $d$ and the optimal-access property.

In \cite{SasAgaKum}, a parity-check viewpoint is adopted to construct a high-rate MSR code for $d=n-1$ with a sub-packetization level $r^{\frac{n}{r}}$, requiring however, a large field-size. The construction was extended in \cite{RawKoyVis_msr}, to $d$ satisfying $k \leq d \leq n-1$.  In \cite{GopFazVar}, the authors provide a construction of MSR codes that holds for all $k \leq d \leq n-1$, but which once again required large field size. In  \cite{AgaSasKum}, the authors provide a construction for an optimal-access systematic MSR code that holds for any parameter set $(n,k,d=n-1)$ having sub-packetization $\alpha$ matching the lower bound given in \cite{TamWanBru_access_tit}. In \cite{TamWanBru, WangTamoBruck, WanTamBru_long, CadHuaLiMeh, SasAgaKum,AgaSasKum, RawKoyVis_msr, GopFazVar}, Combinatorial Nullstellansatz (see \cite{Alon_Comb}) is used to prove the MDS property due to which the codes are non-explicit and have large field sizes.

In \cite{RavSilEtz}, an explicit optimal-access, systematic MSR code is constructed with optimal $\alpha$, but for limited values of $n-k=2, 3$. In \cite{YeBar_1}, the authors present two different classes of explicit MSR constructions, one of which possessed the optimal-access property. Both constructions are for any $(n,k,d)$ with
sub-packetization level growing exponential in $n$.

In a major advance, in \cite{YeBar_2}, Ye and Barg present an explicit construction of a high-rate, optimal-access MSR code with $\alpha = r^{\lceil \frac{n}{r} \rceil}$, field size no larger than $r\lceil \frac{n}{r} \rceil$, and $d=(n-1)$. Essentially the same construction was independently rediscovered in \cite{SasVajKum_arxiv} from a different coupled-layer perspective, where layers of an arbitrary MDS codes are coupled by a simple pairwise coupling transform to yield an MSR code.  Just prior to the appearance of these two papers, in an earlier version of \cite{LiTangTian}, the authors show how a systematic MSR code can be converted into an MSR code by increasing the sub-packetization level by a factor of $r=(n-k)$ using  a pairwise symbol transformation. This result is then extended in \cite{LiTangTian}, to present a technique that takes an MDS code, increases sub-packetization level by a factor of $r$ and converts it into a code in which the optimal repair of $r$ nodes can be carried out. By applying this transform repeatedly $\lceil\frac{n}{r}\rceil$ times, it is shown that any scalar MDS code can be transformed into an MSR code.  It turns out that the three papers \cite{YeBar_2,SasVajKum_arxiv,LiTangTian}, either explicitly or implicitly, employed as a key part of the construction, essentially the same pairwise-coupling transform.

Let $s=(d-k+1)$.  More recently, the lower bound $\alpha \geq s^{\frac{n}{s}}$ was derived in \cite{BalKum_subpkt} for optimal-access MSR codes.  The same paper also shows that the sub-packetization level of an MDS code that can optimally repair any $w$ of the $n$ nodes must satisfy $\alpha \ge s^{\lceil\frac{w}{s}\rceil}$.  These results established that the earlier constructions in \cite{SasAgaKum, RawKoyVis_msr, YeBar_2, SasVajKum_arxiv,LiTangTian, VajBalKum} were optimal in terms of sub-packetization level $\alpha$.    It is also shown in \cite{BalKum_subpkt}, that a vector MDS code that can repair failed nodes belonging to a fixed set of $Q$ nodes with minimum repair bandwidth and in optimal-access fashion, and having minimum sub-packetization level $\alpha = s^{\frac{n}{s}}$ must necessarily have a coupled-layer structure, similar to that found in \cite{YeBar_2,SasVajKum_arxiv,LiTangTian}.

An explicit construction of MSR codes for $d < (n-1)$ with $\alpha$ achieving the lower bound $\alpha \geq s^{\frac{n}{s}}$
for $s =2,3,4$ was recently provided in \cite{VajBalKum}.

\begin{open}Derive a tight lower bound on the sub-packetization level of MSR codes and provide matching constructions.
\end{open}
\begin{open}Constructions for explicit optimal-access MSR codes for any $(n,k,d)$ with optimal sub-packetization.
\end{open}

\begin{table}[ht!]
	\caption{A list of MSR constructions and the parameters. In the table $r=n-k$, $s=d-k+1$ and when All Node Repair is No, the constructions are systematic MSR. By `non-explicit' field-size, we mean that the order of the size of the field from which coefficients are picked is not given explicitly. }
	\bean
	\scalebox{0.85}{$
		\begin{array}{||l|c|c|c|c|c|c||}
		\hline \hline
		\text{MSR Code} &  \text{Parameters} & \alpha & \text{Field Size} & \text{All Node} & \text{Optimal} & \text{Notes}\\
		&&&& \text{Repair}& \text{ Access} &\\ \hline
		\text{\cite{ShaRasKumRam_ia} Shah et al.} & (n,k,d=n-1\ge 2k-1) & r & 2r & \text{No} & \text{Yes} & \text{IA framework}\\ \hline
		\text{\cite{SuhRam} Suh et al.} & (n, k, d \ge 2k-1) & s & 2r & \text{Yes} & \text{No} & \text{IA framework}\\
		& (n, k \le 3, d) & & & & &\\ \hline
		\text{\cite{RasShaKum_pm} Rashmi et al.}  & (n \ge 2k-1, k, d) & r & n & \text{Yes} & \text{No} & \text{Product Matrix framework}\\  \hline

		\text{\cite{PapDimCad} Papailiopoulos et al.} & (n,k,d=n-1)& r^k & \text{non-explicit} &\text{No} &  \text{No} & {\text{High rate systematic MSR}}\\ \hline
		\text{\cite{TamWanBru} Tamo et al. }  & (n,k,d=n-1)  & r^{k+1} & \leq 4 \text{ when } r \leq 3, & \text{Yes} & \text{Yes} & \text{High rate MSR}\\
		\text{\cite{WangTamoBruck} Wang et al.} & & &\text{else non-explicit} & & & \text{known as Zigzag codes}\\
		\hline
		\text{\cite{CadHuaLiMeh} Cadambe et al.}& (n\ge \frac{3k}{2}, k, d=n-1) & O(k^2)& \text{non-explicit} & \text{No} & \text{Yes} & \\ \hline
		&  &  & & & &\text{Introduced Parity-check }\\
		\text{\cite{SasAgaKum} Sasidharan et al.} & (n, k, d=n-1) & r^{\left\lceil\frac{n}{r}\right\rceil} & O(n^r)& \text{Yes}& \text{Yes} & \text{viewpoint, Optimal $\alpha$}\\ \hline

		\text{\cite{GopFazVar} Goparaju et al.} & (n,k,d) & s^{k {r \choose s}} & \text{-} & \text{No} & \text{Yes}  & \text{Very large field-size needed.} \\
		& &  & & &  & \text{See Sec. IV in \cite{GopFazVar} for details.} \\ \hline
		\text{\cite{RawKoyVis_msr} Rawat et al.} & (n, k, d) & s^{\left\lceil\frac{n}{s}\right\rceil} & O(n^r) & \text{Yes}& \text{Yes} & \text{ Extended \cite{SasAgaKum} for $d<n-1$}\\ \hline
		\text{\cite{YeBar_1} Ye et al.} & (n,k,d) & s^n & sn & \text{Yes} & \text{No} & \\
		& (n,k,d) & s^{n-1} & n+1 & \text{Yes} & \text{Yes} &\\ \hline
		\text{\cite{YeBar_2} Ye et al.} & & & & & &\\
		\text{\cite{SasVajKum_arxiv} Sasidharan et al.} & (n, k, d=n-1)& r^{\left\lceil\frac{n}{r}\right\rceil} & r\lceil\frac{n}{r}\rceil & \text{Yes} & \text{Yes} & \text{Optimal } \alpha\\
		\text{\cite{LiTangTian} Li et al.} & &  & & & & \text{for optimal-access MSR}\\ \hline
		\text{\cite{VajBalKum} Vajha et al.} & (n,k,d) &  & & & & \\
		& d \in \{k+1, k+2, k+3\} & s^{\left\lceil \frac{n}{s} \right\rceil} & O(n) & \text{Yes} &\text{Yes}&\\ \hline
		\hline \hline
		\end{array}
		$}
	\eean
\end{table}

\subsection{Constructions of MSR Codes}
\paragraph{Product Matrix Construction \cite{RasShaKum_pm}:} We provide a brief description of the PM construction for parameter set $(n, k, d=2k-2), (\alpha=k-1, \beta = 1, B=k(k-1))$. The message symbols $\{u_i\}_{i=1}^B$ are arranged in the form of a $(d \times \alpha)$ matrix $M$: $M = \left[ \begin{array}{cc}
S_1 & S_2
\end{array}\right]^T$,
where the $S_1, S_2$ are symmetric $(k-1) \times (k-1)$ matrices containing the $B=k(k-1)$ message symbols.

Encoding is carried out using a $(n \times d)$ matrix  $\Psi = [\begin{array}{cc}
\Phi & \Lambda \Phi \end{array}]$, where $\Phi$ is an $n \times (k-1)$ matrix and $\Lambda$ is a diagonal matrix. Let the $i$-th row of $\Psi$  be $\psi_i^T$, the $i$-th row of $\Phi$ be $\phi_i^T$ and the $i$-th diagonal element in $\Lambda$ be $\lambda_i$. The $\alpha$ symbols stored in node $i$ are given by: $\uc_i^T = \psi_i^T M = \phi_i^T S_1 + \lambda_i \phi_i^T S_2.$\\
The matrix $\Psi$ is required to satisfy the properties: 1) any $d$ rows of $\Psi$ are linearly independent, 2) any $\alpha$ rows of $\Phi$ are linearly independent and 3) the $n$ diagonal elements of $\Lambda$ are distinct.

\underline{Node Repair:} Let $f$ be the index of failed node, thus the aim is to reconstruct $\uc_f$.  The $i$-th helper node, $h_i$, $i \in [d]$, passes on the information: $\uc_{h_i}^T \phi_f = \psi_{h_i}^T M \phi_f$.  Upon aggregating the repair information we obtain the vector,
\bean
\left[\begin{array}{cccc}
	\psi_{h_1} & \psi_{h_2} & \cdots & \psi_{h_d}
\end{array}\right]^T
\left[M \phi_f \right].
\eean
As any $d$-rows of $\Psi$ are linearly independent, the vector $M\phi_f$ can be recovered.  From $M\phi_f$, we can obtain $S_1 \phi_f$ and $S_2\phi_f$.  Since $S_1$ and $S_2$ are symmetric, we can recover the contents $\uc_f^T = \phi_f^T S_1 + \lambda_f \phi_f^T S_2$ of the replacement node.

\underline{Data Collection:} Let $\Psi_{\text{DC}} = [\begin{array}{cc} \Phi_{\text{DC}} & \Lambda_{\text{DC}} \Phi_{\text{DC}} \end{array}]$ be the $(k \times d)$ sub matrix of $\Psi$ corresponding to the $k$ nodes contacted for data collection. We wish to retrieve $M$ from $\Psi_{\text{DC}} M = \Phi_{\text{DC}} S_1 + \Lambda_{DC} \Phi_{\text{DC}} S_2$. This can be done in three steps:
\ben
\item First compute $\Psi_{\text{DC}} M \Phi_{\text{DC}}^T =\Phi_{\text{DC}} S_1 \Phi_{\text{DC}}^T + \Lambda_{DC} \Phi_{\text{DC}} S_2 \Phi_{\text{DC}}^T $ and set $P = \Phi_{\text{DC}} S_1 \Phi_{\text{DC}}^T$, $Q = \Phi_{\text{DC}} S_2 \Phi_{\text{DC}}^T$.
\item It is clear that $P, Q$ are symmetric. Thus we know both $P_{ij} + \lambda_{i} Q_{ij}$ and $P_{ij} + \lambda_{j} Q_{ij}$. Since $\lambda_i \ne \lambda_j$ for $i \ne j$, we can recover $P_{ij}$ and $Q_{ij}$ for all $i \ne j$.
\noindent \item Since we know $P_{ij}$ for $j \neq i$, we can compute the vector $\phi_i^T S_1 [\phi_1, \cdots, \phi_{i-1}, \phi_{i+1}, \cdots, \phi_{k}]$.  Since any $\alpha$ rows of $\Phi$ are linearly independent, we can recover $\{\phi_i^T S_1 | 1 \le i \le k \}$.  For any set of $\alpha$ distinct elements $\phi_i^T$, we can compute
$\left[ \begin{array}{ccc}
\phi_1 & \cdots & \phi_{\alpha}
\end{array}\right]^T S_1$,
from which $S_1$ can be recovered. $S_2$ can be similarly recovered from $Q$. The present description assumes data collection from the first $k$ nodes, while a similar argument holds true for any arbitrary set of $k$ nodes.
\een

\paragraph{Coupled Layer Code:\label{par:clay} } We present here the constructions in \cite{YeBar_2,SasVajKum_arxiv,LiTangTian} from a coupled-layer perspective.  We explain the construction here
only for parameter sets of the form:
\bean
(n=st,\ k=s(t-1),\ d=n-1), (\alpha=s^t,\ \beta=s^{t-1}), q \ge n,
\eean
where $s \ge 1, t \ge 2$.  (The construction can however, be extended to yield MSR codes for any $(n,k,d=n-1)$ using a technique called shortening). The coupled-layer code can be constructed in two steps: (a) in the first step, we layer $\alpha$, $(n,k)$ MDS codewords to form an uncoupled data-cube, (b) in the second step, the symbols within the uncoupled-data cube are transformed using a pairwise-forward-transform (PFT) to obtain the coupled layer code.  While we discuss only the case when the MDS code employed in the layers is a scalar MDS code, there is a straightforward extension that permits the use of vector MDS codes (see \cite{SasVajKum_arxiv}).

Let us first consider the $n \alpha$ symbols $\{U(x,y,\uz) \ | \ (x,y) \in \Zs \times \Zt, \uz \in \Zst \}$  of an uncoupled code $\calu$ where each code symbol $U(x,y,\cdot)$ is a vector of $\alpha$ symbols in $\fq$. These $n\alpha$ symbols can be organized to form a three-dimensional (3D) data cube (see Fig.\ref{fig:datacube_uncoupled}), where $(x,y) \in \Zs \times \Zt$ is the node index and where $\uz \in \Zst$ serves to index the contents of a node.  For fixed $\uz \in \Zst$, we think of the symbols $\{U(x,y,\uz) \ | \ (x,y) \in \Zs \times \Zt\}$ as forming a plane or a layer and thus the value of $\uz$ may be regarded as identifying a plane or layer. The symbols in each layer of the uncoupled data cube form an $(n,k)$ MDS code.

\begin{figure}[!ht]
	\centering
	\begin{minipage}[c]{0.3\textwidth}
		\centering
		\includegraphics[width=2.2in]{datacube_uncoupled.pdf}
	\end{minipage}
	\hspace{0.05\textwidth}
	\begin{minipage}[c]{0.6\textwidth}
		\centering
		\includegraphics[width=2.2in]{uncoupled_coupled_datacube.pdf}
	\end{minipage}\\[3mm]
	\begin{minipage}[t]{0.3\textwidth}
		\centering
		\caption{Uncoupled data cube for $s=2$, $t=3$. The red dots represent plane-index $\uz$.}
		\label{fig:datacube_uncoupled}
	\end{minipage}
	\hspace{0.05\textwidth}
	\begin{minipage}[t]{0.6\textwidth}
		\centering
		\caption{Paired symbols are shown using yellow rectangles connected by dotted lines. Uncoupled symbols are transformed using PFT to get the coupled symbols in the coupled data cube.}
		\label{fig:datacube_ucoupled_pairs}
	\end{minipage}
\end{figure}

Let, $\Theta$ be the $\left( (n-k) \times n \right)$ parity check (p-c) matrix of an arbitrarily chosen $(n,k)$ scalar MDS code defined over $\fq$. Let $\theta_{x,y}(\ell)$ denote the element of $\Theta$ lying in the $\ell$th row, and $(x,y)$th column. Then the symbols of the uncoupled code satisfy the p-c equations:
\bea
\label{eq:uncoupled_code}
\sum\limits_{(x,y) \in \Zs \times \Zt} \theta_{x,y}(\ell) U(x,y;\uz) &=& 0, \ \ \forall \ell \in [0, n-k-1], \ \forall \uz \in \Zst.
\eea

Next, consider an identical data-cube (see Fig.~\ref{fig:datacube_ucoupled_pairs}) containing the $n\alpha$ symbols
\bean
\{C(x,y,\uz) \ | \ (x,y) \in \Zs \times \Zt, \uz \in \Zst \}
\eean corresponding to the coupled-layer code. This data-cube will be referred to as the coupled data cube.  The symbols of the coupled data cube are derived from the symbols of the uncoupled data cube as follows.
Let $\gamma$ be an element in $\fq \setminus \{0\}$, $\gamma^2 \ne 1$.   Let us define $\uz(y,x) = (z_0, \cdots, z_{y-1}, x, z_{y+1}, \cdots, z_{t-1})$. Each symbol $C(x,y,\uz)$ which is such that $z_y \ne x$ is paired with a symbol $C(z_y,y,\uz(y,x))$.  The values of the symbols so paired, are derived from those of their counterparts in the uncoupled data cube as per the $(2 \times 2)$ linear transformation given below, termed as the PFT:
\bea
\label{eq:pft}
\left[ \begin{array}{c}
	C(x,y,\uz)\\
	C(z_y,y,\uz(y,x))
\end{array} \right] = \left[\begin{array}{cc}
1 & \gamma\\
\gamma & 1
\end{array}\right]^{-1} \left[\begin{array}{c}
U(x,y,\uz)\\
U(z_y,y,\uz(y,x))
\end{array}\right]. \eea
In the case of the symbols $C(x,y,\uz)$ when $z_y=x$, the relation between symbols in the two data cubes is even simpler and given by: $C(x,y,\uz) = U(x,y,\uz)$. The pairwise reverse transform (PRT) is simply the inverse of the PFT and is used to obtain the uncoupled symbols $U(\cdot)$ from the coupled symbols $C(\cdot)$.

The p-c equations satisfied by the coupled-layer code can be derived using the p-c equations \eqref{eq:uncoupled_code} satisfied by the symbols in the uncoupled data cube and the PRT :
\bea
\scalebox{0.9}{$
\label{eq:coupled_code}
\sum\limits_{(x,y) \in \Zs \times \Zt} \theta_{x,y}(\ell) C(x,y,\uz) + \sum\limits_{y \in \Zt} \sum\limits_{x \ne z_y} \gamma \theta_{x,y}(\ell) C(z_y,y,\uz(y,x)) = 0, \ \ \forall \uz \in \Zst, \ \ell \in [0,n-k-1].$}
\eea
\underline{Node Repair:} Let $(x_0,y_0)$ be the failed node. To recover the symbols $\{C(x_0, y_0, \uz) \ | \  \uz \in \Zst \}$, each of the remaining nodes $(x,y) \ne (x_0, y_0)$ sends helper information:
$\{C(x,y, \uz) \ | \ \uz \in \Zst,\ z_{y_0} = x_0 \}$.  Focusing on \eqref{eq:coupled_code} for $\uz$ such that $z_{y_0} = x_0$ and retaining on the left side the unknown symbols, leads to equations of the form:
\bea
\label{eq:repaireqns}
\theta_{x_0, y_0}(\ell) C(x_0, y_0, \uz) + \sum\limits_{x \ne x_0} \gamma \theta_{x,y_0}(\ell) C(x_0,y_0,\uz(y_0, x)) &=& \kappa^*, \ \ \forall \ell \in [0, n-k-1],
\eea
where $\kappa^*$ is a known value.  These equations can be solved for the contents of the replacement node.

\underline{Data Collection:} Please refer to \cite{SasVajKum_arxiv} for the proof of data collection property.

\paragraph{Ye-Barg Codes \cite{YeBar_1}:}

In \cite{YeBar_1} the authors present two constructions, for non optimal-access MSR and optimal-access MSR codes respectively. These are the only known MSR constructions that are explicit and yield MSR codes for any parameter set $(n,k,d)$. The same codes are also optimal for the repair of multiple nodes. We describe here, for simplicity, the construction of $(n,k,d)$ MSR codes having parameters: $(n, k, d), (\alpha=s^n, \beta=s^{n-1}), q \ge sn $ where $s=d-k+1$, defined over finite field \fq\ for $s \ge 1$. Let $\{C(i,\uz) \ | \ i \in [n], \uz \in \Zsn \}$ be the collection of $n\alpha$ symbols of a codeword, where $i$ is the node index and $\uz$ is the scalar symbol index. The code is defined via the p-c equations given below:
\bea
\label{eq:yebarg_parity}
\sum\limits_{i \in [n]} \lambda_{i, z_i}^{\ell} C(i; \uz) &=& 0, \ \ \forall \uz \in \Zsn, \ \ell \in [0, n-k-1],
\eea
where the $\{ \lambda_{i,j}, i \in [n], j \in [0,s-1]\}$ are all distinct, thereby requiring a field size $q \ge sn$.

\underline{Node Repair:} Let $f$ be the failed node, $D$ be the set of $d$ helper nodes. The helper information sent by a node $i \in D$ is given by: $\{ \mu_f^i(\uz)=\sum\limits_{j=0}^{s-1} C(i, \uz(f,j)) \ | \ \uz \in \Zsn, z_f = 0 \}$.  Next, fixing $z_i, \ \forall i \in [n] \setminus \{f\}$ and summing equations \eqref{eq:yebarg_parity} over the values of $z_f$, we get:

\bea
\label{eq:yebarg_repair1}
\sum\limits_{z_f=0}^{s-1} \lambda_{f,z_f}^{\ell} C(f, \uz) + \sum\limits_{i \in [n] \setminus \{f\} } \lambda_{i,z_i}^{\ell} \mu_f^i(\uz) &=& 0, \ \ \forall \ell \in [0,n-k-1].
\eea

It can be shown that the collection of symbols $\{\mu_f^i(\uz) | i \in [n] \setminus \{f\} \}$ form an $[n-1, d]$ MDS code. Therefore, all the $\mu_f^{i}(\uz)$ can be computed from the known $d$ values supplied by  the helper nodes and

the symbols $\{C(f,\uz) \ | \ \uz \in \Zsn\}$ can thus be recovered from \eqref{eq:yebarg_repair1}.

\underline{Data Collection:} For every $\uz \in \Zsn$, the collection $\{C(i,\uz) | i \in [n]\}$ forms an $(n,k)$ MDS code. Therefore, any $(n-k)$ erased symbols can be recovered.\\

{\bf Multiple Node Repair} Let $1\le t \le n-k$ be the number of erasures to be recovered. It was shown in \cite{CadJafMalRamSuh} that the minimum repair bandwidth required to repair $t$ erasures in an MDS code having sub-packetization level $\alpha$ is lower bounded by $\gamma_t \ge \frac{t(n-t)\alpha}{n-k}$. Given that $ k \le d \le n-t$ is the number of helper nodes that need to be contacted during the repair of $t$ nodes, $\gamma_t$ is lower bounded by: $\gamma_t \ge \frac{td\alpha}{d+t-k}$. The Ye-Barg code presented above achieves this bound~\cite{YeBar_1}. The $t$ node repair discussed here assumes a centralized repair setting whereas an alternate, cooperative repair approach is discussed in Section \ref{subsec:coop_rep}. \\

{\bf Adaptive Repair} Adaptive-repair $(n,k)$ MSR codes are MSR codes that can repair a failed node by connecting to any $d$ nodes, for any $d \in [k, n-1]$ and can reconstruct the failed node by downloading $\frac{\alpha}{d-k+1}$ symbols each from the $d$ helper nodes. Constructions of MSR codes with adaptive repair can be found in \cite{GopFazVar, YeBar_1, MahMohKhis_MSRAdapt}.

\section{On the Storage-Repair Bandwidth Tradeoff under Exact Repair \label{sec:on-srb}}

We distinguish between the S-RB tradeoffs for exact and functional-repair RG code, by referring to them as the ER and FR tradeoff respectively. The file size $B$ under exact repair cannot exceed that in the FR case since ER may be regarded as a trivial instance of FR.  However, unlike in the case of functional-repair codes, the data collection problem in the exact-repair setting, cannot be identified with a multicast problem simply because each replacement node for a failed node acts as a sink for a different set of data.     Thus it is not clear that the cut-set bound for FR can be achieved under ER, leaving the door open for an S-RB tradeoff in the case of ER that lies strictly above and to the right of the FR tradeoff in the $(\alpha, \beta)$-plane.  There do exist constructions of exact-repair MBR and MSR codes meeting the cut-set bound with equality, showing that the ER tradeoff coincides with the FR tradeoff at the extreme MSR and MBR points.

\subsection{The Non-existence of ER Codes Achieving FR tradeoff\label{sec:non-exist}}

The first major result on the ER tradeoff was the result in \cite{ShaRasKumRam_rbt}, showing that apart from the MBR point and a small region adjacent to the MSR point, there do not exist ER codes whose $(\alpha, \beta)$ values lie on the interior point of the FR tradeoff.  We set $\alpha_{\text{\tiny MSR}} = \beta(d-k+1)$ to be the value of $\alpha$ at the MSR point.
\bthm \label{thm:shah_non_exist} For any given values of $(n,k \geq 3,d)$, ER codes having parameters $(\alpha, \beta, B)$ corresponding to an interior point on the FR tradeoff do not exist, except possibly for $\alpha$ in the range
\bea \label{eq:exception}
\alpha_{\text{\tiny MSR}} & \leq \ \alpha \ \leq & \alpha_{\text{\tiny MSR}}
\left( 1 + \frac{1}{   \alpha_{\text{\tiny MSR}} (\alpha_{\text{\tiny MSR}}+1)     }\right) ,

\eea
corresponding to a small region in the neighborhood of the MSR point.
\ethm

\begin{figure}[ht!]
	\centering
	\includegraphics[width=2.5in]{repair_matrix_2.pdf}
	\caption{The repair matrix \label{fig:repmatrix}}
\end{figure}

\bpf (Sketch) By restricting attention to any $(d+1)$ symbols of an RG code having parameter set $(n,k,d, (\alpha, \beta), B)$ one obtains a second RG code with parameter set $((d+1),k,d, (\alpha, \beta), B)$ in which all the remaining nodes participate in the repair of a failed node.  This simplifies the analysis of the repair setting and with this in mind, in the proof, we set $n=(d+1)$.

When the message vector $\underline{u}$ is picked uniformly at random, we have associated nodal random variables $\{W_i \mid i \in [n]\}$ and repair data variables $\{S_i^j \mid i \in [n] \setminus j \}$, where $S_i^j$ denotes the data passed from node $i$ to replacement node $j$. The repair matrix $\mathbb{S}$ (see Fig.~\ref{fig:repmatrix}) is an $(n \times n)$ matrix whose $(i,j)$th entry $i \neq j$, is $S_i^j$.  The diagonal elements of $\mathbb{S}$ do not figure in the discussion and maybe set equal to $0$.  Given subsets $H, N \subset [n]$, we
set $W_N = \{W_i \mid i \in N\}$, $S_H^N= \{S_i^j \mid i \in H, j \in N\}$.

We introduce the index sets $X = \{1, 2, \ldots, m\}$, $Y = [k]\setminus X$ and $Z = [k+1, \ d+1]$ for $m \leq k$. The file size $B$ can be expressed in terms of the joint entropy of the node and repair-data variables (with logs computed to base $q$):
\bea
B & = & H(W_X, W_Y) \ = \ H(W_X, S_{Y \cup Z}^Y) \\
& = & H(W_X) + H(S_{Y \cup Z}^Y \mid W_X) \le  H(W_X) + \sum\limits_{j=m+1}^k H(S_{[m+1,j-1] \cup Z}^j \mid W_X) \label{eq:cond_entropy} \\
& \leq & m\alpha + \sum_{i=m+1}^{k} (d-i+1)\beta \ := \ B_m, \  \ m = 0,1,\cdots, k. \label{eq:ER_cutset}
\eea
The cut-set bound in \eqref{eq:cutsetbound} corresponds to the inequalities: $B \leq \min_{m=0,1,\ldots, k} B_m$. For the  bound to hold with equality, the joint random variables $S_Y^Y$ and $S_Z^Y$ must have maximum entropy. However it can be shown that the entropy of a row in the repair matrix is limited by $\beta$ if the cut-set bound holds with equality. This leads to a contradiction, concluding the proof.
\epf

Theorem~\ref{thm:shah_non_exist} does not however, rule out the possibility of an ER code having tradeoff approaching the FR tradeoff asymptotically i.e., as the file size $B \rightarrow \infty$.

\subsection{The S-RB Tradeoff for $(4,3,3)$}

It is possible that the entropies of

the random variables involved satisfy Shannon inequalities other than the ones we have noted and which shed light on the ER tradeoff. For the particular case $(n,k,d)=(4,3,3)$, Tian \cite{Tia} was able to identify such an inequality with the help of a modified version of the Information Theory Inequality Prover (ITIP) \cite{ITIP,Yeu}.

\begin{figure}[ht!]
	\bc
	\includegraphics[width=2.5in]{433.pdf}
	\caption{The (4,3,3) normalized tradeoff. \label{fig:433}}
	\ec
\end{figure}

Let $\bar{\alpha} = \frac{\alpha}{B}$, $\bar{\beta} = \frac{\beta}{B}$ represent the {\em normalization} of $\alpha$ and $\beta$ with respect to file size $B$. A point $(\bar{\alpha}, \bar{\beta})$ is said to be achievable if for any $\epsilon > 0$, there exists an ER-RG code whose $(\bar{\alpha}_1, \bar{\beta}_1)$ is $\epsilon$-close to $(\bar{\alpha}, \bar{\beta})$.  The normalized tradeoff, i.e., the tradeoff expressed in terms of $\bar{\alpha}$ and $\bar{\beta}$ allows comparison of codes across file sizes $B$.  In the limit as $B \rightarrow \infty$, the S-RB tradeoff

becomes a smooth curve.

Let $C_1$, $C_2$ be RG codes over $\mathbb{F}_q$ having respective parameter sets $(n,k,d, (\alpha_1, \beta_1), B_1)$ and \linebreak $(n,k,d, (\alpha_2, \beta_2), B_2)$.  Consider a codeword array $\underline{c}$ obtained by vertically stacking  $M_1$ codeword arrays of $C_1$ and $M_2$ codeword arrays of $C_2$. The code $C$ comprising of all such arrays is said to be the {\em space-shared code} of $C_1$ and $C_2$. Then $C$ is also an RG code with parameter set $(n,k,d, (M_1\alpha_1+M_2\alpha_2, M_1\beta_1+M_2\beta_2), M_1B_1+M_2B_2)$. The notion of space-sharing clearly extends to multiple codes.

\bthm For $(n,k,d)=(4,3,3)$, the achievable region ${\cal R}$ is given by
\bea
{\cal R} & = & \left\{ (\bar{\alpha}, \bar{\beta}) \middle\vert 3\bar{\alpha} \ \geq \ 1, \ 2\bar{\alpha} + \bar{\beta}  \ \geq \ 1, 6\bar{\beta} \ \geq \ 1, 4\bar{\alpha} + 3\bar{\beta} \ \geq \ 1  \right\}. \ \ \ \ \ \ \ \ \ \ \ \label{eq:433bound}
\eea
\ethm
\bpf Of the four inequalities listed, the first $3$ follow the entropy constraints listed in \eqref{eq:ER_cutset} above.  The last inequality $4\bar{\alpha} + 3\bar{\beta} \ \geq \ 1$ does not follow from \eqref{eq:ER_cutset}, and was found in \cite{Tia} using an ITIP.  It remains to construct a code that operate on points on the $(\bar{\alpha}, \bar{\beta})$-plane, satisfying the inequalities with equality. A $[4,3]$ single parity-check code serves as an MSR code $C_1$ for $(4,3,3)$. A $(4,3,3)$ MBR code $C_2$ can be constructed using the polygonal construction described in Sec.~\ref{sec:mbr}. A hand-crafted code $C_3$ operating at the interior point of deflection (see Fig.~\ref{fig:433}) is given in \cite{Tia}. Every point on the lines determined by equality in \eqref{eq:433bound} is achieved by a code obtained by space-sharing among $C_1, C_2$ and $C_3$.
\epf

\subsection{Layered Codes for Interior Points}
\begin{figure}[ht!]
	\centering
	\begin{tabular}{|c|c|c|c|c|}
		\hline
		\textcolor{blue}{1} & \textcolor{blue}{2} & \textcolor{blue}{3} & \textcolor{blue}{4} &   \textcolor{blue}{5} \\
		\hline
		$c_{11}$ & $c_{12}$ & $c_{13}$  & & \\
		\hline
		&  $c_{21}$ & $c_{22}$ & $c_{23}$ &  \\
		\hline
		& & & & \\
		\hline
		$c_{m1}$ &  & $c_{m2}$ & $c_{m3}$  & \\
		\hline
		\vdots  & \vdots & \vdots & \vdots & \vdots \\

		\hline
	\end{tabular}
	\caption{An $(n=5,k=4,d=4)$ canonical layered code. \label{fig:layered}}
\end{figure}
A simple code-construction technique based on the layering (see Fig.~\ref{fig:layered} for an example) of MDS codes turns out to provide codes that perform well with respect to file size in the interior region of the S-RB tradeoff.   Let ${\cal C}_{\text{\tiny MDS}}$ be an MDS code having parameters $[w+\gamma,w,\gamma+1]$.  Let $n$ be such that $w+\gamma\leq n$ and $L={n \choose w+\gamma}$. Let $\{S_i \subset [n] \mid i =1,2,\cdots L\}$ denote an ordering of the collection of all possible $(w+\gamma)$ subsets of $[n]$.  Let $\underline{u}_i \in \mathbb{F}_q^w$, $i = 1,2,\cdots L$ be $L$ message vectors, not necessarily distinct, and $\underline{c}_i$ be the codeword in ${\cal C}_{\text{\tiny MDS}}$ associated with $\underline{u}_i$. We create an $(L \times n)$ array in which we place the symbols of codeword $\underline{c}_i$ in the location specified by subset $S_i$.  It turns out that this array represents an array code which possesses the data collection property of an RG code, but not the repair property.  By replicating the array a certain number $V$ of times, it turns out that one obtains a regenerating code with parameters $(n, k = n-\gamma, d=k, B_0=LVw)$, operating between the MSR and MBR points. Further details can be found in \cite{TiaSasAggVaiKum}.  We will refer to this code as the canonical layered code ${\cal C}_{\text{can}}$. The canonical layered-code construction has been extended to construct codes with $k < d$ by making use of an outer code designed using linearized polynomials.  An alternate generalization of the canonical code to the case of $k < d$ involved adding additional layers consisting of carefully designed parity symbols. Such an approach leads to the {\em improved layered codes} in \cite{SenSasKum_ita}, that turn out to be optimal for the set of parameters  $(n,k=3,d=n-1)$.

\subsection{ER Tradeoff Strictly Away from FR Tradeoff for all $(n,k,d)$}

In \cite{SasSenKum_isit}, it was shown that the ER tradeoff cannot approach the FR tradeoff even when $B \rightarrow \infty$ for any value of $(n,k,d)$. This was established by deriving a positive lower bound $0 < \delta < \beta$ on the gap between the ER and FR tradeoffs.

\bthm \label{thm:away} The ER tradeoff between $\bar{\alpha}$ and $\bar{\beta}$ for any exact-repair regenerating code, with $k \geq 3$ is strictly separated from the FR tradeoff, apart from the MSR and MBR endpoints as well as the region surrounding the MSR point appearing in \eqref{eq:exception}.

\ethm
The proof the theorem involves identifying contradicting bounds on the entropy of various trapezoidal-shaped subsets within the repair matrix. Subsequent papers \cite{Duu1},\cite{Duu2} derive better bounds, thereby improving the gap $\delta$ to go beyond $\beta$. In \cite{MohTan_isit}, the authors adopt a different approach by first providing three different expression for the entropy $B$ of the data file  involving mutual information between various repair-data variables, and taking a linear combination of these expressions that leads to a significantly tighter bound on $B$:
\bea
\label{eq:soh_final}B &\le & \min_{0 \leq p \leq  k} \frac{(3k-2p)\alpha + \frac{p(2(d-k)+p+1)\beta}{2} + (d-k+1)\min\{\alpha, p\beta\} }{3}.
\eea
The authors in \cite{SasPraKriVajSenKum} improve upon the result in \eqref{eq:soh_final} using repair-matrix techniques, in combination with the bound in Thm.~\ref{thm:away}, leading to the best-known outer bound on the ER tradeoff. For the case of $(n,k=3,d=n-1)$, the outer bound is achieved by the improved layered codes, thus characterizing the ER tradeoff. The bound also characterizes certain interior points when $k=4$ \cite{SasSenKum_isit}.

\subsection{Determinant Codes for Interior Points}

The construction given in \cite{ElyMoh} has parameters $\alpha = {k \choose m}$, $\beta = {k-1 \choose m-1}$ and file size $B = m{k+1 \choose m+1}$, where $m \in \{1, 2, \ldots, k\}$ is an auxiliary parameter. The message symbols are first precoded to obtain $k {k \choose m}$ symbols, and these are then arranged in a data matrix $M$ of size $(k \times \alpha)$ in a particular manner. The codeword array is then obtained as in the case of the Product-Matrix framework introduced in \cite{RasShaKum_pm}, by setting $C_{n \times \alpha} = \psi_{n \times k} M_{k \times \alpha}$, where $\psi_{n \times k}$ is a Vandermonde matrix. The data collection and repair properties of the code are proved by making use of the Laplace expansion of determinants, and the codes for this reason, are called {\em determinant codes}. The codes achieve an outer bound discussed in the next subsection, and thus form an optimal family of codes for parameters $(n,k,k)$.  An extension of the construction to include the parameter set $(n,k,d=k+1)$ can be found in \cite{ElyMoh_Allerton}.

\subsection{ER Tradeoff under Linear Setting}

In \cite{PraKri}, \cite{Duu2}, \cite{ElyMohTan} the authors characterize the ER tradeoff for $(n,k=n-1,d=n-1)$ for the subclass of linear codes, using an approach that involves lower bounding the rank of the parity-check matrix of an RG code. The upper bound in \cite{PraKri} holds in general for any $(n,k,d=k)$.
\begin{thm} \label{thm:rankH_new_bound_k_eq_d} Consider an ER linear regenerating code with parameters $\{(n\geq 4, k, d), (\alpha, \beta)\}$ and file size $B = n\alpha - \rho$. Then
	\begin{eqnarray} \label{eq:bound_rank_H_gen}
	\rho & \geq & \left \{ \begin{array}{cl} \left \lceil \frac{2rn\alpha - n(n-1)\beta}{r^2+r}\right \rceil, & \frac{d\beta}{r} \leq \alpha \leq \frac{d\beta}{r-1}, \ \ 2 \leq r \leq n - 2 \\
	2\alpha - \beta, & \frac{d\beta}{n-1} \leq \alpha \leq \frac{d\beta}{n-2} \end{array} \right. .
	\end{eqnarray}
\end{thm}
The corresponding bound on file size $B$ coincides with the achievable region of layered codes when $k=d=(n-1)$.  Determinant codes achieve the above bound in general for $(n,k,k)$, thus characterizing the linear ER tradeoff in this case.
\begin{open} Characterization of ER tradeoff for general $(n,k,d)$ in both the linear and non-linear settings.
\end{open}

\section{Variations on the Theme of Regenerating Codes}\label{sec:variations}

\subsection{Cooperative repair\label{subsec:coop_rep}}
{\it This subsection was contributed at the request of the authors, by Kenneth Shum.}

The potential benefit of allowing data exchange among the nodes being regenerated while repairing multiple node failures simultaneously, was first investigated by Hu et al. in \cite{HuXuWanZhaLi}.  The cooperative-repair process consists of two phases. In the first phase, each of the new nodes selects a set of $d$ surviving nodes, and downloads a total of $d\beta_1$ symbols from them.  In the second phase, a new node downloads $\beta_2$ symbols from each of the other new nodes. If  $t$ new nodes are re-built at the same time, the repair bandwidth per new node is
$d\beta_1 + (t-1) \beta_2. $  As in the non-cooperative case, there is a tradeoff between the amount of data stored in a node and the repair bandwidth. In the following, we denote the repair bandwidth per new node by $\gamma$. The minimum-storage cooperative regenerating (MSCR) point and minimum-bandwidth cooperative regenerating (MBCR) point are determined in~\cite{KerScoStr} and \cite{ShuHu}, and are given by
\begin{align*}
	(\alpha_{\text{MSCR}}, \gamma_{\text{MSCR}}) = \big(\frac{B}{k}, \frac{B(d+t-1)}{k(d+t-k)} \big),\ \ \ \ (\alpha_{\text{MBCR}},\gamma_{\text{MBCR}}) = \frac{B(2d+t-1)}{k(2d+t-k)} \ (1,1),
\end{align*}
where $t$ is the number of nodes to be repaired simultaneously. When $t=1$, they reduce to the corresponding operative points for single-node repair. The full FR tradeoff curve between storage and repair bandwidth per node is derived in~\cite{ShuHu}.
\begin{table}[ht!]
	\caption{Parameters of explicit constructions of cooperative regenerating codes.}
	\label{table:CRC}
	\begin{center}
		\begin{tabular}{|c|c|c|} \hline
			Type & Code Parameters & Ref. \\ \hline \hline
			MBCR & $n, k$, $ k \le d \le (n-t)$, $t\geq 1$ & \cite{WanZhaCoopRegen} \\
			\hline
			MSCR & $n = d+2$, $k=t=2$ & \cite{Sco12} \\ \hline
			MSCR & $n = 2k$, $d=n-2$, $k\geq 2$, $t=2$ & \cite{ShuChe} \\ \hline
			MSCR & $n = 2k$, $d=n-t$, $k\geq 2$, $k\geq t\geq 2$ & \cite{ShuChe} \\
			& (repair of systematic nodes only)&\\ \hline
			MSCR & $n, k$, $ k \le d \le (n-t)$, $t\geq 1$ & \cite{YeBarg_Coop} \\ \hline
		\end{tabular}
	\end{center}
\end{table}
In the case of exact repair, the explicit construction of cooperative regenerating codes for all parameters at the minimum-bandwidth point was first presented in~\cite{WanZhaCoopRegen}. The construction  in~\cite{WanZhaCoopRegen} is presented in an alternate way in~\cite{ShuChe}. Constructions for minimum-storage cooperative codes are relatively rare (see e.g. \cite{Sco12} and \cite{ShuChe}). Table \ref{table:CRC} summarizes the existing constructions of MSCR and MBCR codes. We note that the MSCR codes in \cite{ShuChe} share the same encoding method as in \cite{SuhRam} and \cite{ShaRasKumRam_ia}. It is shown in \cite{ShuChe} that with the MSR codes in \cite{SuhRam} and \cite{ShaRasKumRam_ia}, we can repair multiple systematic nodes with repair bandwidth achieving the MSCR point. In \cite{YeBarg_Coop}, the authors present constructions for any $(n,k, k \le d \le n-t, t)$ MSCR codes.

The cooperative repair model was extended to partial cooperative repair in~\cite{LiuOgg_a}. The first phase of repair is the same as described above. Each of the $t$ new nodes contacts $d$ other nodes and download a total of $\beta_1$ data packets. In the second phase, a new node exchanges $\beta_2$ data packets with $t-s$ other new nodes, where $s$ is a system parameter between 1 and $t$. When $s=t$, it is the original single-loss repair model. When $s=1$, it reduces to the cooperative repair model. The minimum-storage and minimum bandwidth point are derived in~\cite{LiuOgg_a}. With partial collaboration, the minimum-storage and minimum-bandwidth operating points are given respectively by
\bean
(\alpha,\gamma) = \big(\frac{B}{k}, \frac{B(d+t-s)}{k(d-k+t-s+1)}\big) & \text{ and } & (\alpha,\gamma) =  \frac{B(2d+t-s)}{k(2d-k+t-s+1)} \ (1,1).
\eean
Two explicit codes for partial collaborative repair are presented in~\cite{LiuOgg_b}. The code construction in~\cite{ShuChe} for MBCR codes can be extended to achieve all minimum-bandwidth points with partial collaboration. The security of cooperative regenerating codes is investigated in \cite{KoyRawVish,HuaParXia}.

\subsection{MDS Codes with Repair Capability}

We discuss in this subsection, vector MDS codes that are not MSR, which nevertheless offer some savings in repair bandwidth in comparison to the conventional repair of RS codes while keeping the sub-packetization level $\alpha$ small. The piggybacking framework introduced in \cite{RasShaRam_Piggyback}, was one of the first such efforts.  In \cite{GurRaw_MDS}, the authors introduce codes that offer a choice of sub-packetization levels, namely, $\alpha = r^p$ for $1 \le p < \left\lceil\frac{n}{r}\right\rceil$. The corresponding repair download from each helper node is given by $\beta = (1+\frac{1}{p})r^{p-1}$. When $p=\left\lceil\frac{n}{r}\right\rceil$ these codes coincide with the construction in \cite{SasAgaKum}. A similar approach was followed by the authors of \cite{KralevskaGligoroski} where they provide constructions for MDS codes for any given $1 \le \alpha \le r^{\left\lceil\frac{k}{r}\right\rceil}$. However, the constructions here are restricted to systematic node repair and the bandwidth needed from each helper node is not uniform.
These constructions are motivated by the systematic MSR code with $\alpha=r^{\left\lceil\frac{k}{r}\right\rceil}$ appearing in \cite{AgaSasKum}. In more recent work \cite{RawTamGur_epsilonMSR}, the $\epsilon$-MSR framework was introduced to construct MDS codes that somewhat surprisingly, have sub-packetization $\alpha$ that is {\em logarithmic} in $n$ for a modest increase in repair bandwidth by a multiplicative factor $(1+\epsilon)$.\\

{\bf Piggybacking framework:}  The piggybacking framework \cite{RasShaRam_Piggyback} begins with a collection of $\alpha$ codewords drawn form an MDS code and proceeds to modify the code symbols as described below.

Let $\mathcal{C}$ be an MDS code and let $(f_1(\textbf{u}),f_2(\textbf{u}),\dots,f_n(\textbf{u}))$ represent the codeword  corresponding to message $\textbf{u}$. Next, consider codewords of $\mathcal{C}$ corresponding to $\alpha$ distinct messages, $\textbf{u}_1,\dots,\textbf{u}_\alpha$.  The $\alpha$ code symbols $f_j(\textbf{u}_i)$, $i=1,2,\cdots,\alpha$ are stored on node $j$.

We first modify the code by adding a function $g_{ij}(\textbf{u}_1,\dots,\textbf{u}_{i-1})$ to the $j$-th symbol of $i$-th codeword $f_j(u_i)$, for all $i \in \{2,\dots,\alpha\}, j \in \{1,\dots,n\}$.  The values so added are termed as piggybacks. This modification does not affect our ability to decode the code, if the codewords are decoded in sequence.  Applying an invertible linear transform $T_i$ to the $\alpha$ code symbols in the $i$th node, similarly does not affect our ability to decode the $\alpha$ codewords, nor a node's ability to serve as a helper node.

By carefully choosing the piggybacking functions and the set $T_i$ of invertible linear transformations it possible to reduce the repair bandwidth for the collective repair of the $\alpha$ MDS codewords in comparison with the repair bandwidth needed for the conventional repair of $\alpha$ MDS codewords.
Three families of piggybacking-based MDS codes with reduced repair bandwidth and disk read are constructed in \cite{RasShaRam_Piggyback}. The piggybacking framework typically provides savings between $25\%$ to $50\%$ depending up on the parameters and choice of piggybacking functions. For example, Fig.~\ref{PB} shows modification of a $[4,2]$ MDS code with sub-packetization level $2$ in such a way that the systematic nodes can be repaired by reading $3$ symbols (instead of the $4$ symbols required for MDS decoding), resulting in a $25\%$ repair bandwidth and disk read saving.
\begin{figure}[!ht]
	\centering
	\includegraphics[width=6.5in]{Piggyback_4_2.pdf}
	\caption{Here two codewords of a [4,2] MDS code are piggybacked. The first systematic node can be repaired by reading $ b_2$, $b_1+b_2$ and $b_1+2b_2+a_1$, whereas the second systematic node repair requires $b_1$, $b_1+b_2$ and $2a_2-2b_2-b_1$}.
	\label{PB}
\end{figure}

{\bf $\epsilon$-MSR framework:} The motivation for constructing $\epsilon$-MSR codes \cite{RawTamGur_epsilonMSR} is the larger sub-packetization level of an MSR code, which could possibly prove to be a hurdle in its practical implementation.

The authors of \cite{RawTamGur_epsilonMSR} provide a generic way  to transform an MSR code into an $\epsilon$-MSR code.

\begin{definition}
	An MDS code $\mathcal{C}$ with sub-packetization $\alpha$ over a finite field $\mathbb{B}$  is said to be an $(n,k,d=n-1,\alpha)_\mathbb{B}$ $\epsilon-$MSR code, $\epsilon > 0$, if for every $i \in [n]$ there exists a linear repair scheme for the code symbol $c_i$ which downloads $\beta_{ij} \le (1+\epsilon)\frac{\ell}{n-k}$ symbols over $\mathbb{B}$ from the $(n-1)$ nodes storing code symbols $c_j$, for $j \in [n]\setminus \{i\}$.

\end{definition}

The construction of an $\epsilon$-MSR code presented in \cite{RawTamGur_epsilonMSR} combines a short block-length MSR code with a code having large minimum distance.

Let $\mathcal{C}_I$ be an $(n=k+r,k,d=n-1,\alpha)_{\mathbb{B}}$ MSR code having parity check matrix,
\begin{equation*}
	H=
	\begin{bmatrix}
		H_{1,1} & H_{1,2} &\dots& H_{1,n} \\
		\vdots & \vdots & \dots & \vdots \\
		H_{r,1} & H_{r,2} &\dots& H_{r,n}
	\end{bmatrix},
\end{equation*}
where the sub-matrices $H_{i,j}$ are of size $(\alpha \times \alpha)$. Next, let $\mathcal{C}_{II}$ be a (not necessarily linear) code having block length $N$, size $M$ and minimum distance $D=\delta N$ over an alphabet $\mathbb{G}$ of size $|\mathbb{G}|\le n$. Let us associate with every codeword $c=(c_1,\dots,c_N)$ of $\mathcal{C}_{II}$, an $(rN\alpha \times N\alpha)$ matrix:
\begin{equation*}
	\mathcal{H}_c=
	\begin{bmatrix}
		u_{1,c}\ \text{Diag}(H_{1,c_1},\dots,H_{1,c_N})\\
		\vdots\\
		u_{r,c}\ \text{Diag}(H_{r,c_1},\dots,H_{r,c_N})\\
	\end{bmatrix},
\end{equation*}
where the $\{u_{i,c}\}$ are non-zero coefficients, drawn from $\mathbb{B}$. Next, using the fact that the number of codewords in $\mathcal{C}_{II}$ is $M$, let us form an $(rN\alpha \times MN\alpha)$ matrix $\mathcal{H}$ with each of the $M$ `thick' columns $\mathcal{H}_c$ corresponding to a different codeword $c \in  \mathcal{C}_{II}$. It can be shown that the code having $\mathcal{H}$ as its parity-check matrix is an $(M,M-r,d=M-1,N\alpha)_{\mathbb{B}}$  $\epsilon$-MSR code, where $\epsilon=(r-1)(1-\delta)$.
Ensuring this requires judicious selection of the base MSR code $\mathcal{C}_{I}$ as well as the non-zero scalars $\{u_{i,c}\}$. An additional requirement is that for a given $\epsilon>0$, the code $\mathcal{C}_{II}$ should be chosen such that the parameter $\delta$ satisfies $\delta \ge 1-\frac{\epsilon}{r-1}$. The $\epsilon$-MSR codes constructed using this approach can have sub-packetization level scaling logarithmically in the block length. \\
In \cite{RawTamGur_epsilonMSR}, $\epsilon$-MSR codes are constructed by picking the non-optimal-access MSR constructions in \cite{YeBar_1} as $\mathcal{C}_I$. For instance, using $\mathcal{C}_I$ with parameters $(n=3,k=1,d=2,\alpha=2^{3}=8)$ and $\mathcal{C}_{II}$ with parameters $N=20, M=27$ and $D=13$ over $\mathbb{F}_3$ one can construct a $(M=27,M-r=25,M-1=26,N\alpha=160)$ $\epsilon$-MSR code. Note that the MSR code $\mathcal{C}_I$ with parameters $(n=27,k=25,d=26)$ requires a sub-packetization level of $2^{27}$, whereas this $\epsilon$-MSR code has sub-packetization level of 160 $(\ll 2^{27})$ and repair bandwidth is within $1.35$ times that of the MSR code.

\subsection{Fractional Repetition Codes}
\begin{figure}[ht!]
	\centering
	\includegraphics[width=1.8in]{fig_fano_plane_v2.pdf}
	\caption{Each of the seven lines in the Fano plane indicates a node and points within a line denote the code symbols stored in the corresponding node. For instance, $N_1=\{c_1,c_2,c_3\}$.   }\label{fig:fano_plane}
\end{figure}
Fractional Repair (FR) Codes, introduced in \cite{RouRamFR10}, are regarded as codes that generalize the RBT MBR construction in \cite{RasShaKumRam_allerton09}.   An FR code is associated with the parameter set $\{n,k,\alpha,\rho\}$, where $n$ is the number of nodes and $k$ is the smallest number such that one can retrieve the entire data file from connecting to any set of that many nodes. Let $K$ be the file size of the FR code. To encode and store data, an FR code begins by encoding a collection $\{u_1,\cdots, u_K\}$ of message symbols drawn from a finite field $\mathbb{F}_q$ using a scalar $[N,K]$ MDS code ${\cal A}$, also referred to as the DRESS code in \cite{PawNoorRouRamDressCode11}.  Let $(v_1,v_2,\cdots,v_N)$ denote the symbols of a codeword in ${\cal A}$.  Each of the $N$ scalar code symbols is replicated $\rho$ times and the resultant $\rho N$ symbols are stored across the $n$ nodes in such a way that there are $\alpha$  symbols per node and each code symbol is present in precisely $\rho$ distinct nodes. Combinatorial techniques such as $t$-designs are used to make such an assignment possible. For this to happen, we must have that $n\alpha= N\rho$.
In order to be able to recover the entire data file by connecting to any $k$ nodes we must clearly have that: $R_\mathcal{C}(k)\triangleq\min_{{J\subseteq [n]}:|J|=k}|\cup_{j\in J} N_j|  \geq   K$,
where $N_j$ indicates the set of $\alpha$ code symbols stored in $j^\text{th}$ node, $j\in[n]$. Note that $R_\mathcal{C}(k)$ is defined with respect to a given collection $\{N_j\}_{j=1}^n$. Let $C_{FR}(n,k,\alpha,\rho)$ denote the maximum  $R_\mathcal{C}(k)$ possible across all possibilities of $\{N_j\}_{j=1}^n$, which conform to the parameters $n,\alpha$ and $\rho$. Hence an FR code is said to be {\it $k$-optimal} \cite{SilbEtzOptimalFR15}, if it satisfies: $
K=C_{FR}(n,k,\alpha,\rho)$.

In contrast to an MBR code, an FR code requires the existence of just a single set of $d=\alpha$ helper nodes to perform RBT. However it follows naturally from the $\rho$-replication of code symbols that such a set of $d$ helper nodes is available, even in the presence of $(\rho-1)$ node failures.

\begin{eg}[\cite{RouRamFR10}]
	Consider an FR code $\mathcal{C}$ with parameters $n=7, k=3, d=3, \rho=3$. The code is described using the Fano plane as shown in Figure \ref{fig:fano_plane}. Here $R_\mathcal{C}(k)=6$. By choosing the outer MDS code to be the $[7,6]$ single parity check code, data collection property follows. As each symbol is shared by three lines, $\rho=3$ and hence $\mathcal{C}$ permits RBT up to $2$ node failures.
\end{eg}

The following bound on the maximum rate of an FR code with parameters $(n,k,\alpha,\rho)$, is derived in \cite{RouRamFR10}.
\bean
C_{FR}(n,k,\alpha,\rho) & \leq & \min \left\{ \bigg\lceil\frac{n\alpha}{\rho}\bigg(1-\frac{\binom{n-\rho}{k}}{\binom{n}{k}}\bigg)\bigg\rfloor, \ g(n,k,\alpha,\rho) \right\},\\
\text{ where } \ g(n,1,\alpha,\rho)=1,  &  \text{ and } &  g(n,k+1,\alpha,\rho)=g(n,k,\alpha,\rho)+\alpha-\bigg\lceil\frac{\rho g(n,k,\alpha,\rho)-k\alpha}{n-k}\bigg\rceil.
\eean

The paper \cite{SilbEtzOptimalFR15} considers FR codes with parameters $\alpha \geq k$, $\beta=1$ and provides several $k$-optimal constructions. The work \cite{OlmRamFRCodes16} considers FR codes with parameter $\beta\geq 1$ and also introduces a certain notion of locally recoverable FR codes where the parameter $\alpha<k$. In  \cite{KooGillScaleFR11}, the authors study FR codes that have $\alpha$ much larger than replication degree, $\rho$. In \cite{ExistenceFR}, the authors identify necessary and sufficient conditions for the existence of FR codes.

\subsection{Secure Regenerating Codes}

Three secrecy models in the context of a regenerating code are introduced in \cite{PawarRouayRam}: (a) a passive eavesdropper model, where the eavesdropper can read the contents of any $\ell$ nodes but cannot modify the content of these nodes, (b) an active omniscient adversary model, where the adversary can read the content of $\ell=k$ nodes and can also modify the content of $b$ nodes where $2b \le k$ and (c) an active limited-knowledge adversary model, where the adversary can read the content of $\ell < k$ nodes and can modify the content of $b \le \ell$ nodes. In the case of a passive eavesdropper, the {\em secrecy capacity} ($B_s$)
is the maximum amount of information that can be stored without any information being revealed to the eavesdropper.  In the active eavesdropper model, the {\em resiliency capacity} ($B_r$) is the maximum amount of information that can be stored such that it can be reliably made available to a legitimate data collector, in spite of the tampering on the data in $b$ nodes done by the eavesdropper. In \cite{PawarRouayRam}, the following upper bound on secrecy capacity of the passive eavesdropper model was derived:

\bea
\label{eq:securerc_passive}
B_s(\alpha, \gamma = d\beta) \le \sum\limits_{i=\ell+1}^k \min \{(d-i+1)\beta, \alpha\}.
\eea If $\alpha$ is not constrained, then the resultant {\em bandwidth-limited secrecy capacity} $B_{s,\text{BL}}$ becomes a function of $(k, d,\beta)$ alone. The value of $B_{s,\text{BL}}$ is determined \cite{PawarRouayRam} for $d=(n-1)$ by providing a bound and an optimal construction. It was also shown that the resiliency capacity satisfies $B_r(\alpha, \gamma) \le \sum\limits_{i=i_0}^k \min \{(d-i+1)\beta, \alpha\}$,
where $i_0$ is equal to $2b+1$ for omniscient case and $b+1$ for the limited knowledge case.

In an alternate setting, Rashmi et al. in \cite{RashmiShahRamKum_errors} assume a noisy channel for transmission of data during repair and reconstruction, and introduce the notion of an $(s,t)$-resilient regenerating code that can correct up to $t$ errors and $s$ errors during both repair and reconstruction. The model is aligned with the active eavesdropper model where the eavesdropper can tamper the contents of $b$ nodes. An $(s,t)$-resilient regenerating code is shown to satisfy $B \le \sum\limits_{i=1}^{k} \min \{(d-i+1)\beta, \alpha \}$ where, $d = \Delta - 2t-s$, $k = \kappa - 2t-s$ and $\Delta, \kappa$ are the number of nodes contacted during repair and reconstruction respectively.  Constructions of MSR and MBR codes that are $(s,t)$ resilient are also provided in \cite{RashmiShahRamKum_errors}. In \cite{YeBar_1}, the authors extend this model to the repair of multiple nodes and provide MSR constructions that are resilient to $t$ errors during repair. In \cite{ShahRashKum}, the authors extend the passive eavesdropper model to the setting where out of the $\ell$ nodes accessed, the eavesdropper can read the contents of $\ell_1$ nodes and can observe the information passed on for the repair of $\ell_2 = \ell - \ell_1$ nodes. The upper bound in \eqref{eq:securerc_passive} also holds for this extended case. In the case of an MBR code, since the amount of data stored equals the amount of data received for node repair, the breakup between $\ell_1,\ell_2$ is immaterial.

However in the case of an MSR code, $d\beta > \alpha$. In \cite{ShahRashKum}, the authors provide explicit, secure MBR, and low-rate MSR code constructions that achieve the upper bound \eqref{eq:securerc_passive} for $\ell_2=0$. The secure MSR construction from \cite{ShahRashKum} provides a lower bound to the secure file size of an MSR code: $B_s \ge  (k-\ell)(\alpha - \ell_2 \beta)$ for $\ell_2 > 0$.

The upper bound on secure MSR file size $B_s \le (k-\ell)\alpha$ given by \eqref{eq:securerc_passive} is improved in \cite{TandonAmuruClancyBuehrer,RawatKoyluSilberVish,GopaRouayCladerPoor,HuangParamXian}. In \cite{Rawat_secrecy}, Rawat established that the secrecy capacity of an MSR codes is given by $B_s = (k-\ell)(1-\frac{1}{n-k})^{\ell_2}\alpha$ by providing an MSR construction. An upper bound that matches with Rawat's construction is proved by Goparaju et.al in \cite{GopaRouayCladerPoor} under the constraint of linearity. In \cite{KadheSprinston}, secure MSR codes with smaller field sizes for all parameters were constructed. In \cite{YeShumYeung,ShaoLiuTianShen} the ER tradeoff is studied for secure regenerating codes.


TITLE: How to Define Product Orientations for Topological Manifolds
QUESTION [5 upvotes]: When working with smooth manifolds,  $M^m$ and $N^n$, it is straightforward to see how orientations at points $p\in M$ and $q\in N$ (i.e. ordered bases for the tangent spaces) give rise to an orientation at the point $(p,q) \in M \times N$, given a convention about which basis should come first.  However in the continuous setting, it isn't so clear to me how a choice of generators for $H_m(M, M-p)$ and $H_n (N, N-q)$ should naturally give rise to a generator for $H_{n+m} (M \times N, M\times N -(p,q))$.  I think you can probably do it by the same method as in the smooth case once you choose local coordinates and a convention about how ordered bases for $\mathbb{R}^n$ correspond to generators of $H_n(\mathbb{R}^n, \mathbb{R}^n-0)$, but I was hoping for some purely algebraic-topology construction that doesn't use tangent vectors. Thank you for your time.

REPLY [7 votes]: The answer comes from the Künneth formula. Of course, by excision, you are localizing and looking at $H_m(D^m,\partial D^m)$, $H_n(D^n,\partial D^n)$, and $H_{m+n}(D^{m+n},\partial D^{m+n})$. An orientation, as you pointed out, is a choice of generator for $H_m(D^m,\partial D^m) \cong \mathbb Z$, etc. Now, the Künneth isomorphism [see, e.g., Hatcher p. 276 for the relative statement]
\begin{align*}
H_m(D^m,\partial D^m)\otimes H_n(D^n,\partial D^n) &\overset{\cong}{\to} H_{m+n}(D^m\times D^n,\partial D^m\times D^n \cup D^m\times\partial D^n)\\ &\cong H_{m+n}(D^{m+n},\partial D^{m+n})
\end{align*}
gives you what you want. (It's probably easiest to visualize the last step thinking of cubes, rather than disks.)


TITLE: How to understand two examples of spin bundle
QUESTION [2 upvotes]: I am confused by two examples of spinor bundles over 4-manifolds, which I saw in various places:
(1) The spinor bundle $S = S_+ \oplus S_-$ associated to a spin or spinc structure of Riemannian four-manifold $M$
(2) If the manifold $M$ has almost complex structure, then the bundle $\tilde S \equiv \Lambda^{0,*}T^*M$ is also a spin bundle, which can also be split into $\tilde S_+ = \Lambda^{0,0}T^*M \oplus \Lambda^{0,2}T^*M$ and $\tilde S_- = \Lambda^{0,1}T^*M$.
My question is: are the two examples the same? In particular, I know that $S_+ \otimes S_+ = \Lambda_+^2 T^*M \oplus C^\infty(M)$ where $\Lambda_+^2T^*M$ denotes the bundle of self-dual two forms (corresponding to symmetric product of two $S_+$), I wonder if the same is true for $\tilde S_+$? I think it is true, since I can multiply by $(\sigma_{\mu \nu})^{\alpha \beta}$ to go from a bi-spinor to a self-dual 2-form. But I want to see if there is a more geometrical way (playing with the $(0,{\rm even})$-forms) to see it.
Thanks!

REPLY [3 votes]: First let me point out that the bundle $\Lambda^2_+ T^*M$ makes sense only when $\dim M=4$. Maybe you should   add this assumption.
As for your question, I think that you can find the answer in Example 1.3.3 page 30 of these notes.