Multilevel Diversity Coding with Secure Regeneration: Separate Coding Achieves the MBR Point

Abstract

The problem of multilevel diversity coding with secure regeneration (MDC-SR) is considered, which includes the problems of multilevel diversity coding with regeneration (MDC-R) and secure regenerating code (SRC) as special cases. Two outer bounds are established, showing that separate coding can achieve the minimum-bandwidth-regeneration (MBR) point of the achievable normalized storage-capacity repair-bandwidth trade-off regions for the general MDC-SR problem. The core of the new converse results is an exchange lemma, which can be established using Han’s subset inequality.

1. Introduction

Diversity coding and node repair are two fundamental ingredients of reliable distributed storage systems. While the study of diversity coding has been in the literature for decades [1,2,3,4,5,6], systematic studies of node repair mechanisms were started only recently by Dimakis et al. in their pioneering work [7]. A particular model, which was first introduced in [7] and has since received a significant amount of attention in the literature [8,9,10,11,12,13,14,15,16,17,18,19,20], is the so-called (exact-repair) regenerating code (RC) problem.

More specifically, in an $(n,k,d)$ RC problem, a file $\mathsf{M}$ of size B is to be encoded in a total of n distributed storage nodes, each of capacity $\alpha$. The encoding needs to ensure that the file $\mathsf{M}$ can be perfectly recovered by having full access to any k out of the total n storage nodes. In addition, when node failures occur and there are only d remaining nodes in the system, it is required that the data originally stored in any failed node can be recovered by downloading data of size $\beta$ from each one of the d remaining nodes. An interesting technical challenge is to characterize the optimal trade-offs between the node capacity $\alpha$ and the download bandwidth $\beta$ in satisfying both the file-recovery and node-repair requirements, which was studied in [8,9,10,11,12,13,14,15,16,17,18,19,20]. However, despite intensive research efforts that have yielded many interesting and highly non-trivial partial results including a precise characterization of the minimum-storage-regenerating (MSR) and the minimum-bandwidth-regenerating (MBR) rate points, the optimal trade-offs between the node capacity $\alpha$ and the download bandwidth $\beta$ have not been fully understood for the general RC problem.

More recently, two extensions of the RC problem, namely multilevel diversity coding with regeneration (MDC-R) and secure regenerating code (SRC), have also been studied in the literature. The problem of MDC-R was first introduced by Tian and Liu [21]. In an $(n,d)$ MDC-R problem, a total of d independent files ${\mathsf{M}}_1,\dots ,{\mathsf{M}}_d$ of size $B_1,\dots ,B_d$, respectively, are to be stored in n distributed storage nodes, each of capacity $\alpha$. The encoding needs to ensure that the file ${\mathsf{M}}_j$ can be perfectly recovered by having full access to any j out of the total n storage nodes for any $j\in \{1,\dots ,d\}$. In addition, when node failures occur and there are only d remaining nodes in the system, it is required that the data originally stored in any failed node can be recovered by downloading data of size $\beta$ from each one of the d remaining nodes.

Clearly, an $(n,k,d)$ RC problem can be viewed as an $(n,d)$ MDC-R problem with degenerate messages $({\mathsf{M}}_j:j\ne k)$ (i.e., $B_j=0$ for all $j\ne k$). Therefore, from the code construction perspective, it is natural to consider the so-called separate coding scheme, i.e., to construct a code for the $(n,d)$ MDC-R problem, we can simply use an $(n,j,d)$ RC to encode the file ${\mathsf{M}}_j$ for each $j\in \{1,\dots ,d\}$, and the coded messages for each file remain separate when stored in the storage nodes and during the repair processes. However, despite being a natural scheme, it was shown in [21] that separate coding is in general suboptimal in achieving the optimal trade-offs between the normalized storage-capacity and repair-bandwidth. On the other hand, it has been shown that separate coding can, in fact, achieve both the MSR [21] and the MBR [22] points of the achievable normalized storage-capacity and repair-bandwidth trade-off region for the general MDC-R problem.

The problem of SRC is an extension of the RC problem that further requires security guarantees during the repair processes. More specifically, the $(n,k,d,\ell )$ SRC problem that we consider is the $(n,k,d)$ RC problem [7,8,9,10,11,12,13,14,15,16], with the additional constraint that the file $\mathsf{M}$ needs to be kept information-theoretically secure against an eavesdropper, which can access the data downloaded to regenerate a total of ℓ different failed nodes under all possible repair groups. Obviously, this is only possible when $\ell <k$. Furthermore, when $\ell =0$, the secrecy requirement degenerates, and the $(n,k,d,\ell )$ SRC problem reduces to the $(n,k,d)$ RC problem without any repair secrecy requirement.

Under the additional require secrecy requirement ($\ell \ge 1$), the optimal trade-offs between the node capacity $\alpha$ and repair bandwidth $\beta$ have been studied in [23,24,25,26,27,28,29,30]. In particular, Shah, Rashmi and Kumar [25] showed that a particular trade-off point (referred to as the SRK point as the three first letters of the authors’ names) can be achieved by extending an MBR code based on the product-matrix construction proposed in [8]. Later, it was shown [30] that, for any given $(k,d)$ pair, there is a lower bound on ℓ, denoted by ${\ell }^{*}(k,d)$, such that, when $\ell \ge {\ell }^{*}(k,d)$, the SRK point is the only corner point of the trade-off region for the $(n,k,d,\ell )$ SRC problem. On the other hand, when $1\le \ell <{\ell }^{*}(k,d)$, it is possible that the trade-off region features multiple corner points, even though a precise characterization of the trade-off region, including both the MSR and the MBR points, remains missing in general.

In this paper, we introduce the problem of multilevel diversity coding with secure regeneration (MDC-SR) (The problem of secure multilevel diversity coding without any node regeneration requirement has been considered in [6,31].), which includes the problems of MDC-R and SRC as two special cases. In this model, multiple files are to be stored distributed in several storage nodes, like what in the Multilevel Diversity Coding problem. The system requires that, if a user can fully access some of the nodes, then the user can recover the corresponding part of the original files. Meanwhile, if any storage node failed, it can be regenerated by downloading messages from other nodes within a certain bandwidth limit. Additionally, if some nodes and repairing messages are leaked to an eavesdropper, the original files can still be information that is theoretically secure. The detailed definition of this model can be found in the next section. Similar to the MDC-R problem, it is natural to consider the separate coding scheme for the MDC-SR problem as well. Our main contribution consisted of three parts. Firstly, we established two nontrivial outer bounds for the MDC-SR problem. The secrecy constraint in the MDC-SR problem makes the outer bounding its trade-off region, not a simple extension of the bounding technic of the MDC-R problem in [22]. Secondly, we addressed a coding scheme with a separate coding structure that can achieve the intersection of the two outer bounds that we established, hence we can show that the optimality of separate coding in terms of achieving the MBR point of the achievable normalized storage-capacity and repair-bandwidth trade-off region extends more generally from the MDC-R problem to the MDC-SR problem. Last but not the least, during the process of establishing the two outer bounds, we proposed a lemma called Exchange Lemma, which we believe can be used widely in other similar or even more generalized problems. We need to mention that our system model and main results can be degenerated to some unknown results. For example, when specialized to the SRC problem, our result shows that the SRK point [25] is, in fact, the MBR point of the achievable normalized storage-capacity and repair-bandwidth trade-off region, regardless of the number of corner points of the trade-off region.

From the technical viewpoint, this is mainly accomplished by establishing two outer bounds (one of them must be “horizontal”, i.e., on the normalized repair-bandwidth only) on the achievable normalized storage-capacity and repair-bandwidth trade-off region, which intersect precisely at the superposition of the SRK points. The core of the new converse results is an exchange lemma, which we establish by exploiting the built-in symmetry of the problem via Han’s subset inequality [32]. The meaning of “exchange” will be clear from the statement of the lemma. The lemma only relies on the functional dependencies for the repair processes and might be useful for solving some other related problems as well.

The rest of the paper is organized as follows. In Section 2, we formally introduce the problem of MDC-SR and the separate coding scheme. The main results of the paper are then presented in Section 3. In Section 4, we introduce the exchange lemma and use it to establish the main results of the paper. Finally, we conclude the paper in Section 5.

Notation and Remarks. Sets and random variables will be written in calligraphic and sans-serif fonts respectively, to differentiate from the real numbers written in normal math fonts. For any two integers $t\le t^{\prime }$, we shall denote the set of consecutive integers $\{t,t+1,\dots ,t^{\prime }\}$ by $[t:t^{\prime }]$. The use of the brackets will be supressed otherwise.

Though many remarkable previous works are mentioned in this introduction, some of them, in fact, are more related to our work, such as [15,25,29]. We list them for the best convenience of our readers.

2. The MDC-SR Problem

Let $(n,d,N_1,\dots ,N_d,K,T,S)$ be a tuple of positive integers such that $d<n$. Formally, an $(n,d,N_1,\dots ,N_d,K,T,S)$ code consists of:

• for each $i\in [1:n]$, a message-encoding function $f_i:\left({\prod }_{j=1}^d[1:N_j]\right)\times [1:K]\to [1:T]$;
• for each $\mathcal{A}\subseteq [1:n]:|\mathcal{A}|\in [1:d]$, a message-decoding function $g_{\mathcal{A}}:{[1:T]}^{|\mathcal{A}|}\to [1:N_{|\mathcal{A}|}]$;
• for each $\mathcal{B}\subseteq [1:n]:|\mathcal{B}|=d$, $i^{\prime }\in \mathcal{B}$, and $i\in [1:n]\setminus \mathcal{B}$, a repair-encoding function $f_{i^{\prime }\to i}^{\mathcal{B}}:[1:T]\to [1:S]$;
• for each $\mathcal{B}\subseteq [1:n]:|\mathcal{B}|=d$ and $i\in [1:n]\setminus \mathcal{B}$, a repair-decoding function $g_i^{\mathcal{B}}:{[1:S]}^d\to [1:T]$.

For each $j\in [1:d]$, let ${\mathsf{M}}_j$ be a message that is uniformly distributed over $[1:N_j]$. The messages ${\mathsf{M}}_1,\dots ,{\mathsf{M}}_d$ are assumed to be mutually independent. Let $\mathsf{K}$ be a random key that is uniformly distributed over $[1:K]$ and independent of the messages $({\mathsf{M}}_1,\dots ,{\mathsf{M}}_d)$. For each $i\in [1:n]$, let ${\mathsf{W}}_i=f_i({\mathsf{M}}_1,\dots ,{\mathsf{M}}_d,\mathsf{K})$ be the data stored at the ith storage node, and for each $\mathcal{B}\subseteq [1:n]:|\mathcal{B}|=d$, $i^{\prime }\in \mathcal{B}$, and $i\in [1:n]\setminus \mathcal{B}$, let ${\mathsf{S}}_{i^{\prime }\to i}^{\mathcal{B}}=f_{i^{\prime }\to i}^{\mathcal{B}}({\mathsf{W}}_{i^{\prime }})$ be the data downloaded from the $i^{\prime }$th storage node in order to regenerate the data originally stored at the ith storage node under the context of repair group $\mathcal{B}$. Obviously,

$$\begin{array}{cc}\hfill (B_j& =log{N}_j:j\in [1:d]),\alpha =logT,\mathrm{and}\beta =logS\hfill \end{array}$$

represent the message sizes, storage capacity, and repair bandwidth, respectively.

A normalized message-rate storage-capacity repair-bandwidth tuple $({\overline{B}}_{\ell +1},\dots ,{\overline{B}}_d,\overline{\alpha },\overline{\beta })$ is said to be achievable for the $(n,d,\ell )$ MDC-SR problem if an $(n,d,1,\dots ,1,N_{\ell +1},\dots ,N_d,K,T,S)$ code (i.e., $N_j=1$ for all $j\in [1:\ell ]$) can be found such that:

• (rate normalization)

  $$\begin{array}{c}\hfill \frac{\alpha }{{\sum }_{t=\ell +1}^d{B}_t}=\overline{\alpha },\frac{\beta }{{\sum }_{t=\ell +1}^d{B}_t}=\overline{\beta },\frac{B_j}{{\sum }_{t=\ell +1}^d{B}_t}={\overline{B}}_j\end{array}$$

  (1)

  for any $j\in [\ell +1:d]$;
• (message recovery)

  $$\begin{array}{c}\hfill {\mathsf{M}}_{|\mathcal{A}|}=g_{\mathcal{A}}({\mathsf{W}}_i:i\in \mathcal{A})\end{array}$$

  (2)

  for any $\mathcal{A}\subseteq [1:n]:|\mathcal{A}|\in [\ell +1:d]$;
• (node regeneration)

  $$\begin{array}{c}\hfill {\mathsf{W}}_i=g_i^{\mathcal{B}}({\mathsf{S}}_{i^{\prime }\to i}^{\mathcal{B}}:i^{\prime }\in \mathcal{B})\end{array}$$

  (3)

  for any $\mathcal{B}\subseteq [1:n]:|\mathcal{B}|=d$ and $i\in [1:n]\setminus \mathcal{B}$;
• (repair secrecy)

  $$\begin{array}{c}\hfill I(({\mathsf{M}}_{\ell +1},\dots ,{\mathsf{M}}_d);({\mathsf{S}}_{\to i}:i\in \mathcal{E}))=0\end{array}$$

  (4)

  for any $\mathcal{E}\subseteq [1:n]$ such that $|\mathcal{E}|=\ell$, where ${\mathsf{S}}_{\to i}:=({\mathsf{S}}_{i^{\prime }\to i}^{\mathcal{B}}:\mathcal{B}\subseteq [1:n],|\mathcal{B}|=d,\mathcal{B}\not\ni i,i^{\prime }\in \mathcal{B})$ is the collection of data that can be downloaded from the other nodes to regenerate node i.

The closure of all achievable $({\overline{B}}_{\ell +1},\dots ,{\overline{B}}_d,\overline{\alpha },\overline{\beta })$ tuples is the achievable normalized message-rate storage-capacity repair-bandwidth trade-off region ${\mathcal{R}}_{n,d,\ell }$ for the $(n,d,\ell )$ MDC-SR problem. For a fixed normalized message-rate tuple $({\overline{B}}_{\ell +1},\dots ,{\overline{B}}_d)$, the achievable normalized storage-capacity repair-bandwidth trade-off region is the collection of all normalized storage-capacity repair-bandwidth pairs $(\overline{\alpha },\overline{\beta })$ such that $({\overline{B}}_{\ell +1},\dots ,{\overline{B}}_d,\overline{\alpha },\overline{\beta })\in {\mathcal{R}}_{n,d,\ell }$ and is denoted by ${\mathcal{R}}_{n,d,\ell }({\overline{B}}_{\ell +1},\dots ,{\overline{B}}_d)$.

Based on the above problem formulation, it should be clear that the MDC-SR problem includes several open problems of recent interest:

(1)

the achievable normalized storage-capacity repair-bandwidth trade-off region ${\mathcal{R}}_{n,d}({\overline{B}}_1,\dots ,{\overline{B}}_d)$ of the $(n,d)$ MDC-R problem is simply ${\mathcal{R}}_{n,d,0}({\overline{B}}_1,\dots ,{\overline{B}}_d)$ for any given normalized message-rate tuple $({\overline{B}}_1,\dots ,{\overline{B}}_d)$,

(2)

the achievable normalized storage-capacity repair-bandwidth trade-off region ${\mathcal{R}}_{n,k,d,\ell }$ of the $(n,k,d,\ell )$ SRC problem is simply ${\mathcal{R}}_{n,d,\ell }(0,\dots ,0,{\overline{B}}_k=1,0,\dots ,0)$,

(3)

the achievable normalized storage-capacity repair-bandwidth trade-off region ${\mathcal{R}}_{n,k,d}$ of the $(n,k,d)$ RC problem is simply ${\mathcal{R}}_{n,d}(0,\dots ,0,{\overline{B}}_k=1,0,\dots ,0)$ or, equivalently, ${\mathcal{R}}_{n,k,d,0}$.

Given these connections, our problem formulation can be viewed as providing a unified framework to investigate these closely-related problems.

A simple and natural strategy for constructing a code for the $(n,d,\ell )$ MDC-SR problem is to use to an $(n,j,d,\ell )$ SRC to encode the message ${\mathsf{M}}_j$ separately for each $j\in [\ell +1:d]$. Since the coded data are kept separate during the encoding, decoding and repair processes, we have

$$\begin{array}{c}\hfill K=\prod _{j=\ell +1}^d{K}_j,T=\prod _{j=\ell +1}^d{T}_j,\mathrm{and}S=\prod _{j=\ell +1}^d{S}_j.\end{array}$$

Thus, for the general MDC-SR problem, the separate coding normalized storage-capacity repair-bandwidth trade-off region ${\widehat{\mathcal{R}}}_{n,d,\ell }({\overline{B}}_{\ell +1},\dots ,{\overline{B}}_d)$ for a fixed normalized message-rate tuple $({\overline{B}}_{\ell +1},\dots ,{\overline{B}}_d)$ is given by:

