Codes with unequal locality
- 11 August 2016
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 435-439
Abstract
In many practical settings, there is a need to design distributed storage codes with certain locality constraints. For a code C, its i-th symbol is said to have locality r if it can be recovered by accessing some other r symbols of C. Locally repairable codes (LRCs) are the family of codes such that every symbol has small locality. In this paper, we focus on LRCs with unequal symbol locality, wherein different symbols of the code have different locality values. First, we consider a class of codes with unequal information locality, i.e., systematic codes with unequal locality constraints imposed only on the information symbols. For this class of codes, we compute a tight upper bound on the minimum distance as a function of locality constraints. We demonstrate that the construction of Pyramid codes by Huang et al. can be adapted to design optimal codes with unequal information locality that achieve the minimum distance bound. Next, we consider codes with unequal all-symbol locality, i.e., codes in which the locality constraints are imposed on all symbols. We establish an upper bound on the minimum distance as a function of number of symbols of each locality value. We show that the construction based on rank-metric codes by Silberstein et al. can be adapted to obtain optimal codes with unequal all-symbol locality. Finally, we introduce the concept of locality requirement of a code, which can be viewed as a recoverability requirement on symbols. Information locality requirement of a code essentially specifies the minimum number of information symbols of each locality value that must be present in the code. For a given locality requirement, we present a greedy algorithm to construct codes that have maximum minimum distance among all codes that satisfy the locality requirement.Keywords
All Related Versions
This publication has 18 references indexed in Scilit:
- Codes with unequal locality2016
- Bounds and constructions of codes with multiple localities2016
- Bounds on the Size of Locally Recoverable CodesIEEE Transactions on Information Theory, 2015
- An Integer Programming-Based Bound for Locally Repairable CodesIEEE Transactions on Information Theory, 2015
- Analyzing the download time of availability codes2015
- A Family of Optimal Locally Recoverable CodesIEEE Transactions on Information Theory, 2014
- Locally Repairable CodesIEEE Transactions on Information Theory, 2014
- On the Delay-Storage Trade-Off in Content Download from Coded Distributed Storage SystemsIEEE Journal on Selected Areas in Communications, 2014
- Optimal locally repairable codes via rank-metric codes2013
- Pyramid Codes: Flexible Schemes to Trade Space for Access Efficiency in Reliable Data Storage Systems2007