New bounds on the (n, k, d) storage systems with exact repair
Soheil Mohajer, Ravi Tandon · 2015
The exact-repair problem for distributed storage systems is considered. Characterizing the optimal storage-vs-repair bandwidth tradeoff for such systems remains an open problem for more than four storage nodes. A new family of information theoretic bounds is provided for the storage-vs-repair bandwidth tradeoff for all (n, k, d) systems. The proposed bound readily recovers Tian's result for the (4, 3, 3) system, and hence suffices for exact characterization for this system. In addition, the bound improves upon the existing bounds for the (5, 4, 4) system. More generally, it is shown that this bound characterizes the optimal boundary of the exact repair tradeoff for all distributed storage systems, with (n, k, d) = (n, n-1; n-1) when β ≤ 2α/k.