Instruction: to retrieve the proof data file for each inequality, click the corresponding inequality. The data file can be loaded into matlab and has one vector and one matrix. The vector has the entropy terms used in the proof, and each row of the matrix is one known inequality. This webpage requires javascript enabled to be viewed correctly. The full-resolution images can be downloaded by right-clicking the images and select "save image as".
Regenerating Codes MLD Coding with Regeneration Coded Caching
Exact Repair Regenerating Codes
Regenerating codes are codes that allow more efficient node repair in distributed data storage systems. An \((n,k,d)\) exact repair regenerating code has \(n\) storage nodes, any \(k\) of the nodes can completely recover the stored data, and any failed node can be repaired by any of the remaining \(d\) nodes. The bandwidth usage during the repair can be reduced at the expense of increased storage overhead. The precise tradeoff between the two quantities is still unknown. Here are the solutions we have obtained.
(4,3,3) codes
This is the first case that shows the tradeoff of exact repair codes is fundamentally different from that of the functional repair version, and the starting point of the computational approach we are exploring. Details can be found in "Characterizing the rate-region of the (4,3,3) exact-repair regenerating codes," C. Tian, IEEE JSAC, May 2014. The only new inequality that need to be proved is the one below: $$4\bar\alpha+6\bar\beta \geq 3.$$ In a recent work "A probabilistic approach towards exact-repair regeneration codes", Elyasi and Mohajer showed that the same region is in fact the optimal tradeoff region for any \((n,k=3,d=3)\) exact-repair regenerating codes by providing a new code construction.
(5,4,4) codes
Several recent works have provided partial answers in this case. We provide a conclusive result by extending the computational approach. See the technical report (and references therein): "A note on the rate region of exact repair regenerating codes". Beyond the known functional repair outer bounds, there are two additional inequalities that need to be proved here: $$15\bar\alpha+10\bar\beta \geq 6,$$ $$5\bar\alpha+10\bar\beta \geq 3.$$ Existence evidence appears to suggest that the canonical layered codes proposed in "Layered, exact-repair regenerating codes via embedded error correction and block designs," C. Tian, B. Sasidharan, V. Aggarwal, V. A. Vaishampayan, P. V. Kumar, is able to achieve the complete optimal tradeoff for the \((n,k=n-1,d=n-1)\) case. This is now known to be true for \(n\leq 5\), and this class of codes is also known to be optimal for general \(n\) values within the restricted class of linear codes; see "The storage-repair-bandwidth trade-off of exact repair linear regenerating codes for the case \(d=k=n-1\)" by N. Prakash and M. N. Krishnan, "Linear exact repair rate region of \(k+1,k,k\) distributed storage systems: A new approach" by Elyasi, Mohajer and Tandon, and "Shortened regenerating codes" by I. M. Duursma.
(5,3,4) codes
We provide an outer bound proof obtained by the computational approach. It appears (the bounds in these two papers need some work to convert) in this case, the same outer bound we obtained can also be obtained from those analytically derived in two recent papers: "An improved outer bound on the storage-repair-bandwidth tradeoff of exact-repair regenerating codes," B. Sasidharan, K. Senthoor, P. V. Kumar, and "Outer bounds for exact repair codes," I. M. Duursma. $$7\bar\alpha+17\bar\beta \geq 5.$$ This region turns out to be tight and this requires a new code construction by Senthoor, Sasidharan and P. V. Kumar, "Improved layered regenerating codes characterizing the exact-repair storage-repair bandwidth tradeoff for certain parameter sets".
Multlevel Diversity Coding with Regeneration
Multilevel diversity coding allows different contents in distributed storage systems to have different reliabilities. The problem of multilevel diversity coding with generation (MLD-R) problem concerns with the storage vs. repair bandwidth tradeoff in this setting. An \(n\)-node MLD-R code needs to make the first \(k\) messages recoverable from any \(k\) nodes, and any failed node repairable using the other nodes. The \(i\)-th message has normalized rate \(\bar{B}_i\) and the accumulative first \(i\) messages have total normalized rate \(\bar{B}^+_i\).
Four nodes
We show mixing of different contents can provide strict improvement over non-mixing solutions (lower is better in the plot). Details can be found in "Multilevel divesity coding with regeneration," by C. Tian and T. Liu. The following inequalities are proved computationally: $$24[\bar{\alpha} +\bar{\beta}]\geq 24[\frac{4}{3}\bar{B}_1+\frac{3}{4}\bar{B}_2+\frac{5}{8}\bar{B}_3]=14\bar{B}^+_1+3\bar{B}^+_2+15\bar{B}^+_3,$$ $$6[2\bar{\alpha}+3\bar{\beta}]\geq 6\left[3\bar{B}_1+\frac{5}{3}\bar{B}_2+\frac{3}{2}\bar{B}_3\right]=8\bar{B}^+_1+\bar{B}^+_2+9\bar{B}^+_3,$$ $$6[\bar{\alpha}+2\bar{\beta}]\geq 6\left[\frac{5}{3}\bar{B}_1+\bar{B}_2+\frac{5}{6}\bar{B}_3\right]=4\bar{B}^+_1+\bar{B}^+_2+5\bar{B}^+_3,$$ $$\hspace{-10cm}30\bar{\beta}\geq 30\left[\frac{1}{3}\bar{B}_1+\frac{1}{5}\bar{B}_2+\frac{1}{6}\bar{B}_3\right]=4\bar{B}^+_1+\bar{B}^+_2+5\bar{B}^+_3.$$
Five nodes
Under investigation...
Coded Caching
Maddah-Ali and Niesen considered the caching problem which deals with improving the content delivery efficiency, i.e., the traffic rate \(R\), using local caching of capacity \(M\), in a system with \(N\) files and \(K\) users. It was shown coded caching can be quite beneficial. However, the fundamental tradeoff between the delivery traffic rate \(R\) and cache memory \(M\) was not fully known except the two-user and two-file case.
Three files and three users \((N,K)=(3,3)\)
We find a stronger outer bound using the computationl approach for this problem. We assume each file is of size \(1\) unit. More details are given in an ISIT submission "Symmetry, demand types and outer bounds for caching systems" which will be made availabe online. The following inequalities are proved computationally (as of Jan. 2016): $$6M+3R\geq 8,$$ $$M+R\geq 2,$$ $$2M+3R\geq 5,$$
Two files and three users \((N,K)=(2,3)\)
We are able to provide a complete characterization of the tradeoff region for this case. Particularly, the following inequalities are proved computationally. $$3M+3R\geq 5,$$
Two files and four users \((N,K)=(2,4)\)
We again find a stronger outer bound using the computationl approach for this problem. More details are given in an ISIT submission "Symmetry, demand types and outer bounds for caching systems" which will be made availabe online. The following inequalities are found and proved computationally (as of Jan. 2016), however since the second inequality also appears for \((N,K)=(2,3)\) case, there is in fact no need to reprove it: $$8M+6R\geq 11,$$ $$3M+3R\geq 5,$$ $$5M+6R\geq 9,$$