Document Open Access Logo

Noisy Radio Network Lower Bounds via Noiseless Beeping Lower Bounds

Authors Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2023.46.pdf
  • Filesize: 0.79 MB
  • 20 pages

Document Identifiers

Author Details

Klim Efremenko
  • Ben-Gurion University, Beer Sheva, Israel
Gillat Kol
  • Princeton University, NJ, USA
Dmitry Paramonov
  • Princeton University, NJ, USA
Raghuvansh R. Saxena
  • Microsoft, Cambridge, MA, USA

Cite AsGet BibTex

Klim Efremenko, Gillat Kol, Dmitry Paramonov, and Raghuvansh R. Saxena. Noisy Radio Network Lower Bounds via Noiseless Beeping Lower Bounds. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 46:1-46:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.ITCS.2023.46

Abstract

Much of today’s communication is carried out over large wireless systems with different input-output behaviors. In this work, we compare the power of central abstractions of wireless communication through the general notion of boolean symmetric f-channels: In every round of the f-channel, each of its n parties decides to either broadcast or not, and the channel outputs f(m), where m is the number of broadcasting parties. Our first result is that the well studied beeping channel, where f is the threshold-1 function, is not stronger than any other f-channel. To this end, we design a protocol over the f-channel and prove that any protocol that simulates it over the beeping channel blows up the round complexity by a factor of Ω(log n). Our lower bound technique may be of independent interest, as it essentially generalizes the popular fooling set technique by exploiting a "local" relaxation of combinatorial rectangles. Curiously, while this result shows the limitations of a noiseless channel, namely, the beeping channel, we are able to use it to show the limitations of the noisy version of many other channels. This includes the extensively studied single-hop radio network model with collisions-as-silence (CAS), which is equivalent to the f-channel with f(m) = 1 iff m = 1. In particular, our second and main result, obtained from the first, shows that converting CAS protocols to noise resilient ones may incur a large performance overhead, i.e., no constant rate interactive code exists. To this end, we design a CAS protocol and prove that any protocol that simulates it over the noisy CAS model with correlated stochastic noise, blows up the round complexity by a factor of Ω(log n). We mention that the Ω(log n) overhead in both our results is tight.

Subject Classification

ACM Subject Classification
  • Theory of computation → Communication complexity
Keywords
  • Beeping Model
  • Radio Networks

Metrics

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

Related Versions

