On the Locality of Codeword Symbols

被引:600
作者
Gopalan, Parikshit [1 ]
Huang, Cheng [1 ]
Simitci, Huseyin [1 ]
Yekhanin, Sergey [1 ]
机构
[1] Microsoft Corp, Redmond, WA 98052 USA
关键词
Block codes; linear codes; DISTRIBUTED STORAGE; DECODABLE CODES;
D O I
10.1109/TIT.2012.2208937
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
Consider a linear [n, k, d](q) code C. We say that the ith coordinate of C has locality r, if the value at this coordinate can be recovered from accessing some other r coordinates of C. Data storage applications require codes with small redundancy, low locality for information coordinates, large distance, and low locality for parity coordinates. In this paper, we carry out an in-depth study of the relations between these parameters. We establish a tight bound for the redundancy n - k in terms of the message length, the distance, and the locality of information coordinates. We refer to codes attaining the bound as optimal. We prove some structure theorems about optimal codes, which are particularly strong for small distances. This gives a fairly complete picture of the tradeoffs between codewords length, worst case distance, and locality of information symbols. We then consider the locality of parity check symbols and erasure correction beyond worst case distance for optimal codes. Using our structure theorem, we obtain a tight bound for the locality of parity symbols possible in such codes for a broad class of parameter settings. We prove that there is a tradeoff between having good locality and the ability to correct erasures beyond the minimum distance.
引用
收藏
页码:6925 / 6934
页数:10
相关论文
共 18 条
  • [1] [Anonymous], USENIX ANN TECH C BO
  • [2] Cadambe V.R., 2010, ARXIV10044299
  • [3] Low-Complexity Array Codes for Random and Clustered 4-Erasures
    Cassuto, Yuval
    Bruck, Jehoshua
    [J]. IEEE TRANSACTIONS ON INFORMATION THEORY, 2012, 58 (01) : 146 - 158
  • [4] Chen Minghua, 2007, P IEEE INT S INF THE, P486
  • [5] A Survey on Network Codes for Distributed Storage
    Dimakis, Alexandros G.
    Ramchandran, Kannan
    Wu, Yunnan
    Suh, Changho
    [J]. PROCEEDINGS OF THE IEEE, 2011, 99 (03) : 476 - 489
  • [6] Network Coding for Distributed Storage Systems
    Dimakis, Alexandros G.
    Godfrey, P. Brighten
    Wu, Yunnan
    Wainwright, Martin J.
    Ramchandran, Kannan
    [J]. IEEE TRANSACTIONS ON INFORMATION THEORY, 2010, 56 (09) : 4539 - 4551
  • [7] Efremenko K, 2009, ACM S THEORY COMPUT, P39
  • [8] Farràs O, 2007, LECT NOTES COMPUT SC, V4515, P448
  • [9] Pyramid codes: Flexible schemes to trade space for access efficiency in reliable data storage systems
    Huang, Cheng
    Chen, Minghua
    Li, Jin
    [J]. SIXTH IEEE INTERNATIONAL SYMPOSIUM ON NETWORK COMPUTING AND APPLICATIONS, PROCEEDINGS, 2007, : 79 - +
  • [10] Jukna S., 2001, TEXT THEORET COMP S