Designing compact repair groups for Reed-Solomon codes

Thi Xinh Dinh, Serdar Boztas, Son Hoang Dau, Emanuele Viterbo

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review


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 languageEnglish
Title of host publication2023 IEEE International Symposium on Information Theory (ISIT)
EditorsAlbert Guillén i Fàbregas, Hsiao-Feng (Francis) Lu, Stefan M. Moser, Anelia Somekh-Baruch
Place of PublicationPiscataway NJ USA
PublisherIEEE, Institute of Electrical and Electronics Engineers
Number of pages6
ISBN (Electronic)9781665475549
ISBN (Print)9781665475556
Publication statusPublished - 2023
EventIEEE International Symposium on Information Theory 2023 - Taipei, Taiwan
Duration: 25 Jun 202330 Jun 2023 (Proceedings) (Website)


ConferenceIEEE International Symposium on Information Theory 2023
Abbreviated titleISIT 2023
Internet address

Cite this