Title: Outer bounds on the storage-repair bandwidth trade-off of exact-repair regenerating codes

Authors: Birenjith Sasidharan; N. Prakash; M. Nikhil Krishnan; Myna Vajha; Kaushik Senthoor; P. Vijay Kumar

Addresses: Department of ECE, Indian Institute of Science, Bangalore 560012, India ' Massachusetts Institute of Technology, Research Laboratory of Electronics, Room 36-512, 77 Massachusetts Avenue, Cambridge, MA 02139, USA ' Department of ECE, Indian Institute of Science, Bangalore 560012, India ' Department of ECE, Indian Institute of Science, Bangalore 560012, India ' Department of Electrical Engineering, Indian Institute of Technology Madras, Chennai, India ' Department of ECE, Indian Institute of Science, Bangalore 560012, India

Abstract: In this paper, three outer bounds on the normalised storage-repair bandwidth trade-off of regenerating codes having parameter set {(n, k, d), (α, β)} under the exact-repair (ER) setting are presented. The first outer bound, termed as the repair-matrix bound, is applicable for every parameter set (n, k, d), and in conjunction with a code construction known as improved layered codes, it characterises the normalised ER trade-off for the case (n, k = 3, d = n – 1). The bound shows that a non-vanishing gap exists between the ER and functional-repair (FR) trade-offs for every (n, k, d). The second bound, termed as the improved Mohajer-Tandon bound, is an improvement upon an existing bound due to Mohajer et al. and performs better in a region away from the minimum-storage-regenerating (MSR) point. However, in the vicinity of the MSR point, the repair-matrix bound outperforms the improved Mohajer-Tandon bound. The third bound is applicable to linear codes for the case k = d. In conjunction with the class of layered codes, the third outer bound characterises the normalised ER trade-off in the case of linear codes when k = d = n – 1.

Keywords: distributed storage; exact-repair regenerating codes; storage-repair bandwidth trade-off; outer bounds; linear codes.

DOI: 10.1504/IJICOT.2016.079498

International Journal of Information and Coding Theory, 2016 Vol.3 No.4, pp.255 - 298

Received: 28 Apr 2016
Accepted: 10 May 2016

Published online: 29 Sep 2016 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article