$$\begin{array}{c}\hfill \left(\left(\sum _{j=\ell +1}^d{\overline{\alpha }}_j{\overline{B}}_j,\sum _{j=\ell +1}^d{\overline{\beta }}_j{\overline{B}}_j\right):({\overline{\alpha }}_j,{\overline{\beta }}_j)\in {\mathcal{R}}_{n,j,d,\ell }\right).\end{array}$$

(5)

As mentioned previously, when $\ell =0$, the repair secrecy requirement (4) degenerates, and the $(n,d,\ell )$ MDC-SR problem reduces to the $(n,d)$ MDC-R problem. In this case, it was shown in [22] that any achievable normalized message-rate storage-capacity repair-bandwidth tuple $({\overline{B}}_1,\dots ,{\overline{B}}_d,\overline{\alpha },\overline{\beta })\in {\mathcal{R}}_{n,d}$ must satisfy:

$$\begin{array}{cc}\hfill \overline{\beta }& \ge \sum _{j=1}^d{T}_{d,j}^{-1}{\overline{B}}_j,\hfill \end{array}$$

(6)

$$\begin{array}{cc}\hfill \mathrm{and}\overline{\alpha }+\frac{d(d-1)}{2}\overline{\beta }& \ge \frac{d(d+1)}{2}\sum _{j=1}^d{T}_{d,j}^{-1}{\overline{B}}_j,\hfill \end{array}$$

(7)

where $T_{d,j}:={\sum }_{t=1}^j(d+1-t)$. When set as equalities, the intersection of (6) and (7) is given by:

$$\begin{array}{cc}\hfill \left(\overline{\alpha },\overline{\beta }\right)& =\left(d\sum _{j=1}^d{T}_{d,j}^{-1}{\overline{B}}_j,\sum _{j=1}^d{T}_{d,j}^{-1}{\overline{B}}_j\right).\hfill \end{array}$$

For any $j\in [1:d]$, the MBR point for the $(n,j,d)$ RC problem can be written as [8]

$$\begin{array}{c}\hfill \left(d{T}_{d,j}^{-1},T_{d,j}^{-1}\right)\in {\mathcal{R}}_{n,j,d}.\end{array}$$

(8)

We may thus conclude immediately from (5) (with $\ell =0$) that separate coding can achieve the MBR point for the general MDC-R problem.

Figure 1 shows the optimal trade-off curve between the normalized storage-capacity and repair-bandwidth and the best possible trade-offs that can be achieved by separate coding for the $(4,3)$ MDC-R problem with $({\overline{B}}_1,{\overline{B}}_2,{\overline{B}}_3)=(0,1/3,2/3)$ [21]. Clearly, for this example, separate coding is strictly suboptimal when $\overline{\alpha }\in (5/12,1/2)$. On the other hand, when $\overline{\alpha }\le 5/12$ or $\overline{\alpha }\ge 1/2$, separate coding can, in fact, achieve the optimal trade-offs. In particular, separate encoding can achieve the MSR point $(7/18,11/36)$ and the MBR point $(8/15,8/45)$. In the same figure, the outer bounds (6) and (7) have also been plotted. As illustrated, they intersect precisely at the MBR point $(8/15,8/45)$. Notice that, for this example at least, the outer bound (7) is tight only at the MBR point.

3. Main Results

Our main result of the paper is to show that the optimality of separate coding in terms of achieving the MBR point of the normalized storage-capacity repair-bandwidth trade-off region extends more generally from the MDC-R problem to the MDC-SR problem. The results are summarized in the following theorem.

Theorem 1.

For the general MDC-SR problem, any achievable normalized message-rate storage-capacity repair-bandwidth tuple $({\overline{B}}_{\ell +1},\dots ,{\overline{B}}_d,\overline{\alpha },\overline{\beta })\in {\mathcal{R}}_{n,d,\ell }$ must satisfy:

$$\begin{array}{cc}\hfill \overline{\beta }& \ge \sum _{j=\ell +1}^d{T}_{d,j,\ell }^{-1}{\overline{B}}_j,\hfill \end{array}$$

(9)

$$\begin{array}{cc}\hfill and\overline{\alpha }+(d(d-\ell )-\ell )\overline{\beta }& \ge (d-\ell )(d+1)\sum _{j=\ell +1}^d{T}_{d,j,\ell }^{-1}{\overline{B}}_j,\hfill \end{array}$$

(10)

where $T_{d,k,\ell }:={\sum }_{t=\ell +1}^k(d+1-t)$. When set as equalities, the intersection of (9) and (10) is given by:

$$\begin{array}{cc}\hfill \left(\overline{\alpha },\overline{\beta }\right)& =\left(d\sum _{j=\ell +1}^d{T}_{d,j,\ell }^{-1}{\overline{B}}_j,\sum _{j=\ell +1}^d{T}_{d,j,\ell }^{-1}{\overline{B}}_j\right).\hfill \end{array}$$

For any $j\in [\ell +1:d]$, the SRK point for the $(n,j,d,\ell )$ SRC problem can be written as [25]:

$$\begin{array}{c}\hfill (d{T}_{d,j,\ell }^{-1},T_{d,j,\ell }^{-1})\in {\mathcal{R}}_{n,j,d,\ell }.\end{array}$$

(11)

We may thus conclude immediately from (5) that separate coding can achieve the MBR point for the general MDC-SR problem.

The following corollary follows immediately from Theorem 1 by setting ${\overline{B}}_j=0$ for all $j\ne k$.

Corollary 1.

For the general SRC problem, any achievable normalized storage-capacity repair-bandwidth tuple $(\overline{\alpha },\overline{\beta })\in {\mathcal{R}}_{n,k,d,\ell }$ must satisfy:

$$\begin{array}{cc}\hfill \overline{\beta }& \ge T_{d,k,\ell }^{-1},\hfill \end{array}$$

(12)

$$\begin{array}{cc}\hfill and\overline{\alpha }+(d(d-\ell )-\ell )\overline{\beta }& \ge (d-\ell )(d+1)T_{d,k,\ell }^{-1}.\hfill \end{array}$$

(13)

When set as equalities, the intersection of (12) and (13) is precisely the SRK point (11) (with $j=k$), showing that the SRK point is, in fact, the MBR point of the achievable normalized storage-capacity repair-bandwidth trade-off region for the general SRC problem.

While the outer bound (12) is known [23,24,30], the outer bound (13) is new. Figure 2 shows the optimal trade-off curve between the normalized storage-capacity and repair-bandwidth for the $(7,6,6,1)$ SRC problem. Notice that, for this example, the SRK point $(2/5,1/15)$ is, in fact, the MBR point even though the trade-off region has two corner points. In the same figure, the outer bunds (12) and (13) have also been plotted. As illustrated, when set as equalities, they intersect precisely at the MBR/SRK point $(2/5,1/15)$. Notice that for this example at least, the outer bound (13) is tight only at the MBR/SRK point.

As a final remark, we mention here that when $\ell =0$, the outer bound (9) is reduced to (6) for the $(n,d)$ MDC-R problem by the fact that $T_{n,d,0}=T_{n,d}$. However, when $\ell =0$, the outer bound (10) is reduced to:

$$\begin{array}{cc}\hfill \overline{\alpha }+d^2\overline{\beta }& \ge d(d+1)\sum _{j=1}^d{T}_{d,j}^{-1}{\overline{B}}_j,\hfill \end{array}$$

(14)

which is weaker than the outer bound (7) by the fact that $d^2>\frac{d(d-1)}{2}$. Figure 1 shows the outer bound (14) for the $(4,3)$ MDC-R problem with $({\overline{B}}_1,{\overline{B}}_2,{\overline{B}}_3)=(0,1/3,2/3)$. As illustrated, (14) is weaker than (7), and both are only tight at the MBR point $(8/15,8/45)$.

4. Proof of the Main Results

Let us first outline the main ingredients for proving the outer bounds (9) and (10).

(1)

Total number of nodes. To prove the outer bounds (9) and (10), let us first note that these bounds are independent of the total number of storage nodes n in the system. Therefore, in our proof, we only need to consider the cases where $n=d+1$—for the cases where $n>d+1$, since any subsystem consisting of $d+1$ out of the total n storage nodes must give rise to a $(d+1,d,\ell )$ MDC-SR problem. Therefore, these outer bounds must apply as well. When $n=d+1$, any repair group $\mathcal{B}$ of size d is uniquely determined by the node j to be repaired, i.e., $\mathcal{B}=[1:n]\setminus \left\{j\right\}$, and hence can be dropped from the notation ${\mathsf{S}}_{i\to j}^{\mathcal{B}}$ without causing any confusion.

