2017/01/01 by Olgica Milenković, Dau, Hoang, Milenkovic, Olgica +1 · 3 citations
Computer Science · #Advanced Data Storage Technologies #Cellular Automata and Applications #Coding theory and cryptography #Distributed systems and fault tolerance #FOS: Computer and information sciences #Information Theory (cs.IT)
paper · pdf · doi:10.48550/arxiv.1701.04120
openalex publication_date 2017/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
Reed-Solomon codes have found many applications in practical storage systems,\nbut were until recently considered unsuitable for distributed storage\napplications due to the widely-held belief that they have poor repair\nbandwidth. The work of Guruswami and Wootters (STOC'16) has shown that one can\nactually perform bandwidth-efficient linear repair with Reed-Solomon codes:\nWhen the codes are over the field mathbbFqt and the number of parities\nr \≥ qs, where (t-s) divides t, there exists a linear scheme that\nachieves a repair bandwidth of (n-1)(t-s)\log2 q bits. We extend this result\nby showing the existence of such a linear repair scheme for every 1 \≤ s <\nt. Moreover, our new schemes are optimal among all linear repair schemes for\nReed-Solomon codes when n = qt and r = qs. Additionally, we improve the\nlower bound on the repair bandwidth for Reed-Solomon codes, also established in\nthe work of Guruswami and Wootters.\n