Recovery balance in linear codes tied to matroid properties
A Matroidal Framework for Random Access in Linear Codes
Information Theory
Summary
The paper looks at how to recover lost parts of special codes called linear codes by randomly sampling their pieces. It introduces a way to tell if each part of the code is equally easy to recover, called recovery balance. The authors prove that if such a code is recovery balanced, then its related code (called the dual) also has this property. They also explore recovery balance in a broader concept called matroids and find that most sparse paving matroids don’t have this balance.
What this means in practice
- •For distributed storage engineers: Assess conditions under which data recovery times are uniform across storage fragments using linear coding schemes.
- •For network reliability designers: Design network codes with predictable recovery performance by employing insights about recovery balance in linear codes and their duals.
A theory result. No direct application yet.
Authors
Daniella Bar-Lev, Hiram H. López, Gretchen L. Matthews, Flavio Salizzoni
Abstract
We study random access in linear codes when codeword symbols are sampled independently and uniformly with replacement. A code is recovery balanced if the expected number of samples required to recover a codeword coordinate is the same for every coordinate. We express the recovery expectations in terms of the associated matroid and derive a coordinatewise identity relating these values for a code and its dual. This proves that a linear code is recovery balanced if and only if its dual is recovery balanced, establishing a conjecture of Gruica et al. We further define the recovery balance for arbitrary matroids and show that asymptotically almost every sparse paving matroid is not recovery balanced.