(2)

Code symmetry. Due to the built-in symmetry of the problem, to prove the outer bounds (9) and (10), we only need to consider the so-called symmetrical codes [10] for which the joint entropy of any subset of random variables from

$$\begin{array}{c}\left(({\mathsf{M}}_1,\dots ,{\mathsf{M}}_d),\mathsf{K},\right.\hfill \\ \left.({\mathsf{W}}_i:i\in [1:n]),({\mathsf{S}}_{i\to j}:i,j\in [1:n],i\ne j)\right)\hfill \end{array}$$

remains unchanged under any permutation over the storage-node indices.

(3)

Key collections of random variables. Focusing on the symmetrical $(n=d+1,d,N_1,\dots ,N_d,K,T,S)$ codes, the following collections of random variables play a key role in our proof:

$$\begin{array}{c}{\mathsf{M}}_{\mathcal{A}}:=({\mathsf{M}}_i:i\in \mathcal{A}),\mathcal{A}\subseteq [1:d],\hfill \\ {\mathsf{M}}^{(m)}:={\mathsf{M}}_{[1:m]},m\in [1:d],\hfill \\ {\mathsf{W}}_{\mathcal{A}}:=\left({\mathsf{W}}_i:i\in \mathcal{A}\right),\mathcal{A}\subseteq [1:n],\hfill \\ {\mathsf{S}}_{i\to \mathcal{B}}:=\left({\mathsf{S}}_{i\to j}:j\in \mathcal{B}\right),i\in [1:n],\mathcal{B}\subseteq [1:n]\setminus \left\{i\right\},\hfill \\ {\mathsf{S}}_{\mathcal{B}\to j}:=\left({\mathsf{S}}_{i\to j}:i\in \mathcal{B}\right),j\in [1:n],\mathcal{B}\subseteq [1:n]\setminus \left\{j\right\},\hfill \\ {\mathsf{S}}_{\to j}:={\mathsf{S}}_{[1:j-1]\cup [j+1:n]\to j},j\in [1:n],\hfill \\ {\mathsf{S}}_{\to \mathcal{B}}:=\left({\mathsf{S}}_{\to j}:j\in \mathcal{B}\right),\mathcal{B}\subseteq [1:n],\hfill \\ {\underline{\mathsf{S}}}_{\to j}:={\mathsf{S}}_{[1:j-1]\to j},j\in [1:n],\hfill \\ {\underline{\mathsf{S}}}_{\to \mathcal{B}}:=({\underline{\mathsf{S}}}_{\to j}:j\in \mathcal{B}),\mathcal{B}\subseteq [1:n],\hfill \\ {\overline{\mathsf{S}}}_{\to j}:={\mathsf{S}}_{[j+1:n]\to j},j\in [1:n],\hfill \\ {\overline{\mathsf{S}}}_{\to \mathcal{B}}:=({\overline{\mathsf{S}}}_{\to j}:j\in \mathcal{B}),\mathcal{B}\subseteq [1:n],\hfill \\ {\mathsf{U}}^{(t,s)}:=({\mathsf{W}}_{[1:t]},{\overline{\mathsf{S}}}_{\to [t+1:s]}),s\in [1:n],t\in [0:s],\hfill \\ {\mathsf{U}}^{(s)}:={\mathsf{U}}^{(0,s)}.\hfill \end{array}$$

These collections of random variables have also been used in [22,30].

An important part of the proof is to understand the relations between the collections of random variables defined above, and to use them to derive the desired converse results. We shall discuss this next.

4.1. Technical Lemmas

Lemma 1.

For any $(n=d+1,d,N_1,\dots ,N_d,K,T,S)$ code that satisfies the node regeneration requirement (3), $({\underline{\mathsf{S}}}_{\to [t+1:s]},{\mathsf{W}}_{[t+1:s]})$ is a function of ${\mathsf{U}}^{(t,s)}$ for any $s\in [1:n]$ and $t\in [0:s-1]$.

Proof of Lemma 1.

Fix $s\in [1:n]$ and $t\in [0:s-1]$. Let us first note that ${\underline{\mathsf{S}}}_{\to t+1}$ is a function of ${\mathsf{W}}_{[1:t]}$. As a result, ${\mathsf{S}}_{\to t+1}=({\underline{\mathsf{S}}}_{\to t+1},{\overline{\mathsf{S}}}_{\to t+1})$ is a function of ${\mathsf{U}}^{(t,s)}$. It thus follows immediately from the node regeneration requirement (3) that ${\mathsf{W}}_{t+1}$ is a function of ${\mathsf{U}}^{(t,s)}$. Similarly and inductively, it can be shown that $({\underline{\mathsf{S}}}_{\to j},{\mathsf{W}}_j)$ is a function of ${\mathsf{U}}^{(t,s)}$ for all $j\in [t+2:s]$. This completes the proof of the lemma. ☐

The above lemma demonstrates the “compactness” of ${\mathsf{U}}^{(t,s)}$ and has a number of direct consequences. For example, for any fixed $s\in [1:n]$, it is clear from Lemma 1 that ${\mathsf{U}}^{(t_2,s)}$ is a function of ${\mathsf{U}}^{(t_1,s)}$ and hence $H({\mathsf{U}}^{(t_2,s)})\le H({\mathsf{U}}^{(t_1,s)})$ for any $0\le t_1\le t_2\le s-1$.

The following lemma plays the key role in proving the outer bounds (6) and (7). The proof is rather long and is deferred to the Appendix to enhance the flow of the paper.

Lemma 2 (Exchange lemma).

For any symmetrical $(n=d+1,d,N_1,\dots ,N_d,K,T,S)$ code that satisfies the node regeneration requirement (3), we have

$$\begin{array}{c}\frac{d+1-j}{d-m}H({\mathsf{U}}^{(i,m)}|{\mathsf{M}}^{(m)})+H({\mathsf{U}}^{(i^{\prime },j)}|{\mathsf{M}}^{(m)})\hfill \\ \ge \frac{d+1-j}{d-m}H({\mathsf{U}}^{(i,m+1)}|{\mathsf{M}}^{(m)})+H({\mathsf{U}}^{(i^{\prime },j-1)}|{\mathsf{M}}^{(m)})\hfill \end{array}$$

(15)

for any $m\in [1:d-1]$, $i\in [0:m-1]$, $i^{\prime }\in [0:i]$, and $j\in [i^{\prime }+1:m-i+i^{\prime }+1]$.

Corollary 2.

For any symmetrical $(n=d+1,d,N_1,\dots ,N_d,K,T,S)$ code that satisfies the node regeneration requirement (3), we have

$$\begin{array}{c}{T}_{d,m,\ell }^{-1}H({\mathsf{U}}^{(m)}|{\mathsf{M}}^{(m)})\ge T_{d,m+1,\ell }^{-1}H({\mathsf{U}}^{(m+1)}|{\mathsf{M}}^{(m)})+\hfill \\ (T_{d,m,\ell }^{-1}-T_{d,m+1,\ell }^{-1})H({\mathsf{U}}^{(\ell )}|{\mathsf{M}}^{(m)})\hfill \end{array}$$

(16)

for any $\ell \in [0:d-1]$ and $m\in [\ell +1:d-1]$.

Proof of Corollary 2.

Fix $\ell \in [0:d-1]$ and $m\in [\ell +1:d-1]$. Setting $i=i^{\prime }=0$ in (15), we have

$$\begin{array}{c}\frac{d+1-j}{d-m}H({\mathsf{U}}^{(m)}|{\mathsf{M}}^{(m)})+H({\mathsf{U}}^{(j)}|{\mathsf{M}}^{(m)})\hfill \\ \ge \frac{d+1-j}{d-m}H({\mathsf{U}}^{(m+1)}|{\mathsf{M}}^{(m)})+H({\mathsf{U}}^{(j-1)}|{\mathsf{M}}^{(m)})\hfill \end{array}$$

(17)

for any $j\in [1:m+1]$. Add the inequalities (17) for $j\in [\ell +1:m]$ and cancel the common term ${\sum }_{j=\ell +1}^{m-1}H({\mathsf{U}}^{(j)}|{\mathsf{M}}^{(m)})$ from both sides. We have

$$\begin{array}{c}\frac{T_{d,m,\ell }}{d-m}H({\mathsf{U}}^{(m)}|{\mathsf{M}}^{(m)})+H({\mathsf{U}}^{(m)}|{\mathsf{M}}^{(m)})\hfill \\ \ge \frac{T_{d,m,\ell }}{d-m}H({\mathsf{U}}^{(m+1)}|{\mathsf{M}}^{(m)})+H({\mathsf{U}}^{(\ell )}|{\mathsf{M}}^{(m)}),\hfill \end{array}$$

