2011/06/08 by Dimitris Papailiopoulos, Alexandros G. Dimakis, Papailiopoulos, Dimitris S. +1
Computer Science · #Advanced Data Storage Technologies #Caching and Content Delivery #Cooperative Communication and Network Coding #Distributed #FOS: Computer and information sciences #Information Theory (cs.IT) #Networking and Internet Architecture (cs.NI) #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.1106.1652
openalex publication_date 2011/06/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In distributed storage systems that employ erasure coding, the issue of minimizing the total \it repair bandwidth required to exactly regenerate a storage node after a failure arises. This repair bandwidth depends on the structure of the storage code and the repair strategies used to restore the lost data. Minimizing it requires that undesired data during a repair align in the smallest possible spaces, using the concept of interference alignment (IA). Here, a points-on-a-lattice representation of the symbol extension IA of Cadambe \it et al. provides cues to perfect IA instances which we combine with fundamental properties of Hadamard matrices to construct a new storage code with favorable repair properties. Specifically, we build an explicit (k+2,k) storage code over \mathbbGF(3), whose single systematic node failures can be repaired with bandwidth that matches exactly the theoretical minimum. Moreover, the repair of single parity node failures generates at most the same repair bandwidth as any systematic node failure. Our code can tolerate any single node failure and any pair of failures that involves at most one systematic failure.