Name
Abstract | ||
|---|---|---|
We extend the notion of locality from the Hamming metric to the rank and subspace metrics. Our main contribution is to construct a class of array codes with locality constraints in the rank metric. Our motivation for constructing such codes stems from the need to design codes for efficient data recovery from correlated and/or mixed (
<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i.e.,</italic>
complete and partial) failures in distributed storage systems. Specifically, the proposed local rank-metric codes can recover locally from
<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">crisscross errors and erasures</italic>
, which affect a limited number of rows and/or columns of the storage array. We also derive a Singleton-like upper bound on the minimum rank distance of (linear) codes with
<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">rank-locality</italic>
constraints. Our proposed construction achieves this bound for a broad range of parameters. The construction builds upon Tamo and Barg’s method for constructing locally repairable codes with optimal minimum Hamming distance. Finally, we construct a class of constant-dimension subspace codes (also known as Grassmannian codes) with locality constraints in the subspace metric. The key idea is to show that a Grassmannian code with locality can be easily constructed from a rank-metric code with locality by using the lifting method proposed by Silva
<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">et al.</italic>
We present an application of such codes for distributed storage systems, wherein nodes are connected over a network that can introduce errors and erasures. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1109/TIT.2019.2915539 | IEEE Transactions on Information Theory |
Keywords | Field | DocType |
Servers,Measurement,Arrays,Distributed databases,Upper bound,Maintenance engineering,Block codes | Row,Discrete mathematics,Locality,Subspace topology,Upper and lower bounds,Computer science,Block code,Distributed data store,Hamming distance,Grassmannian | Journal |
Volume | Issue | ISSN |
65 | 9 | 0018-9448 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Swanand Kadhe | 1 | 54 | 11.22 |
| Salim El Rouayheb | 2 | 39 | 4.06 |
| Iwan M. Duursma | 3 | 279 | 26.85 |
| Alex Sprintson | 4 | 279 | 35.35 |