which can be equivalently written as

$$\begin{array}{c}\frac{T_{d,m+1,\ell }}{d-m}H({\mathsf{U}}^{(m)}|{\mathsf{M}}^{(m)})\hfill \\ \ge \frac{T_{d,m,\ell }}{d-m}H({\mathsf{U}}^{(m+1)}|{\mathsf{M}}^{(m)})+H({\mathsf{U}}^{(\ell )}|{\mathsf{M}}^{(m)})\hfill \end{array}$$

(18)

by the fact that $T_{d,m,\ell }+(d-m)=T_{d,m+1,\ell }$. Multiplying both sides of (18) by

$$\frac{d-m}{T_{d,m+1,\ell }{T}_{d,m,\ell }}=T_{d,m,\ell }^{-1}-T_{d,m+1,\ell }^{-1}$$

completes the proof of (16). ☐

Corollary 3.

For any symmetrical $(n=d+1,d,N_1,\dots ,N_d,K,T,S)$ code that satisfies the node regeneration requirement (3), we have

$$\begin{array}{cc}\hfill H& ({\mathsf{U}}^{(1,m)}|{\mathsf{M}}^{(m)})+(d-m)T_{d,m,\ell }^{-1}H({\mathsf{U}}^{(m)}|{\mathsf{M}}^{(m)})\hfill \\ & \ge H({\mathsf{U}}^{(1,m+1)}|{\mathsf{M}}^{(m)})+(d-m)T_{d,m,\ell }^{-1}H({\mathsf{U}}^{(\ell )}|{\mathsf{M}}^{(m)})\hfill \end{array}$$

(19)

for any $\ell \in [0:d-1]$ and $m\in [\ell +1:d-1]$.

Proof of Corollary 3.

Fix $\ell \in [0:d-1]$ and $m\in [\ell +1:d-1]$. Set $i=1$ and $i^{\prime }=0$ in (15). We have

$$\begin{array}{c}\frac{d+1-j}{d-m}H({\mathsf{U}}^{(1,m)}|{\mathsf{M}}^{(m)})+H({\mathsf{U}}^{(j)}|{\mathsf{M}}^{(m)})\hfill \\ \ge \frac{d+1-j}{d-m}H({\mathsf{U}}^{(1,m+1)}|{\mathsf{M}}^{(m)})+H({\mathsf{U}}^{(j-1)}|{\mathsf{M}}^{(m)})\hfill \end{array}$$

(20)

for any $j\in [1:m]$. Add the inequalities (20) for $j\in [\ell +1:m]$ and cancel the common term ${\sum }_{j=\ell +1}^{m-1}H({\mathsf{U}}^{(j)}|{\mathsf{M}}^{(m)})$ from both sides. We have

$$\begin{array}{c}\frac{T_{d,m,\ell }}{d-m}H({\mathsf{U}}^{(1,m)}|{\mathsf{M}}^{(m)})+H({\mathsf{U}}^{(m)}|{\mathsf{M}}^{(m)})\hfill \\ \ge \frac{T_{d,m,\ell }}{d-m}H({\mathsf{U}}^{(1,m+1)}|{\mathsf{M}}^{(m)})+H({\mathsf{U}}^{(\ell )}|{\mathsf{M}}^{(m)}).\hfill \end{array}$$

(21)

Multiplying both sides of (21) by $(d-m)T_{d,m,\ell }^{-1}$ completes the proof of (19). ☐

4.2. The Proof

Consider a symmetrical $(n=d+1,d,1,\dots ,1,N_{\ell +1},\dots ,N_d,K,T,S)$ regenerating code that satisfies the rate normalization requirement (1), the message recovery requirement (2), the node regeneration requirement (3), and the repair secrecy requirement (4). Let us first prove a few intermediate results. The outer bounds (9) and (10) will then follow immediately.

Proposition 1.

$$\begin{array}{c}\frac{1}{d-\ell }H({\mathsf{U}}^{(\ell +1)})\ge \sum _{j=\ell +1}^m{T}_{d,j,\ell }^{-1}{B}_j+\hfill \\ T_{d,m,\ell }^{-1}H({\mathsf{U}}^{(m)}|{\mathsf{M}}_{[\ell +1:m]})+\left(\frac{1}{d-\ell }-T_{d,m,\ell }^{-1}\right)H({\mathsf{U}}^{(\ell )})\hfill \end{array}$$

(22)

for any $m\in [\ell +1:d]$. Consequently,

$$\begin{array}{c}\hfill \frac{1}{d-\ell }H({\mathsf{U}}^{(\ell +1)})\ge \sum _{j=\ell +1}^d{T}_{d,j,\ell }^{-1}{B}_j+\frac{1}{d-\ell }H({\mathsf{U}}^{(\ell )}).\end{array}$$

(23)

Proof of Proposition 1.

To see (22), consider proof by induction. For the base case with $m=\ell +1$, we have

$$\begin{array}{cc}\hfill \frac{1}{d-\ell }H({\mathsf{U}}^{(\ell +1)})& \stackrel{(a)}{=}\frac{1}{d-\ell }H({\mathsf{U}}^{(\ell +1)},{\mathsf{M}}_{\ell +1})\hfill \\ & \stackrel{(b)}{=}\frac{1}{d-\ell }\left(H({\mathsf{M}}_{\ell +1})+H({\mathsf{U}}^{(\ell +1)}|{\mathsf{M}}_{\ell +1})\right)\hfill \\ & \stackrel{(c)}{=}\frac{1}{d-\ell }\left(B_{\ell +1}+H({\mathsf{U}}^{(\ell +1)}|{\mathsf{M}}_{\ell +1})\right)\hfill \\ & \stackrel{(d)}{=}{T}_{d,\ell +1,\ell }^{-1}{B}_{\ell +1}+T_{d,\ell +1,\ell }^{-1}H({\mathsf{U}}^{(\ell +1)}|{\mathsf{M}}_{\ell +1}),\hfill \end{array}$$

where $(a)$ follows from the fact that ${\mathsf{M}}_{\ell +1}$ is a function of ${\mathsf{W}}_{[1:\ell +1]}$, which is a function of ${\mathsf{U}}^{(\ell +1)}$ by Lemma 1; $(b)$ follows from the chain rule for entropy; $(c)$ follows from the fact that $H({\mathsf{M}}_{\ell +1})=B_{\ell +1}$; and $(d)$ follows from the fact that $T_{d,\ell +1,\ell }=d-\ell$. Assuming that (22) holds for some $m\in [\ell +1:d-1]$, we have

$$\begin{array}{c}\frac{1}{d-\ell }H({\mathsf{U}}^{(\ell +1)})\hfill \\ \stackrel{(a)}{\ge }\sum _{j=\ell +1}^m{T}_{d,j,\ell }^{-1}{B}_j+T_{d,m,\ell }^{-1}H({\mathsf{U}}^{(m)}|{\mathsf{M}}_{[\ell +1:m]})+\hfill \\ \left(\frac{1}{d-\ell }-T_{d,m,\ell }^{-1}\right)H({\mathsf{U}}^{(\ell )})\hfill \\ \stackrel{(b)}{\ge }\sum _{j=\ell +1}^m{T}_{d,j,\ell }^{-1}{B}_j+T_{d,m+1,\ell }^{-1}H({\mathsf{U}}^{(m+1)}|{\mathsf{M}}_{[\ell +1:m]})+\hfill \\ \left(\frac{1}{d-\ell }-T_{d,m+1,\ell }^{-1}\right)H({\mathsf{U}}^{(\ell )})\hfill \\ \stackrel{(c)}{\ge }\sum _{j=\ell +1}^m{T}_{d,j,\ell }^{-1}{B}_j+T_{d,m+1,\ell }^{-1}H({\mathsf{U}}^{(m+1)},{\mathsf{M}}_{m+1}|{\mathsf{M}}_{[\ell +1:m]})+\hfill \\ \left(\frac{1}{d-\ell }-T_{d,m+1,\ell }^{-1}\right)H({\mathsf{U}}^{(\ell )})\hfill \\ \stackrel{(d)}{=}\sum _{j=\ell +1}^m{T}_{d,j,\ell }^{-1}{B}_j+T_{d,m+1,\ell }^{-1}H({\mathsf{M}}_{m+1}|{\mathsf{M}}_{[\ell +1:m]})+\hfill \\ T_{d,m+1,\ell }^{-1}H({\mathsf{U}}^{(m+1)}|{\mathsf{M}}_{[\ell +1:m+1]})+\hfill \\ \left(\frac{1}{d-\ell }-T_{d,m+1,\ell }^{-1}\right)H({\mathsf{U}}^{(\ell )})\hfill \\ \stackrel{(e)}{=}\sum _{j=\ell +1}^m{T}_{d,j,\ell }^{-1}{B}_j+T_{d,m+1,\ell }^{-1}{B}_{m+1}+\hfill \\ T_{d,m+1,\ell }^{-1}H({\mathsf{U}}^{(m+1)}|{\mathsf{M}}_{[\ell +1:m+1]})+\hfill \\ \left(\frac{1}{d-\ell }-T_{d,m+1,\ell }^{-1}\right)H({\mathsf{U}}^{(\ell )})\hfill \\ =\sum _{j=\ell +1}^{m+1}{T}_{d,j,\ell }^{-1}+T_{d,m+1,\ell }^{-1}H({\mathsf{U}}^{(m+1)}|{\mathsf{M}}_{[\ell +1:m+1]})+\hfill \\ \left(\frac{1}{d-\ell }-T_{d,m+1,\ell }^{-1}\right)H({\mathsf{U}}^{(\ell )}),\hfill \end{array}$$