References

  1. Yehuda Afek, Noga Alon, Omer Barad, Eran Hornstein, Naama Barkai, and Ziv Bar-Joseph. A biological solution to a fundamental distributed computing problem. Science, 331(6014):183-185, 2011. Google Scholar
  2. Noga Alon, Mark Braverman, Klim Efremenko, Ran Gelles, and Bernhard Haeupler. Reliable communication over highly connected noisy networks. In Symposium on Principles of Distributed Computing (DISC), pages 165-173, 2016. Google Scholar
  3. Yagel Ashkenazi, Ran Gelles, and Amir Leshem. Brief announcement: Noisy beeping networks. In Symposium on Principles of Distributed Computing (PODC), pages 458-460, 2020. Google Scholar
  4. Mark Braverman, Klim Efremenko, Ran Gelles, and Bernhard Haeupler. Constant-rate coding for multiparty interactive communication is impossible. In Symposium on Theory of Computing (STOC), pages 999-1010, 2016. Google Scholar
  5. Mark Braverman, Gillat Kol, Rotem Oshman, and Avishay Tal. On the computational power of radio channels. In International Symposium on Distributed Computing (DISC), volume 146, pages 8:1-8:17, 2019. Google Scholar
  6. Nader H. Bshouty. On the coin weighing problem with the presence of noise. In Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques (RANDOM/APPROX), volume 7408 of Lecture Notes in Computer Science, pages 471-482, 2012. Google Scholar
  7. David G Cantor. Determining a set from the cardinalities of its intersections with other sets. Canadian Journal of Mathematics, 16:94-97, 1964. Google Scholar
  8. Keren Censor-Hillel, Bernhard Haeupler, D. Ellis Hershkowitz, and Goran Zuzic. Broadcasting in noisy radio networks. In Symposium on Principles of Distributed Computing (PODC), pages 33-42, 2017. Google Scholar
  9. Keren Censor-Hillel, Bernhard Haeupler, D Ellis Hershkowitz, and Goran Zuzic. Erasure correction for noisy radio networks. In International Symposium on Distributed Computing (DISC), 2019. Google Scholar
  10. Imrich Chlamtac and Shay Kutten. On broadcasting in radio networks-problem analysis and protocol design. IEEE Trans. Communications, 33(12):1240-1246, 1985. Google Scholar
  11. Bogdan S. Chlebus, Gianluca De Marco, and Muhammed Talo. Naming a channel with beeps. Fundamenta Informaticae, 153(3)(199-219), 2017. Google Scholar
  12. Andrea E. F. Clementi, Angelo Monti, and Riccardo Silvestri. Selective families, superimposed codes, and broadcasting on unknown radio networks. In Symposium on Discrete Algorithms (SODA), pages 709-718, 2001. Google Scholar
  13. Alejandro Cornejo and Fabian Kuhn. Deploying wireless networks with beeps. In International Symposium on Distributed Computing (DISC), pages 148-162, 2010. Google Scholar
  14. Klim Efremenko, Gillat Kol, Dmitry Paramonov, and Raghuvansh R. Saxena. Computation over the noisy broadcast channel with malicious parties. In Innovations in Theoretical Computer Science Conference, (ITCS), volume 185, pages 82:1-82:19, 2021. Google Scholar
  15. Klim Efremenko, Gillat Kol, Dmitry Paramonov, and Raghuvansh R. Saxena. Tight bounds for general computation in noisy broadcast networks. In Symposium on Foundations of Computer Science (FOCS), 2021. Google Scholar
  16. Klim Efremenko, Gillat Kol, and Raghuvansh Saxena. Interactive coding over the noisy broadcast channel. In Symposium on Theory of Computing (STOC), pages 507-520, 2018. Google Scholar
  17. Klim Efremenko, Gillat Kol, and Raghuvansh Saxena. Radio network coding requires logarithmic overhead. In Foundations of Computer Science (FOCS), pages 348-369, 2019. Google Scholar
  18. Klim Efremenko, Gillat Kol, and Raghuvansh R. Saxena. Noisy beeps. In Symposium on Principles of Distributed Computing (PODC), pages 418-427, 2020. Google Scholar
  19. Paul Erdos and Alfréd Rényi. On two problems of information theory. Magyar Tud. Akad. Mat. Kutató Int. Közl, 8:229-243, 1963. Google Scholar
  20. Ran Gelles and Yael T Kalai. Constant-rate interactive coding is impossible, even in constant-degree networks. IEEE Transactions on Information Theory, 65:3812-3829, 2019. Google Scholar
  21. Ran Gelles, Yael Tauman Kalai, and Govind Ramnarayan. Efficient multiparty interactive coding for insertions, deletions, and substitutions. In Symposium on Principles of Distributed Computing (PODC), pages 137-146, 2019. Google Scholar
  22. László Györfi, S Győri, Bálint Laczay, and M Ruszinkó. Lectures on multiple access channels, book draft, 2005. URL: http://www.szit.bme.hu/~gyori/AFOSR_05/book.pdf.
  23. Kokouvi Hounkanli, Avery Miller, and Andrzej Pelc. Global synchronization and consensus using beeps in a fault-prone multiple access channel. Theoretical Computer Science, 806:567-576, 2020. Google Scholar
  24. William M. Hoza and Leonard J. Schulman. The adversarial noise threshold for distributed protocols. In Symposium on Discrete Algorithms (SODA), pages 240-258, 2016. Google Scholar
  25. Abhishek Jain, Yael Tauman Kalai, and Allison Bishop Lewko. Interactive coding for multiparty protocols. In Innovations in Theoretical Computer Science (ITCS), pages 1-10, 2015. Google Scholar
  26. Marek Klonowski, Dariusz R. Kowalski, and Dominik Pajak. Generalized framework for group testing: Queries, feedbacks and adversaries. Theoretical Computer Science, 919:18-35, 2022. Google Scholar
  27. B Lindström. Determining subsets by unramified experiments. in editor jn srivastava, editor, a survey of statistical designs and linear models, 1975. Google Scholar
  28. Bernt Lindström. On a combinatory detection problem i. I. Magyar Tud. Akad. Mat. Kutató Int. Közl, 9:195-207, 1964. Google Scholar
  29. Bernt Lindström. On a combinatorial problem in number theory. Canadian Mathematical Bulletin, 8(4):477-490, 1965. Google Scholar
  30. Bernt Lindström. On möbius functions and a problem in combinatorial number theory. Canadian Mathematical Bulletin, 14(4):513-516, 1971. Google Scholar
  31. Gianluca De Marco and Dariusz R. Kowalski. Searching for a subset of counterfeit coins: Randomization vs determinism and adaptiveness vs non-adaptiveness. Random Struct. Algorithms, 42(1):97-109, 2013. Google Scholar
  32. Shay Moran, Makrand Sinha, and Amir Yehudayoff. Fooling pairs in randomized communication complexity. In Jukka Suomela, editor, Structural Information and Communication Complexity (SIROCCO), volume 9988, pages 49-59, 2016. Google Scholar
  33. Saket Navlakha and Ziv Bar-Joseph. Distributed information processing in biological and computational systems. Communications of the ACM, 58(1):94-102, 2015. Google Scholar
  34. Calvin C. Newport. Radio network lower bounds made easy. In International Symposium on Distributed Computing (DISC), volume 8784 of Lecture Notes in Computer Science, pages 258-272, 2014. Google Scholar
  35. Sridhar Rajagopalan and Leonard J. Schulman. A coding theorem for distributed computation. In Symposium on the Theory of Computing (STOC), pages 790-799, 1994. Google Scholar
  36. Leonard J Schulman. Communication on noisy channels: A coding theorem for computation. In Foundations of Computer Science (FOCS), pages 724-733, 1992. Google Scholar
  37. H Shapiro and S Soderberg. A combinatory detection problem. Amer. Math. Monthly, 70:1066-1070, 1963. 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 Imprint Privacy Contact