Abstract
Motivated by the application of Reed-Solomon codes to recently emerging decentralized storage systems such as Storj and Filebase/Sia, we study the problem of designing compact repair groups for recovering multiple failures in a decentralized manner. Here, compactness means that the corresponding trace repair schemes of these groups of helpers can be generated from a single or a few seed repair schemes, thus saving the time and space required for finding and storing them. The goal is to design compact repair groups that can tolerate as many failures as possible. It turns out that the maximum number of failures a collection of repair groups can tolerate equals the size of a minimum hitting set of a collection of subsets of the finite field Fql minus one. When the repair groups for each symbol are generated from a single subspace, we establish a pair of asymptotically tight lower bound and upper bound on the size of such a minimum hitting set. Using Burnside's Lemma and the Möbius inversion formula, we determine a number of subspaces that together attain the upper bound on the minimum hitting set size when the repair groups are generated from multiple subspaces.
Original language | English |
---|---|
Title of host publication | 2023 IEEE International Symposium on Information Theory (ISIT) |
Editors | Albert Guillén i Fàbregas, Hsiao-Feng (Francis) Lu, Stefan M. Moser, Anelia Somekh-Baruch |
Place of Publication | Piscataway NJ USA |
Publisher | IEEE, Institute of Electrical and Electronics Engineers |
Pages | 2027-2032 |
Number of pages | 6 |
ISBN (Electronic) | 9781665475549 |
ISBN (Print) | 9781665475556 |
DOIs | |
Publication status | Published - 2023 |
Event | IEEE International Symposium on Information Theory 2023 - Taipei, Taiwan Duration: 25 Jun 2023 → 30 Jun 2023 https://ieeexplore.ieee.org/xpl/conhome/10206429/proceeding (Proceedings) https://isit2023.org/ (Website) |
Conference
Conference | IEEE International Symposium on Information Theory 2023 |
---|---|
Abbreviated title | ISIT 2023 |
Country/Territory | Taiwan |
City | Taipei |
Period | 25/06/23 → 30/06/23 |
Internet address |
|