where $(a)$ follows from the induction assumption; $(b)$ follows from Corollary 2; $(c)$ follows from the fact that ${\mathsf{M}}_{m+1}$ is a function of ${\mathsf{W}}_{[1:m+1]}$, which is a function of ${\mathsf{U}}^{(m+1)}$ by Lemma 1; $(d)$ follows from the chain rule for entropy; and $(e)$ follows from the facts that ${\mathsf{M}}_{m+1}$ is independent of ${\mathsf{M}}_{[\ell +1:m]}$ and that $H({\mathsf{M}}_{m+1})=B_{m+1}$. This completes the induction step and hence the proof of (22).

To see (23), simply set $m=d$ in (22). We have

$$\begin{array}{c}\frac{1}{d-\ell }H({\mathsf{U}}^{(\ell +1)})\ge \sum _{j=\ell +1}^d{T}_{d,j,\ell }^{-1}{B}_j+\hfill \\ T_{d,d,\ell }^{-1}H({\mathsf{U}}^{(d)}|{\mathsf{M}}_{[\ell +1:d]})+\left(\frac{1}{d-\ell }-T_{d,d,\ell }^{-1}\right)H({\mathsf{U}}^{(\ell )}).\hfill \end{array}$$

(24)

Note that

$$\begin{array}{c}\hfill H({\mathsf{U}}^{(d)}|{\mathsf{M}}_{[\ell +1:d]})\ge H({\mathsf{U}}^{(\ell )}|{\mathsf{M}}_{[\ell +1:d]})=H({\mathsf{U}}^{(\ell )})\end{array}$$

(25)

where the last equality follows from the fact that $I({\mathsf{U}}^{(\ell )};{\mathsf{M}}_{[\ell +1:d]})=0$ by the repair secrecy requirement (4). Substituting (25) into (24) completes the proof of (23). ☐

Proposition 2.

$$\begin{array}{c}\hfill H({\mathsf{S}}_{d+1\to [1:\ell ]})+(d(d-\ell )-\ell )\beta +dH({\mathsf{U}}^{(\ell )})\ge dH({\mathsf{U}}^{(\ell +1)}).\end{array}$$

(26)

Proof of Proposition 2.

First note that, for any $m\in [1:\ell ]$, we have

$$\begin{array}{cc}\hfill H& ({\mathsf{S}}_{d+1\to [1:m]})+H({\mathsf{U}}^{(\ell )})\hfill \\ & \stackrel{(a)}{=}H({\mathsf{S}}_{d+1\to [1:m-1]\cup \{\ell +1\}})+H({\mathsf{U}}^{(\ell )})\hfill \\ & \stackrel{(b)}{\ge }H({\mathsf{S}}_{d+1\to [1:m-1]})+H({\mathsf{U}}^{(\ell )},{\mathsf{S}}_{d+1\to \ell +1}),\hfill \end{array}$$

(27)

where $(a)$ follows from the fact that $H({\mathsf{S}}_{d+1\to [1:m]})=H({\mathsf{S}}_{d+1\to [1:m-1]\cup \{\ell +1\}})$ due to the symmetrical code that we consider, and $(b)$ follows from the submodularity of the entropy function. Add (27) over $m\in [1:\ell ]$ and cancel ${\sum }_{m=1}^{\ell -1}H({\mathsf{S}}_{d+1\to [1:m]})$ from both sides. We have

$$\begin{array}{c}\hfill H({\mathsf{S}}_{d+1\to [1:\ell ]})+\ell H({\mathsf{U}}^{(\ell )})\ge \ell H({\mathsf{U}}^{(\ell )},{\mathsf{S}}_{d+1\to \ell +1}).\end{array}$$

(28)

It follows that

$$\begin{array}{cc}\hfill H& ({\mathsf{S}}_{d+1\to [1:\ell ]})+(d(d-\ell )-\ell )\beta +dH({\mathsf{U}}^{(\ell )})\hfill \\ & =\left(H({\mathsf{S}}_{d+1\to [1:\ell ]})+\ell H({\mathsf{U}}^{(\ell )})\right)+\hfill \\ & (d(d-\ell )-\ell )\beta +(d-\ell )H({\mathsf{U}}^{(\ell )})\hfill \\ & \stackrel{(a)}{\ge }\ell H({\mathsf{U}}^{(\ell )},{\mathsf{S}}_{d+1\to \ell +1})+(d(d-\ell )-\ell )\beta +(d-\ell )H({\mathsf{U}}^{(\ell )})\hfill \\ & =\ell \left((d-\ell -1)\beta +H({\mathsf{U}}^{(\ell )},{\mathsf{S}}_{d+1\to \ell +1})\right)+\hfill \\ & (d-\ell )\left((d-\ell )\beta +H({\mathsf{U}}^{(\ell )})\right)\hfill \\ & \stackrel{(b)}{\ge }\ell \left(H({\mathsf{S}}_{[\ell +2:d]\to \ell +1})+H({\mathsf{U}}^{(\ell )},{\mathsf{S}}_{d+1\to \ell +1})\right)+\hfill \\ & (d-\ell )\left(H({\overline{\mathsf{S}}}_{\to \ell +1})+H({\mathsf{U}}^{(\ell )})\right)\hfill \\ & \stackrel{(c)}{\ge }\ell H({\mathsf{U}}^{(\ell +1)})+(d-\ell )H({\mathsf{U}}^{(\ell +1)})\hfill \\ & =dH({\mathsf{U}}^{(\ell +1)}),\hfill \end{array}$$

where $(a)$ follows from (28); $(b)$ follows from the fact that $H({\mathsf{S}}_{[\ell +2:d]\to \ell +1})\le (d-\ell -1)\beta$ and that $H({\overline{\mathsf{S}}}_{\to \ell +1})\le (d-\ell )\beta$; and $(c)$ follows from the fact that $H({\mathsf{S}}_{[\ell +2:d]\to \ell +1})+H({\mathsf{U}}^{(\ell )},{\mathsf{S}}_{d+1\to \ell +1})\ge H({\mathsf{U}}^{(\ell +1)})$ and that $H({\overline{\mathsf{S}}}_{\to \ell +1})+H({\mathsf{U}}^{(\ell )})\ge H({\mathsf{U}}^{(\ell +1)})$ by the union bound on entropy. This completes the proof of the proposition. ☐

Proposition 3.

$$\begin{array}{c}H({\mathsf{U}}^{(1,m)})+\frac{d-m}{d-\ell }H({\mathsf{U}}^{(\ell +1)})\hfill \\ \ge (d-m)\sum _{j=\ell +1}^m{T}_{d,j,\ell }^{-1}{B}_j+H({\mathsf{U}}^{(1,m+1)})+\frac{d-m}{d-\ell }H({\mathsf{U}}^{(\ell )})\hfill \end{array}$$

(29)

for any $m\in [\ell +1,d-1]$. Consequently,

$$\begin{array}{c}H({\mathsf{U}}^{(1,\ell +1)})+\frac{T_{d,d,\ell +1}}{d-\ell }H({\mathsf{U}}^{(\ell +1)})\hfill \\ \ge T_{d,d,\ell }\sum _{j=\ell +1}^d{T}_{d,j,\ell }^{-1}{B}_j+\frac{T_{d,d,\ell }}{d-\ell }H({\mathsf{U}}^{(\ell )}).\hfill \end{array}$$

(30)

Proof of Proposition 3.

To see (29), note that, for any $m\in [\ell +1,d-1]$, we have

