Multilinear Algebra for Minimum Storage Regenerating Codes
share
An (n, k, d, α)-MSR (minimum storage regeneration) code is a set of n nodes used to store a file. For a file of total size kα, each node stores α symbols, any k nodes recover the file, and any d nodes can repair any other node via each sending out α/(d-k+1) symbols. In this work, we explore various ways to re-express the infamous product-matrix construction using skew-symmetric matrices, polynomials, symmetric algebras, and exterior algebras. We then introduce a multilinear algebra foundation to produce (n, k, (k-1)t/t-1, k-1t-1)-MSR codes for general t≥2. At the t=2 end, they include the product-matrix construction as a special case. At the t=k end, we recover determinant codes of mode m=k; further restriction to n=k+1 makes it identical to the layered code at the MSR point. Our codes' sub-packetization level—α—is independent of n and small. It is less than L^2.8(d-k+1), where L is Alrabiah–Guruswami's lower bound on α. Furthermore, it is less than other MSR codes' α for a subset of practical parameters. We offer hints on how our code repairs multiple failures at once.
READ FULL TEXT