Document Open Access Logo

Algorithms for Noisy Broadcast with Erasures

Authors Ofer Grossman, Bernhard Haeupler, Sidhanth Mohanty

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2018.153.pdf
  • Filesize: 435 kB
  • 12 pages

Document Identifiers

Author Details

Ofer Grossman
  • EECS Departent, MIT, Cambridge, MA, USA
Bernhard Haeupler
  • Computer Science Department, Carnegie Mellon University, Pittsburgh, PA, USA
Sidhanth Mohanty
  • Computer Science Department, Carnegie Mellon University, Pittsburgh, PA, USA

Cite As Get BibTex

Ofer Grossman, Bernhard Haeupler, and Sidhanth Mohanty. Algorithms for Noisy Broadcast with Erasures. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 153:1-153:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ICALP.2018.153

Abstract

The noisy broadcast model was first studied by [Gallager, 1988] where an n-character input is distributed among n processors, so that each processor receives one input bit. Computation proceeds in rounds, where in each round each processor broadcasts a single character, and each reception is corrupted independently at random with some probability p. [Gallager, 1988] gave an algorithm for all processors to learn the input in O(log log n) rounds with high probability. Later, a matching lower bound of Omega(log log n) was given by [Goyal et al., 2008].
We study a relaxed version of this model where each reception is erased and replaced with a `?' independently with probability p, so the processors have knowledge of whether a bit has been corrupted. In this relaxed model, we break past the lower bound of [Goyal et al., 2008] and obtain an O(log^* n)-round algorithm for all processors to learn the input with high probability. We also show an O(1)-round algorithm for the same problem when the alphabet size is Omega(poly(n)).

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed computing models
Keywords
  • noisy broadcast
  • error correction
  • erasures
  • distributed computing with noise

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 Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, pages 165-173. ACM, 2016. Google Scholar
  2. Florent Becker, Antonio Fernandez Anta, Ivan Rapaport, and Eric Reémila. Brief announcement: A hierarchy of congested clique models, from broadcast to unicast. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, pages 167-169. ACM, 2015. Google Scholar
  3. Mark Braverman, Klim Efremenko, Ran Gelles, and Bernhard Haeupler. Constant-rate coding for multiparty interactive communication is impossible. Journal of the ACM (JACM), 65(1):4, 2017. Google Scholar
  4. Keren Censor-Hillel, Petteri Kaski, Janne H Korhonen, Christoph Lenzen, Ami Paz, and Jukka Suomela. Algebraic methods in the congested clique. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, pages 143-152. ACM, 2015. Google Scholar
  5. Andrew Drucker, Fabian Kuhn, and Rotem Oshman. On the power of the congested clique model. In Proceedings of the 2014 ACM symposium on Principles of distributed computing, pages 367-376. ACM, 2014. Google Scholar
  6. Klim Efremenko, Gillat Kol, and Raghuvansh Saxena. Interactive coding over the noisy broadcast channel. In Electronic Colloquium on Computational Complexity (ECCC), volume 24, page 93, 2017. Google Scholar
  7. A El Gamal. Open problems presented at the 1984 workshop on specific problems in communication and computation sponsored by bell communication research. Open Problems in Communication and Computation, 1987. Google Scholar
  8. Uriel Feige and Joe Kilian. Finding or in a noisy broadcast network. Information Processing Letters, 73(1-2):69-75, 2000. Google Scholar
  9. Uriel Feige, Prabhakar Raghavan, David Peleg, and Eli Upfal. Computing with noisy information. SIAM Journal on Computing, 23(5):1001-1018, 1994. Google Scholar
  10. Robert G Gallager. Finding parity in a simple broadcast network. IEEE Transactions on Information Theory, 34(2):176-180, 1988. Google Scholar
  11. Navin Goyal, Guy Kindler, and Michael Saks. Lower bounds for the noisy broadcast problem. SIAM Journal on Computing, 37(6):1806-1841, 2008. Google Scholar
  12. Tomasz Jurdzinski and Krzysztof Nowicki. Msf and connectivity in limited variants of the congested clique. arXiv preprint arXiv:1703.02743, 2017. Google Scholar
  13. Jørn Justesen. Class of constructive asymptotically good algebraic codes. IEEE Transactions on Information Theory, 18(5):652-656, 1972. Google Scholar
  14. Eyal Kushilevitz and Yishay Mansour. Computation in noisy radio networks. In SODA, volume 98, pages 236-243, 1998. Google Scholar
  15. Pedro Montealegre and Ioan Todinca. Deterministic graph connectivity in the broadcast congested clique. arXiv preprint arXiv:1602.04095, 2016. Google Scholar
  16. Ilan Newman. Computing in fault tolerance broadcast networks. In Computational Complexity, 2004. Proceedings. 19th IEEE Annual Conference on, pages 113-122. IEEE, 2004. Google Scholar
  17. Sridhar Rajagopalan and Leonard Schulman. A coding theorem for distributed computation. In Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, pages 790-799. ACM, 1994. 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