$$\begin{array}{c}H({\mathsf{U}}^{(1,m)}|{\mathsf{M}}_{[\ell +1:m]})+\frac{d-m}{d-\ell }H({\mathsf{U}}^{(\ell +1)})\hfill \\ \stackrel{(a)}{\ge }H({\mathsf{U}}^{(1,m)}|{\mathsf{M}}_{[\ell +1:m]})+(d-m)\left(\sum _{j=\ell +1}^m{T}_{d,j,\ell }^{-1}{B}_j+\right.\hfill \\ \left.T_{d,m,\ell }^{-1}H({\mathsf{U}}^{(m)}|{\mathsf{M}}_{[\ell +1:m]})+\left(\frac{1}{d-\ell }-T_{d,m,\ell }^{-1}\right)H({\mathsf{U}}^{(\ell )})\right)\hfill \\ =H({\mathsf{U}}^{(1,m)}|{\mathsf{M}}_{[\ell +1:m]})+(d-m)T_{d,m,\ell }^{-1}H({\mathsf{U}}^{(m)}|{\mathsf{M}}_{[\ell +1:m]})+\hfill \\ (d-m)\left(\sum _{j=\ell +1}^m{T}_{d,j,\ell }^{-1}{B}_j+\left(\frac{1}{d-\ell }-T_{d,m,\ell }^{-1}\right)H({\mathsf{U}}^{(\ell )})\right)\hfill \\ \stackrel{(b)}{\ge }H({\mathsf{U}}^{(1,m+1)}|{\mathsf{M}}_{[\ell +1:m]})+(d-m)T_{d,m,\ell }^{-1}H({\mathsf{U}}^{(\ell )}|{\mathsf{M}}_{[\ell +1:m]})+\hfill \\ (d-m)\left(\sum _{j=\ell +1}^m{T}_{d,j,\ell }^{-1}{B}_j+\left(\frac{1}{d-\ell }-T_{d,m,\ell }^{-1}\right)H({\mathsf{U}}^{(\ell )})\right)\hfill \\ \stackrel{(c)}{=}H({\mathsf{U}}^{(1,m+1)}|{\mathsf{M}}_{[\ell +1:m]})+(d-m)T_{d,m,\ell }^{-1}H({\mathsf{U}}^{(\ell )})+\hfill \\ (d-m)\left(\sum _{j=\ell +1}^m{T}_{d,j,\ell }^{-1}{B}_j+\left(\frac{1}{d-\ell }-T_{d,m,\ell }^{-1}\right)H({\mathsf{U}}^{(\ell )})\right)\hfill \\ =H({\mathsf{U}}^{(1,m+1)}|{\mathsf{M}}_{[\ell +1:m]})+(d-m)\sum _{j=\ell +1}^m{T}_{d,j,\ell }^{-1}{B}_j+\hfill \\ \frac{d-m}{d-\ell }H({\mathsf{U}}^{(\ell )}),\hfill \end{array}$$

where $(a)$ follows from (22) of Proposition 1; $(b)$ follows from Corollary 3; and $(c)$ follows from the fact that $I({\mathsf{U}}^{(\ell )};{\mathsf{M}}_{[\ell +1:m]})=0$ due to the repair secrecy requirement (4). Adding $H({\mathsf{M}}_{[\ell +1:m]})$ to both sides and using the facts that

$$\begin{array}{cc}\hfill H({\mathsf{U}}^{(1,m)}|& {\mathsf{M}}_{[\ell +1:m]})+H({\mathsf{M}}_{[\ell +1:m]})\hfill \\ & =H({\mathsf{U}}^{(1,m)},{\mathsf{M}}_{[\ell +1:m]})\stackrel{(a)}{=}H({\mathsf{U}}^{(1,m)})\hfill \end{array}$$

and that

$$\begin{array}{cc}\hfill H({\mathsf{U}}^{(1,m+1)}|& {\mathsf{M}}_{[\ell +1:m]})+H({\mathsf{M}}_{[\ell +1:m]})\hfill \\ \hfill =& H({\mathsf{U}}^{(1,m+1)},{\mathsf{M}}_{[\ell +1:m]})\stackrel{(b)}{=}H({\mathsf{U}}^{(1,m+1)})\hfill \end{array}$$

complete the proof of (29). Here, $(a)$ and $(b)$ are due to the facts that ${\mathsf{M}}_{[\ell +1:m]}$ is a function of ${\mathsf{W}}_{[1:m]}$, which is a function of both ${\mathsf{U}}^{(1,m)}$ and ${\mathsf{U}}^{(1,m+1)}$ by Lemma 1.

To see (30), add (29) over $m\in [\ell +1:d-1]$ and cancel ${\sum }_{m=\ell +2}^{d-1}H({\mathsf{U}}^{(1,m)})$ from both sides of the inequality. We have

$$\begin{array}{c}H({\mathsf{U}}^{(1,\ell +1)})+\frac{T_{d,d,\ell +1}}{d-\ell }H({\mathsf{U}}^{(\ell +1)})\hfill \\ \ge \sum _{m=\ell +1}^{d-1}\left((d-m)\sum _{j=\ell +1}^m{T}_{d,j,\ell }^{-1}{B}_j\right)+\hfill \\ H({\mathsf{U}}^{(1,d)})+\frac{T_{d,d,\ell +1}}{d-\ell }H({\mathsf{U}}^{(\ell )}).\hfill \end{array}$$

(31)

Note that

$$\begin{array}{c}\sum _{m=\ell +1}^{d-1}\left((d-m)\sum _{j=\ell +1}^m{T}_{d,j,\ell }^{-1}{B}_j\right)\hfill \\ =\sum _{j=\ell +1}^{d-1}{T}_{d,j,\ell }^{-1}{B}_j\left(\sum _{m=j}^{d-1}(d-m)\right)=\sum _{j=\ell +1}^{d-1}{T}_{d,j,\ell }^{-1}{T}_{d,d,j}{B}_j.\hfill \end{array}$$

(32)

Furthermore,

$$\begin{array}{cc}\hfill H({\mathsf{U}}^{(1,d)})& \stackrel{(a)}{=}H({\mathsf{U}}^{(1,d)},{\mathsf{M}}_{[\ell +1:d]})\hfill \\ & \stackrel{(b)}{=}H({\mathsf{U}}^{(1,d)}|{\mathsf{M}}_{[\ell +1:d]})+H({\mathsf{M}}_{[\ell +1:d]})\hfill \\ & \stackrel{(c)}{=}H({\mathsf{U}}^{(1,d)}|{\mathsf{M}}_{[\ell +1:d]})+\sum _{j=\ell +1}^d{B}_j\hfill \\ & \stackrel{(d)}{=}H({\mathsf{U}}^{(1,d)},{\mathsf{S}}_{1\to [2:d-1]}|{\mathsf{M}}_{[\ell +1:d]})+\sum _{j=\ell +1}^d{B}_j\hfill \\ & \stackrel{(e)}{=}H({\mathsf{U}}^{(d-1)},{\mathsf{W}}_{d+1}|{\mathsf{M}}_{[\ell +1:d]})+\sum _{j=\ell +1}^d{B}_j\hfill \\ & \ge H({\mathsf{U}}^{(\ell )}|{\mathsf{M}}_{[\ell +1:d]})+\sum _{j=\ell +1}^d{B}_j\hfill \\ & \stackrel{(f)}{=}H({\mathsf{U}}^{(\ell )})+\sum _{j=\ell +1}^d{B}_j,\hfill \end{array}$$

(33)

where $(a)$ follows from the fact that ${\mathsf{M}}_{[\ell +1:d]}$ is a function of ${\mathsf{W}}_{[1:d]}$, which is a function of ${\mathsf{U}}^{(1,d)}$ by Lemma 1; $(b)$ follows from the chain rule for entropy; $(c)$ follows from the fact that $H({\mathsf{M}}_{[\ell +1:d]})={\sum }_{j=\ell +1}^d{B}_j$; $(d)$ follows from the fact that ${\mathsf{S}}_{1\to [2:d-1]}$ is a function of ${\mathsf{W}}_1$ and hence a function of ${\mathsf{U}}^{(1,d)}$; $(e)$ follows from the fact that $H({\mathsf{U}}^{(1,d)},{\mathsf{S}}_{1\to [2:d-1]}|{\mathsf{M}}_{[\ell +1:d]})=H({\mathsf{U}}^{(d-1)},{\mathsf{W}}_{d+1}|{\mathsf{M}}_{[\ell +1:d]})$ due to the symmetrical code that we consider; and $(f)$ follows from the fact that $I({\mathsf{U}}^{(\ell )};{\mathsf{M}}_{[\ell +1:d]})=0$ due to the repair secrecy requirement (4).

