Coding for Modern Distributed Storage Systems I
summary
Introduces a formal data locality R and proves any linear code with that locality needs length at least K + ceil(K/R) + D − 2, so locality forces a roughly linear overhead (surprising when compared to Reed–Solomon intuition). Gives matching constructions: pyramid-style parities and explicit all‑symbol‑locality codes over large fields built by evaluating linearized polynomials (Gabidulin-style) on a field basis, grouping R points and adding one parity per group, and shows puncturing one per group yields an MDS restriction.
AI-written summary · about
chapters (10)
- 0:00Start
- 4:09The data deluge ...
- 5:58Data storage: the basics
- 15:31Degraded Reads
- 16:27Disk Failure
- 16:48Can we do better?
- 25:30Locally Decodable/Testable Codes
- 29:45Codes with data locality
- 31:50Rate-distance-locality tradeoffs
- 36:37Explicit codes with all-symbol locality.
related talks
30mA New Look at Gallager's Bounds
31mUpper Bound on List-decoding Radius of Binary Codes
01h 00mAverage-case Complexity for Polynomials, and All That
01h 19mTutorial on Efficient Coding for Interactive Communication via List Decoding
29mExtended Formulations and Information Complexity
36mRelative Discrepancy Does Not Separate Information and Communication Complexity
01h 37mMatrix Rigidity
59mDawn in the age of quantum fault tolerance