Distributed Storage Codes
Stub. Error-correcting codes designed for distributed storage systems rather than communication channels: the repair problem (reconstructing one failed storage node's data from the others, efficiently, rather than by reading an entire codeword) and the resulting tradeoffs between storage overhead, repair bandwidth, and the number of nodes contacted during repair.
Corresponds to Lecture topic 10. Classical error-correcting codes are designed to recover a message from a noisy or partially erased codeword read all at once; distributed storage (across many disks or servers) poses a different, more structured version of the same problem: when a single node fails, its data should be reconstructed by downloading as little data as possible from the surviving nodes, rather than naively re-reading and re-decoding the entire original message. This note covers the resulting codes (e.g. regenerating codes, locally repairable codes) and the fundamental tradeoff curve between storage overhead (how much redundancy is kept) and repair bandwidth (how much must be downloaded to fix one failure).
Outline (TODO — flesh out each)
- The distributed storage repair problem
- Regenerating codes
- Locally repairable codes
- The storage-bandwidth tradeoff