Document Open Access Logo

Interactive Coding Resilient to an Unknown Number of Erasures

Authors Ran Gelles , Siddharth Iyer

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2019.13.pdf
  • Filesize: 0.51 MB
  • 16 pages

Document Identifiers

Author Details

Ran Gelles
  • Faculty of Engineering, Bar-Ilan University, Ramat-Gan, Israel
Siddharth Iyer
  • University of Washington, WA, USA

Funding

  • Gelles, Ran: Research supported in part by the Israel Science Foundation (ISF) through grant No. 1078/17.

Acknowledgements

We thank Amir Leshem for plenty of helpful discussions.

Cite AsGet BibTex

Ran Gelles and Siddharth Iyer. Interactive Coding Resilient to an Unknown Number of Erasures. In 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, pp. 13:1-13:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.OPODIS.2019.13

Abstract

We consider distributed computations between two parties carried out over a noisy channel that may erase messages. Following a noise model proposed by Dani et al. (2018), the noise level observed by the parties during the computation in our setting is arbitrary and a priori unknown to the parties. We develop interactive coding schemes that adapt to the actual level of noise and correctly execute any two-party computation. Namely, in case the channel erases T transmissions, the coding scheme will take N+2T transmissions using an alphabet of size 4 (alternatively, using 2N+4T transmissions over a binary channel) to correctly simulate any binary protocol that takes N transmissions assuming a noiseless channel. We can further reduce the communication to N+T by relaxing the communication model and allowing parties to remain silent rather than forcing them to communicate in every round of the coding scheme. Our coding schemes are efficient, deterministic, have linear overhead both in their communication and round complexity, and succeed (with probability 1) regardless of the number of erasures T.

Subject Classification

ACM Subject Classification
  • Theory of computation → Interactive computation
  • Mathematics of computing → Coding theory
  • Computing methodologies → Distributed algorithms
Keywords
  • Interactive coding
  • erasure channels
  • distributed computation with noise
  • unbounded noise

Metrics

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

Related Versions

References

  1. Abhinav Aggarwal, Varsha Dani, Thomas P. Hayes, and Jared Saia. Distributed Computing with Channel Noise. Cryptology ePrint Archive, Report 2017/710, 2017. URL: https://eprint.iacr.org/2017/710.
  2. Abhinav Aggarwal, Varsha Dani, Thomas P. Hayes, and Jared Saia. Sending a Message with Unknown Noise. In Proceedings of the 19th International Conference on Distributed Computing and Networking, ICDCN '18, pages 8:1-8:10, 2018. URL: https://doi.org/10.1145/3154273.3154318.
  3. Shweta Agrawal, Ran Gelles, and Amit Sahai. Adaptive Protocols for Interactive Communication. In 2016 IEEE International Symposium on Information Theory (ISIT), 2016. URL: https://doi.org/10.1109/ISIT.2016.7541368.
  4. Zvika Brakerski, Yael T. Kalai, and Moni Naor. Fast Interactive Coding Against Adversarial Noise. J. ACM, 61(6):35:1-35:30, December 2014. URL: https://doi.org/10.1145/2661628.
  5. G. Brassard, A. Nayak, A. Tapp, D. Touchette, and F. Unger. Noisy Interactive Quantum Communication. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pages 296-305, October 2014. URL: https://doi.org/10.1109/FOCS.2014.39.
  6. M. Braverman and K. Efremenko. List and Unique Coding for Interactive Communication in the Presence of Adversarial Noise. SIAM Journal on Computing, 46(1):388-428, 2017. URL: https://doi.org/10.1137/141002001.
  7. M. Braverman, R. Gelles, J. Mao, and R. Ostrovsky. Coding for Interactive Communication Correcting Insertions and Deletions. IEEE Transactions on Information Theory, 63(10):6256-6270, October 2017. URL: https://doi.org/10.1109/TIT.2017.2734881.
  8. Mark Braverman. Towards deterministic tree code constructions. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, ITCS '12, pages 161-167. ACM, 2012. URL: https://doi.org/10.1145/2090236.2090250.
  9. Mark Braverman and Anup Rao. Toward Coding for Maximum Errors in Interactive Communication. Information Theory, IEEE Transactions on, 60(11):7248-7255, 2014. URL: https://doi.org/10.1109/TIT.2014.2353994.
  10. Ronald Cramer, Yevgeniy Dodis, Serge Fehr, Carles Padró, and Daniel Wichs. Detection of Algebraic Manipulation with Applications to Robust Secret Sharing and Fuzzy Extractors. In Advances in Cryptology - EUROCRYPT 2008, pages 471-488, 2008. URL: https://doi.org/10.1007/978-3-540-78967-3_27.
  11. Varsha Dani, Thomas P. Hayes, Mahnush Movahedi, Jared Saia, and Maxwell Young. Interactive communication with unknown noise rate. Information and computation, 261:464-486, 2018. URL: https://doi.org/10.1016/j.ic.2018.02.018.
  12. Klim Efremenko, Ran Gelles, and Bernhard Haeupler. Maximal Noise in Interactive Communication Over Erasure Channels and Channels With Feedback. IEEE Trans. Information Theory, 62(8):4575-4588, 2016. URL: https://doi.org/10.1109/TIT.2016.2582176.
  13. Klim Efremenko, Elad Haramaty, and Yael Kalai. Interactive Coding with Constant Round and Communication Blowup. Electronic Colloquium on Computational Complexity (ECCC), 25:54, 2018. URL: https://eccc.weizmann.ac.il/report/2018/054.
  14. Matthew Franklin, Ran Gelles, Rafail Ostrovsky, and Leonard J. Schulman. Optimal Coding for Streaming Authentication and Interactive Communication. Information Theory, IEEE Transactions on, 61(1):133-145, January 2015. URL: https://doi.org/10.1109/TIT.2014.2367094.
  15. R. Gelles and B. Haeupler. Capacity of Interactive Communication over Erasure Channels and Channels with Feedback. SIAM Journal on Computing, 46(4):1449-1472, 2017. URL: https://doi.org/10.1137/15M1052202.
  16. R. Gelles, B. Haeupler, G. Kol, N. Ron-Zewi, and A. Wigderson. Explicit Capacity Approaching Coding for Interactive Communication. IEEE Transactions on Information Theory, 64(10):6546-6560, October 2018. URL: https://doi.org/10.1109/TIT.2018.2829764.
  17. Ran Gelles. Coding for Interactive Communication: A Survey. Foundations and Trends® in Theoretical Computer Science, 13(1-2):1-157, 2017. URL: https://doi.org/10.1561/0400000079.
  18. Ran Gelles and Siddharth Iyer. Interactive coding resilient to an unknown number of erasures. CoRR, abs/1811.02527, 2018. A preliminary full version of this paper. URL: http://arxiv.org/abs/1811.02527.
  19. Ran Gelles, Ankur Moitra, and Amit Sahai. Efficient Coding for Interactive Communication. Information Theory, IEEE Transactions on, 60(3):1899-1913, March 2014. URL: https://doi.org/10.1109/TIT.2013.2294186.
  20. Mohsen Ghaffari and Bernhard Haeupler. Optimal Error Rates for Interactive Coding II: Efficiency and List Decoding. In Foundations of Computer Science (FOCS), IEEE 55th Annual Symposium on, pages 394-403, 2014. Google Scholar
  21. Mohsen Ghaffari, Bernhard Haeupler, and Madhu Sudan. Optimal Error Rates for Interactive Coding I: Adaptivity and Other Settings. In STOC '14: Proceedings of the 46th Annual ACM Symposium on Theory of Computing, pages 794-803, 2014. URL: https://doi.org/10.1145/2591796.2591872.
  22. Bernhard Haeupler. Interactive Channel Capacity Revisited. In Foundations of Computer Science (FOCS), IEEE 55th Annual Symposium on, pages 226-235, 2014. Google Scholar
  23. Bernhard Haeupler, Amirbehshad Shahrasbi, and Ellen Vitercik. Synchronization Strings: Channel Simulations and Interactive Coding for Insertions and Deletions. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), volume 107 of Leibniz International Proceedings in Informatics (LIPIcs), pages 75:1-75:14, 2018. URL: https://doi.org/10.4230/LIPIcs.ICALP.2018.75.
  24. Joseph Y. Halpern and Yoram Moses. Knowledge and Common Knowledge in a Distributed Environment. J. ACM, 37(3):549-587, July 1990. URL: https://doi.org/10.1145/79147.79161.
  25. IEEE. IEEE standard for Ethernet. IEEE Std 802.3-2015 (Revision of IEEE Std 802.3-2012), pages 1-4017, March 2016. URL: https://doi.org/10.1109/IEEESTD.2016.7428776.
  26. Gillat Kol and Ran Raz. Interactive channel capacity. In STOC '13: Proceedings of the 45th annual ACM Symposium on theory of computing, pages 715-724, 2013. URL: https://doi.org/10.1145/2488608.2488699.
  27. Debbie Leung, Ashwin Nayak, Ala Shayeghi, Dave Touchette, Penghui Yao, and Nengkun Yu. Capacity Approaching Coding for Low Noise Interactive Quantum Communication. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, pages 339-352, 2018. URL: https://doi.org/10.1145/3188745.3188908.
  28. Denis Pankratov. On the Power of Feedback in Interactive Channels. [Online:] http://people.cs.uchicago.edu/~pankratov/papers/feedback.pdf, 2013.
  29. Leonard J. Schulman. Communication on noisy channels: a coding theorem for computation. Foundations of Computer Science, Annual IEEE Symposium on, pages 724-733, 1992. URL: https://doi.org/10.1109/SFCS.1992.267778.
  30. Leonard J. Schulman. Coding for interactive communication. IEEE Transactions on Information Theory, 42(6):1745-1756, 1996. URL: https://doi.org/10.1109/18.556671.
  31. Leonard J. Schulman. A postcript to "Coding for Interactive Communication". [Online:] http://www.cs.caltech.edu/~schulman/Papers/intercodingpostscript.txt, 2003.
  32. Alexander A. Sherstov and Pei Wu. Optimal Interactive Coding for Insertions, Deletions, and Substitutions. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 240-251, October 2017. URL: https://doi.org/10.1109/FOCS.2017.30.
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 Imprint Privacy Contact