Applied Algebra Group at the University of Zürich


Convolutional LPDC codes for Distributed Storage Systems

Prof. Dr. Hugues Mercier's talk
Date: 22.05.19   Time: 15.30 - 16.10   Room: UNINE, B217

We study convolutional LDPC codes over the binary erasure channel for immutable distributed storage systems. These codes allow the archival of data objects in a sequential fashion on an increasing number of storage nodes as they arrive in the system, as well as fast repair using a simple message passing decoder. We further target systematic codes, high code rates and low locality, which are paramount in this setting. We describe a family of codes that split each archived data object in s blocks, entangle them with t = s + p blocks already archived, and generate p parity blocks per archived data object. We carefully choose the parity-check matrix and the blocks already archived to maximize the repair capability of the resulting codes, and describe the best constructions for 1 ≤ s ≤ 5 and p = 2. A Markov analysis shows that for the same storage overhead, our codes are orders of magnitude more reliable than state-of-the-art Reed-Solomon and locally repairable codes.