Algebraic Geometric Rook Codes for Coded Distributed Computing
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866912090405470208 |
|---|---|
| author | Matthews, Gretchen L. Soto, Pedro |
| author_facet | Matthews, Gretchen L. Soto, Pedro |
| contents | We extend coded distributed computing over finite fields to allow the number of workers to be larger than the field size. We give codes that work for fully general matrix multiplication and show that in this case we serendipitously have that all functions can be computed in a distributed fault-tolerant fashion over finite fields. This generalizes previous results on the topic. We prove that the associated codes achieve a recovery threshold similar to the ones for characteristic zero fields but now with a factor that is proportional to the genus of the underlying function field. In particular, we have that the recovery threshold of these codes is proportional to the classical complexity of matrix multiplication by a factor of at most the genus. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_09746 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Algebraic Geometric Rook Codes for Coded Distributed Computing Matthews, Gretchen L. Soto, Pedro Information Theory Distributed, Parallel, and Cluster Computing Discrete Mathematics Algebraic Geometry 11T71 E.4 We extend coded distributed computing over finite fields to allow the number of workers to be larger than the field size. We give codes that work for fully general matrix multiplication and show that in this case we serendipitously have that all functions can be computed in a distributed fault-tolerant fashion over finite fields. This generalizes previous results on the topic. We prove that the associated codes achieve a recovery threshold similar to the ones for characteristic zero fields but now with a factor that is proportional to the genus of the underlying function field. In particular, we have that the recovery threshold of these codes is proportional to the classical complexity of matrix multiplication by a factor of at most the genus. |
| title | Algebraic Geometric Rook Codes for Coded Distributed Computing |
| topic | Information Theory Distributed, Parallel, and Cluster Computing Discrete Mathematics Algebraic Geometry 11T71 E.4 |
| url | https://arxiv.org/abs/2405.09746 |