Document Open Access Logo

Low-Bandwidth Recovery of Linear Functions of Reed-Solomon-Encoded Data

Authors Noah Shutty, Mary Wootters

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2022.117.pdf
  • Filesize: 0.76 MB
  • 19 pages

Document Identifiers

Author Details

Noah Shutty
  • Stanford University, CA, USA
Mary Wootters
  • Stanford University, CA, USA

Funding

  • Shutty, Noah: Supported in part by NSF DGE-1656518.
  • Wootters, Mary: Research partially supported by NSF Grants CCF-1844628 and CCF-BSF-1814629, and by a Sloan Research Fellowship.

Acknowledgements

We thank Yuval Ishai for helpful conversations, and in particular for suggesting the approach in Remark 7. We also thank Ravi Vakil for helpful conversations.

Cite As Get BibTex

Noah Shutty and Mary Wootters. Low-Bandwidth Recovery of Linear Functions of Reed-Solomon-Encoded Data. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 117:1-117:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ITCS.2022.117

Abstract

We study the problem of efficiently computing on encoded data. More specifically, we study the question of low-bandwidth computation of functions F:F^k → F of some data 𝐱 ∈ F^k, given access to an encoding 𝐜 ∈ Fⁿ of 𝐱 under an error correcting code. In our model - relevant in distributed storage, distributed computation and secret sharing - each symbol of 𝐜 is held by a different party, and we aim to minimize the total amount of information downloaded from each party in order to compute F(𝐱). Special cases of this problem have arisen in several domains, and we believe that it is fruitful to study this problem in generality.
Our main result is a low-bandwidth scheme to compute linear functions for Reed-Solomon codes, even in the presence of erasures. More precisely, let ε > 0 and let 𝒞: F^k → Fⁿ be a full-length Reed-Solomon code of rate 1 - ε over a field F with constant characteristic. For any γ ∈ [0, ε), our scheme can compute any linear function F(𝐱) given access to any (1 - γ)-fraction of the symbols of 𝒞(𝐱), with download bandwidth O(n/(ε - γ)) bits. In contrast, the naive scheme that involves reconstructing the data 𝐱 and then computing F(𝐱) uses Θ(n log n) bits. Our scheme has applications in distributed storage, coded computation, and homomorphic secret sharing.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Coding theory
Keywords
  • Reed-Solomon Codes
  • Regenerating Codes
  • Coded Computation

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Ceph authors and contributors. Ceph erasure code documentation. https://docs.ceph.com/en/latest/rados/operations/erasure-code/, 2016. Last accessed: 2021.
  2. Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, and Michele Orrù. Homomorphic secret sharing: optimizations and applications. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pages 2105-2122, 2017. Google Scholar
  3. Elette Boyle, Niv Gilboa, and Yuval Ishai. Breaking the circuit size barrier for secure computation under ddh. In Annual International Cryptology Conference, pages 509-539. Springer, 2016. Google Scholar
  4. Elette Boyle, Niv Gilboa, Yuval Ishai, Huijia Lin, and Stefano Tessaro. Foundations of homomorphic secret sharing. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. Google Scholar
  5. Elette Boyle, Lisa Kohl, and Peter Scholl. Homomorphic secret sharing from lattices without fhe. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 3-33. Springer, 2019. Google Scholar
  6. Zachary Charles, Dimitris Papailiopoulos, and Jordan Ellenberg. Approximate gradient coding via sparse random graphs. arXiv preprint arXiv:1711.06771, 2017. Google Scholar
  7. Victor Chen, Elena Grigorescu, and Ronald de Wolf. Error-correcting data structures. SIAM Journal on Computing, 42(1):84-111, 2013. Google Scholar
  8. Roni Con and Itzhak Tamo. Nonlinear repair schemes of reed-solomon codes. arXiv preprint arXiv:2104.01652, 2021. Google Scholar
  9. Alexandros G Dimakis, P Brighten Godfrey, Yunnan Wu, Martin J Wainwright, and Kannan Ramchandran. Network coding for distributed storage systems. IEEE transactions on information theory, 56(9):4539-4551, 2010. Google Scholar
  10. Alexandros G Dimakis, Kannan Ramchandran, Yunnan Wu, and Changho Suh. A survey on network codes for distributed storage. Proceedings of the IEEE, 99(3):476-489, 2011. Google Scholar
  11. Sanghamitra Dutta, Viveck Cadambe, and Pulkit Grover. “short-dot”: Computing large linear transforms distributedly using coded short dot products. IEEE Transactions on Information Theory, 65(10):6171-6193, 2019. Google Scholar
  12. Ingerid Fosli, Yuval Ishai, Victor Kolobov, and Mary Wootters. On the download rate of homomorphic secret sharing, 2021. Manuscript. Google Scholar
  13. Matthew Franklin and Moti Yung. Communication complexity of secure computation. In Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, pages 699-710, 1992. Google Scholar
  14. Venkatesan Guruswami and Mary Wootters. Repairing Reed-Solomon codes. IEEE transactions on Information Theory, 63(9):5684-5698, 2017. Google Scholar
  15. Apache Hadoop. HDFS erasure coding documentation. https://hadoop.apache.org/docs/current/hadoop-project-dist/hadoop-hdfs/HDFSErasureCoding.html, 2015. Last accessed: 2021.
  16. Wael Halbawi, Navid Azizan, Fariborz Salehi, and Babak Hassibi. Improving distributed gradient descent using reed-solomon codes. In 2018 IEEE International Symposium on Information Theory (ISIT), pages 2027-2031. IEEE, 2018. Google Scholar
  17. Kangwook Lee, Maximilian Lam, Ramtin Pedarsani, Dimitris Papailiopoulos, and Kannan Ramchandran. Speeding up distributed machine learning using codes. IEEE Transactions on Information Theory, 64(3):1514-1529, 2017. Google Scholar
  18. Andreas Lenz, Rawad Bitar, Antonia Wachter-Zeh, and Eitan Yaakobi. Function-correcting codes. arXiv preprint arXiv:2102.03094, 2021. Google Scholar
  19. Songze Li and Salman Avestimehr. Coded Computing: Mitigating Fundamental Bottlenecks in Large-scale Distributed Computing and Machine Learning. Now Foundations and Trends, 2020. Google Scholar
  20. Songze Li, Seyed Mohammadreza Mousavi Kalan, A Salman Avestimehr, and Mahdi Soltanolkotabi. Near-optimal straggler mitigation for distributed gradient methods. In 2018 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW), pages 857-866. IEEE, 2018. Google Scholar
  21. Songze Li, Mohammad Ali Maddah-Ali, Qian Yu, and A Salman Avestimehr. A fundamental tradeoff between computation and communication in distributed computing. IEEE Transactions on Information Theory, 64(1):109-128, 2017. Google Scholar
  22. Claudio Orlandi, Peter Scholl, and Sophia Yakoubov. The rise of paillier: Homomorphic secret sharing and public-key silent ot. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 678-708. Springer, 2021. Google Scholar
  23. Netanel Raviv, Itzhak Tamo, Rashish Tandon, and Alexandros G Dimakis. Gradient coding from cyclic mds codes and expander graphs. IEEE Transactions on Information Theory, 66(12):7475-7489, 2020. Google Scholar
  24. Lawrence Roy and Jaspal Singh. Large message homomorphic secret sharing from dcr and applications. IACR Cryptol. ePrint Arch., 2021:274, 2021. Google Scholar
  25. Karthikeyan Shanmugam, Dimitris S Papailiopoulos, Alexandros G Dimakis, and Giuseppe Caire. A repair framework for scalar mds codes. IEEE Journal on Selected Areas in Communications, 32(5):998-1007, 2014. Google Scholar
  26. Noah Shutty and Mary Wootters. Low-bandwidth recovery of linear functions of reed-solomon-encoded data. arXiv preprint arXiv:2107.11847, 2021. Google Scholar
  27. Itzhak Tamo, Min Ye, and Alexander Barg. The repair problem for reed-solomon codes: Optimal repair of single and multiple erasures with almost optimal node size. IEEE Transactions on Information Theory, 65(5):2673-2695, 2018. Google Scholar
  28. Rashish Tandon, Qi Lei, Alexandros G Dimakis, and Nikos Karampatziakis. Gradient coding: Avoiding stragglers in distributed learning. In International Conference on Machine Learning, pages 3368-3376. PMLR, 2017. Google Scholar
  29. Min Ye and Emmanuel Abbe. Communication-computation efficient gradient coding. In International Conference on Machine Learning, pages 5610-5619. PMLR, 2018. Google Scholar
  30. Qian Yu, Songze Li, Netanel Raviv, Seyed Mohammadreza Mousavi Kalan, Mahdi Soltanolkotabi, and Salman A Avestimehr. Lagrange coded computing: Optimal design for resiliency, security, and privacy. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1215-1225. PMLR, 2019. Google Scholar
  31. Qian Yu, Mohammad Ali Maddah-Ali, and A Salman Avestimehr. Coded fourier transform. In 2017 55th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 494-501. IEEE, 2017. Google Scholar
  32. Qian Yu, Mohammad Ali Maddah-Ali, and A Salman Avestimehr. Polynomial codes: an optimal design for high-dimensional coded matrix multiplication. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pages 4406-4416, 2017. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact