Document Open Access Logo

Making Asynchronous Distributed Computations Robust to Channel Noise

Authors Keren Censor-Hillel, Ran Gelles, Bernhard Haeupler

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2018.50.pdf
  • Filesize: 0.61 MB
  • 20 pages

Document Identifiers

Author Details

Keren Censor-Hillel
Ran Gelles
Bernhard Haeupler

Cite As Get BibTex

Keren Censor-Hillel, Ran Gelles, and Bernhard Haeupler. Making Asynchronous Distributed Computations Robust to Channel Noise. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 50:1-50:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ITCS.2018.50

Abstract

We consider the problem of making distributed computations robust to noise, in particular to worst-case (adversarial) corruptions of messages. We give a general distributed interactive coding scheme which simulates any asynchronous distributed protocol while tolerating a maximal corruption level of \Theta(1/n)-fraction of all messages. Our noise tolerance is optimal and is obtained with only a moderate overhead in the number of messages.
Our result is the first fully distributed interactive coding scheme in which the topology of the communication network is not known in advance. Prior work required either a coordinating node to be connected to all other nodes in the network or assumed a synchronous network in which all nodes already know the complete topology of the network.
Overcoming this more realistic setting of an unknown topology leads to intriguing distributed problems, in which nodes try to learn sufficient information about the network topology in order to perform efficient coding and routing operations for coping with the noise. What makes these problems hard is that these topology exploration computations themselves must already be robust to noise.

Subject Classification

Keywords
  • Distributed Computation
  • Coding for Interactive Communication
  • Noise- Resilient Computation
  • Coding Theory

Metrics

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

References

  1. Noga Alon, Mark Braverman, Klim Efremenko, Ran Gelles, and Bernhard Haeupler. Reliable communication over highly connected noisy networks. In George Giakkoupis, editor, Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC 2016, Chicago, IL, USA, July 25-28, 2016, pages 165-173. ACM, 2016. URL: http://dx.doi.org/10.1145/2933057.2933085.
  2. Hagit Attiya and Jennifer Welch. Distributed Computing: Fundamentals, Simulations and Advanced Topics. John Wiley &Sons, 2004. Google Scholar
  3. Baruch Awerbuch. Complexity of network synchronization. J. ACM, 32(4):804-823, 1985. URL: http://dx.doi.org/10.1145/4221.4227.
  4. Baruch Awerbuch, Boaz Patt-Shamir, David Peleg, and Michael E. Saks. Adapting to asynchronous dynamic networks (extended abstract). In S. Rao Kosaraju, Mike Fellows, Avi Wigderson, and John A. Ellis, editors, Proceedings of the 24th Annual ACM Symposium on Theory of Computing, May 4-6, 1992, Victoria, British Columbia, Canada, pages 557-570. ACM, 1992. URL: http://dx.doi.org/10.1145/129712.129767.
  5. Piotr Berman, Krzysztof Diks, and Andrzej Pelc. Reliable broadcasting in logarithmic time with byzantine link failures. J. Algorithms, 22(2):199-211, 1997. URL: http://dx.doi.org/10.1006/jagm.1996.0810.
  6. Zvika Brakerski, Yael Tauman Kalai, and Moni Naor. Fast interactive coding against adversarial noise. J. ACM, 61(6):35:1-35:30, 2014. URL: http://dx.doi.org/10.1145/2661628.
  7. Mark Braverman and Klim Efremenko. List and unique coding for interactive communication in the presence of adversarial noise. SIAM J. Comput., 46(1):388-428, 2017. URL: http://dx.doi.org/10.1137/141002001.
  8. Mark Braverman, Klim Efremenko, Ran Gelles, and Bernhard Haeupler. Constant-rate coding for multiparty interactive communication is impossible. In Daniel Wichs and Yishay Mansour, editors, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 999-1010. ACM, 2016. URL: http://dx.doi.org/10.1145/2897518.2897563.
  9. Mark Braverman, Ran Gelles, Jieming Mao, and Rafail Ostrovsky. Coding for interactive communication correcting insertions and deletions. IEEE Trans. Information Theory, 63(10):6256-6270, 2017. URL: http://dx.doi.org/10.1109/TIT.2017.2734881.
  10. Mark Braverman and Anup Rao. Toward coding for maximum errors in interactive communication. IEEE Trans. Information Theory, 60(11):7248-7255, 2014. URL: http://dx.doi.org/10.1109/TIT.2014.2353994.
  11. Keren Censor-Hillel, Ran Gelles, and Bernhard Haeupler. Making asynchronous distributed computations robust to noise, 2017. URL: http://arxiv.org/abs/1702.07403.
  12. Pallab Dasgupta. Agreement under faulty interfaces. Inf. Process. Lett., 65(3):125-129, 1998. URL: http://dx.doi.org/10.1016/S0020-0190(97)00202-0.
  13. Bilel Derbel, Mohamed Mosbah, and Akka Zemmari. Sublinear fully distributed partition with applications. Theory Comput. Syst., 47(2):368-404, 2010. URL: http://dx.doi.org/10.1007/s00224-009-9190-x.
  14. 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: http://dx.doi.org/10.1109/TIT.2016.2582176.
  15. Ofer Feinerman, Bernhard Haeupler, and Amos Korman. Breathe before speaking: efficient information dissemination despite noisy, limited and anonymous communication. In Magnús M. Halldórsson and Shlomi Dolev, editors, ACM Symposium on Principles of Distributed Computing, PODC '14, Paris, France, July 15-18, 2014, pages 114-123. ACM, 2014. URL: http://dx.doi.org/10.1145/2611462.2611469.
  16. Michael J. Fischer, Nancy A. Lynch, and Mike Paterson. Impossibility of distributed consensus with one faulty process. J. ACM, 32(2):374-382, 1985. URL: http://dx.doi.org/10.1145/3149.214121.
  17. Matthew K. Franklin, Ran Gelles, Rafail Ostrovsky, and Leonard J. Schulman. Optimal coding for streaming authentication and interactive communication. IEEE Trans. Information Theory, 61(1):133-145, 2015. URL: http://dx.doi.org/10.1109/TIT.2014.2367094.
  18. Robert G. Gallager. Distributed minimum hop algorithms. Technical Report LIDS-P-1175, M.I.T. Laboratory for Information and Decision Systems, 1982. Google Scholar
  19. Ran Gelles. Coding for interactive communication: A survey. Foundations and Trends in Theoretical Computer Science, 13(1-2):1-157, 2017. URL: http://dx.doi.org/10.1561/0400000079.
  20. Ran Gelles, Bernhard Haeupler, Gillat Kol, Noga Ron-Zewi, and Avi Wigderson. Towards optimal deterministic coding for interactive communication. In Robert Krauthgamer, editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 1922-1936. SIAM, 2016. URL: http://dx.doi.org/10.1137/1.9781611974331.ch135.
  21. Ran Gelles and Yael Tauman Kalai. Constant-rate interactive coding is impossible, even in constant-degree networks. In Christos H. Papadimitriou, editor, 8th Innovations in Theoretical Computer Science Conference, ITCS 2017, January 9-11, 2017, Berkeley, CA, USA, volume 67 of LIPIcs, pages 21:1-21:13. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.ITCS.2017.21.
  22. Ran Gelles, Ankur Moitra, and Amit Sahai. Efficient coding for interactive communication. IEEE Trans. Information Theory, 60(3):1899-1913, 2014. URL: http://dx.doi.org/10.1109/TIT.2013.2294186.
  23. Mohsen Ghaffari, Bernhard Haeupler, and Madhu Sudan. Optimal error rates for interactive coding I: adaptivity and other settings. In David B. Shmoys, editor, Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 794-803. ACM, 2014. URL: http://dx.doi.org/10.1145/2591796.2591872.
  24. Li Gong, Patrick Lincoln, and John Rushby. Byzantine agreement with authentication: Observations and applications in tolerating hybrid and link faults. In Dependable Computing and Fault Tolerant Systems, volume 10, pages 139-158. IEEE Computer Society, 1995. URL: http://www.csl.sri.com/papers/dcca95/dcca95.pdf.
  25. Bernhard Haeupler. Interactive channel capacity revisited. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 226-235. IEEE Computer Society, 2014. URL: http://dx.doi.org/10.1109/FOCS.2014.32.
  26. Michael Harrington and Arun K. Somani. Synchronizing hypercube networks in the presence of faults. IEEE Trans. Computers, 43(10):1175-1183, 1994. URL: http://dx.doi.org/10.1109/12.324543.
  27. William M. Hoza and Leonard J. Schulman. The adversarial noise threshold for distributed protocols. In Robert Krauthgamer, editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 240-258. SIAM, 2016. URL: http://dx.doi.org/10.1137/1.9781611974331.ch18.
  28. Abhishek Jain, Yael Tauman Kalai, and Allison Bishop Lewko. Interactive coding for multiparty protocols. In Tim Roughgarden, editor, Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, ITCS 2015, Rehovot, Israel, January 11-13, 2015, pages 1-10. ACM, 2015. URL: http://dx.doi.org/10.1145/2688073.2688109.
  29. Gillat Kol and Ran Raz. Interactive channel capacity. In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, editors, Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013, pages 715-724. ACM, 2013. URL: http://dx.doi.org/10.1145/2488608.2488699.
  30. Allison Lewko and Ellen Vitercik. Balancing communication for multi-party interactive coding, 2015. URL: http://arxiv.org/abs/1503.06381.
  31. Nancy A. Lynch. Distributed Algorithms. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1996. Google Scholar
  32. Andrzej Pelc. Reliable communication in networks with byzantine link failures. Networks, 22(5):441-459, 1992. URL: http://dx.doi.org/10.1002/net.3230220503.
  33. David Peleg. Distributed Computing: A Locality-Sensitive Approach. Society for Industrial and Applied Mathematics, 2000. URL: http://dx.doi.org/10.1137/1.9780898719772.
  34. David Peleg and Alejandro A. Schäffer. Graph spanners. Journal of Graph Theory, 13(1):99-116, 1989. URL: http://dx.doi.org/10.1002/jgt.3190130114.
  35. Sridhar Rajagopalan and Leonard J. Schulman. A coding theorem for distributed computation. In Frank Thomson Leighton and Michael T. Goodrich, editors, Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 23-25 May 1994, Montréal, Québec, Canada, pages 790-799. ACM, 1994. URL: http://dx.doi.org/10.1145/195058.195462.
  36. Hasan Md. Sayeed, Marwan Abu-Amara, and Hosame Abu-Amara. Optimal asynchronous agreement and leader election algorithm for complete networks with byzantine faulty links. Distributed Computing, 9(3):147-156, 1995. URL: http://dx.doi.org/10.1007/s004460050016.
  37. Leonard J. Schulman. Communication on noisy channels: A coding theorem for computation. In 33rd Annual Symposium on Foundations of Computer Science, Pittsburgh, Pennsylvania, USA, 24-27 October 1992, pages 724-733. IEEE Computer Society, 1992. URL: http://dx.doi.org/10.1109/SFCS.1992.267778.
  38. Leonard J. Schulman. Coding for interactive communication. IEEE Transactions on Information Theory, 42(6):1745-1756, 1996. Google Scholar
  39. Gurdip Singh. Leader election in the presence of link failures. IEEE Trans. Parallel Distrib. Syst., 7(3):231-236, 1996. URL: http://dx.doi.org/10.1109/71.491576.
  40. Hin-Sing Siu, Yeh-Hao Chin, and Wei-Pang Yang. Byzantine agreement in the presence of mixed faults on processors and links. IEEE Trans. Parallel Distrib. Syst., 9(4):335-345, 1998. URL: http://dx.doi.org/10.1109/71.667895.
  41. Gerard Tel. Introduction to distributed algorithms. Cambridge university press, 2000. Chapter 12.4. Asynchronous BFS Algorithms, pages 414–420. 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