Substituting (32) and (33) into (31) gives:

$$\begin{array}{c}H({\mathsf{U}}^{(1,\ell +1)})+\frac{T_{d,d,\ell +1}}{d-\ell }H({\mathsf{U}}^{(\ell +1)})\hfill \\ \ge \sum _{j=\ell +1}^{d-1}{T}_{d,j,\ell }^{-1}{T}_{d,d,j}{B}_j+\sum _{j=\ell +1}^d{B}_j+\left(1+\frac{T_{d,d,\ell +1}}{d-\ell }\right)H({\mathsf{U}}^{(\ell )})\hfill \\ =\sum _{j=\ell +1}^{d-1}{T}_{d,j,\ell }^{-1}(T_{d,d,j}+T_{d,j,\ell })B_j+B_d+\frac{T_{d,d,\ell }}{d-\ell }H({\mathsf{U}}^{(\ell )})\hfill \\ \stackrel{(a)}{=}{T}_{d,d,\ell }\sum _{j=\ell +1}^{d-1}{T}_{d,j,\ell }^{-1}{B}_j+B_d+\frac{T_{d,d,\ell }}{d-\ell }H({\mathsf{U}}^{(\ell )})\hfill \\ =T_{d,d,\ell }\sum _{j=\ell +1}^d{T}_{d,j,\ell }^{-1}{B}_j+\frac{T_{d,d,\ell }}{d-\ell }H({\mathsf{U}}^{(\ell )}),\hfill \end{array}$$

where $(a)$ follows from the fact that $T_{d,d,j}+T_{d,j,\ell }=T_{d,d,\ell }$. This completes the proof of the proposition. ☐

Proof of Theorem 1.

We are now ready to prove the outer bounds (9) and (10). To prove (9), note that

$$\begin{array}{cc}\hfill \beta +\frac{1}{d-\ell }H({\mathsf{U}}^{\ell })& \stackrel{(a)}{\ge }\frac{1}{d-\ell }\left(H({\overline{\mathsf{S}}}_{\to \ell +1})+H({\mathsf{U}}^{(\ell )})\right)\hfill \\ & \stackrel{(b)}{\ge }\frac{1}{d-\ell }H({\mathsf{U}}^{(\ell +1)})\hfill \\ & \stackrel{(c)}{\ge }\sum _{j=\ell +1}^d{T}_{d,j,\ell }^{-1}{B}_j+\frac{1}{d-\ell }H({\mathsf{U}}^{(\ell )}),\hfill \end{array}$$

where $(a)$ follows from the fact that $H({\overline{\mathsf{S}}}_{\to \ell +1})\le (d-\ell )\beta$; $(b)$ follows from the union bound on entropy; and $(c)$ follows from (23) of Proposition 1. Cancelling $\frac{1}{d-\ell }H({\mathsf{U}}^{\ell })$ from both sides of the inequality and normalizing both sides by ${\sum }_{t=\ell +1}^d{B}_t$ complete the proof of (9).

To prove (10), note that

$$\begin{array}{cc}\hfill \alpha & +(d(d-\ell )-\ell )\beta +(d+1)H({\mathsf{U}}^{(\ell )})\hfill \\ & \stackrel{(a)}{\ge }H({\mathsf{W}}_{d+1})+H({\mathsf{U}}^{(\ell )})+(d(d-\ell )-\ell )\beta +dH({\mathsf{U}}^{(\ell )})\hfill \\ & \stackrel{(b)}{=}H({\mathsf{W}}_{d+1},{\mathsf{S}}_{d+1\to [1:\ell ]})+H({\mathsf{U}}^{(\ell )})+\hfill \\ & (d(d-\ell )-\ell )\beta +dH({\mathsf{U}}^{(\ell )})\hfill \\ & \stackrel{(c)}{\ge }H({\mathsf{W}}_{d+1},{\mathsf{U}}^{(\ell )})+H({\mathsf{S}}_{d+1\to [1:\ell ]})+\hfill \\ & (d(d-\ell )-\ell )\beta +dH({\mathsf{U}}^{(\ell )})\hfill \\ & \stackrel{(d)}{\ge }H({\mathsf{W}}_{d+1},{\mathsf{U}}^{(\ell )})+dH({\mathsf{U}}^{(\ell +1)})\hfill \\ & \stackrel{(e)}{=}H({\mathsf{U}}^{(1,\ell +1)},{\mathsf{S}}_{1\to [2:\ell +1]})+dH({\mathsf{U}}^{(\ell +1)})\hfill \\ & \ge H({\mathsf{U}}^{(1,\ell +1)})+dH({\mathsf{U}}^{(\ell +1)})\hfill \\ & =H({\mathsf{U}}^{(1,\ell +1)})+\frac{T_{d,d,\ell +1}}{d-\ell }H({\mathsf{U}}^{(\ell +1)})+\hfill \\ & \left(d-\frac{T_{d,d,\ell +1}}{d-\ell }\right)H({\mathsf{U}}^{(\ell +1)})\hfill \\ & \stackrel{(f)}{\ge }{T}_{d,d,\ell }\left(\sum _{j=\ell +1}^d{T}_{d,j,\ell }^{-1}{B}_j+\frac{H({\mathsf{U}}^{(\ell )})}{d-\ell }\right)+\hfill \\ & \left(d-\frac{T_{d,d,\ell +1}}{d-\ell }\right)\left((d-\ell )\sum _{j=\ell +1}^d{T}_{d,j,\ell }^{-1}{B}_j+H({\mathsf{U}}^{(\ell )})\right)\hfill \\ & =\left(T_{d,d,\ell }+d(d-\ell )-T_{d,d,\ell +1}\right)\sum _{j=\ell +1}^d{T}_{d,j,\ell }^{-1}{B}_j+\hfill \\ & \left(\frac{T_{d,d,\ell }}{d-\ell }+d-\frac{T_{d,d,\ell +1}}{d-\ell }\right)H({\mathsf{U}}^{(\ell )})\hfill \\ & \stackrel{(g)}{=}(d+1)(d-\ell )\sum _{j=\ell +1}^d{T}_{d,j,\ell }^{-1}{B}_j+(d+1)H({\mathsf{U}}^{(\ell )}),\hfill \end{array}$$

where $(a)$ follows from the fact that $H({\mathsf{W}}_{d+1})\le \alpha$; $(b)$ follows from the fact that ${\mathsf{S}}_{d+1\to [1:\ell ]}$ is a function of ${\mathsf{W}}_{d+1}$; $(c)$ follows from the fact that $H({\mathsf{W}}_{d+1},{\mathsf{S}}_{d+1\to [1:\ell ]})+H({\mathsf{U}}^{(\ell )})\ge H({\mathsf{W}}_{d+1},{\mathsf{U}}^{(\ell )})+H({\mathsf{S}}_{d+1\to [1:\ell ]})$ due to the submodularity of the entropy function; $(d)$ follows from Proposition 2; $(e)$ follows from the fact that $H({\mathsf{W}}_{d+1},{\mathsf{U}}^{(\ell )})=H({\mathsf{U}}^{(1,\ell +1)},{\mathsf{S}}_{1\to [2:\ell +1]})$ due to the symmetrical code that we consider; $(f)$ follows from (23) of Proposition 1 and (30) of Proposition 3; and $(g)$ follows from the fact that $T_{d,d,\ell }-T_{d,d,\ell +1}=d-\ell$. Cancelling $(d+1)H({\mathsf{U}}^{\ell })$ from both sides of the inequality and normalizing both sides by ${\sum }_{t=\ell +1}^d{B}_t$ complete the proof of (10). ☐

5. Conclusions

This paper considered the problem of MDC-SR, which includes the problems of MDC-R and SRC as special cases. Two outer bounds were established, showing that separate coding can achieve the MBR point of the achievable normalized storage-capacity repair-bandwidth trade-off regions for the general MDC-SR problem. When specialized to the SRC problem, it was shown that the SRK point [25] is the MBR point of the achievable normalized storage-capacity repair-bandwidth trade-off regions for the general SRC problem. The core of the new converse results is an exchange lemma, which we established by using Han’s subset inequality [32]. The exchange lemma only relies on the functional dependencies for the repair processes and might be useful for solving some other related problems as well.

Note that separate encoding can also achieve the MSR point of the achievable normalized storage-capacity repair-bandwidth trade-off regions for the general MDC-R problem [22]. We suspect that this also generalizes to the MDC-SR problem. To prove such this result, however, we shall need new converse results as well as new code constructions for the general SRC problem, both of which are currently under our investigations.