Document Open Access Logo

On the Computational Power of Radio Channels

Authors Mark Braverman, Gillat Kol, Rotem Oshman, Avishay Tal

PDF
Thumbnail PDF

File

LIPIcs.DISC.2019.8.pdf
  • Filesize: 0.51 MB
  • 17 pages

Document Identifiers

Author Details

Mark Braverman
  • Princeton University, Princeton, NJ, USA
Gillat Kol
  • Princeton University, Princeton, NJ, USA
Rotem Oshman
  • Tel Aviv University, Israel
Avishay Tal
  • UC Berkeley, CA, USA

Funding

  • Braverman, Mark: Research supported in part by NSF Award CCF- 1525342 and the NSF Alan T. Waterman Award, Grant No. 1933331, a Packard Fellowship in Science and Engineering, and the Simons Collaboration on Algorithms and Geometry.
  • Kol, Gillat: Research supported by an Alfred P. Sloan Fellowship, the National Science Foundation CAREER award CCF-1750443, and by the E. Lawrence Keyes Jr. / Emerson Electric Co. Award.
  • Oshman, Rotem: This work was done in part while the author was visiting the Simons Institute for the Theory of Computing. Research supported by the Israeli Centers of Research Excellence (I-CORE) program (Center No.4/11) and by BSF Grant No. 2014256.
  • Tal, Avishay: This work was done in part while the author was visiting the Simons Institute for the Theory of Computing. Partially supported by a Motwani Postdoctoral Fellowship and by NSF grant CCF-1763311.

Cite As Get BibTex

Mark Braverman, Gillat Kol, Rotem Oshman, and Avishay Tal. On the Computational Power of Radio Channels. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 8:1-8:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.DISC.2019.8

Abstract

Radio networks can be a challenging platform for which to develop distributed algorithms, because the network nodes must contend for a shared channel. In some cases, though, the shared medium is an advantage rather than a disadvantage: for example, many radio network algorithms cleverly use the shared channel to approximate the degree of a node, or estimate the contention. In this paper we ask how far the inherent power of a shared radio channel goes, and whether it can efficiently compute "classicaly hard" functions such as Majority, Approximate Sum, and Parity.
Using techniques from circuit complexity, we show that in many cases, the answer is "no". We show that simple radio channels, such as the beeping model or the channel with collision-detection, can be approximated by a low-degree polynomial, which makes them subject to known lower bounds on functions such as Parity and Majority; we obtain round lower bounds of the form Omega(n^{delta}) on these functions, for delta in (0,1). Next, we use the technique of random restrictions, used to prove AC^0 lower bounds, to prove a tight lower bound of Omega(1/epsilon^2) on computing a (1 +/- epsilon)-approximation to the sum of the nodes' inputs. Our techniques are general, and apply to many types of radio channels studied in the literature.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed computing models
  • Theory of computation → Communication complexity
Keywords
  • radio channel
  • lower bounds
  • approximate majority

Metrics

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

References

  1. Scott Aaronson. BQP and the polynomial hierarchy. In Symposium on Theory of Computing (STOC), pages 141-150, 2010. Google Scholar
  2. Yehuda Afek, Noga Alon, and Ziv Bar-Joseph. Beeping an MIS. Manuscript, 2011. Google Scholar
  3. Yehuda Afek, Noga Alon, Ziv Bar-Joseph, Alejandro Cornejo, Bernhard Haeupler, and Fabian Kuhn. Beeping a maximal independent set. Distributed Computing, 26(4):195-208, 2013. Google Scholar
  4. 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
  5. Miklós Ajtai. Σ¹₁-formulae on finite structures. Annals of pure and applied logic, 24(1):1-48, 1983. Google Scholar
  6. Kazuyuki Amano. Bounds on the Size of Small Depth Circuits for Approximating Majority. In International Colloquium on Automata, Languages and Programming (ICALP), pages 59-70, 2009. Google Scholar
  7. Reuven Bar-Yehuda, Oded Goldreich, and Alon Itai. On the Time-Complexity of Broadcast in Multi-hop Radio Networks: An Exponential Gap Between Determinism and Randomization. J. Comput. Syst. Sci., 45(1):104-126, 1992. Google Scholar
  8. Boaz Barak, Mark Braverman, Xi Chen, and Anup Rao. How to Compress Interactive Communication. SIAM J. Comput., 42(3):1327-1363, 2013. Google Scholar
  9. Eric Blais, Li-Yang Tan, and Andrew Wan. An inequality for the Fourier spectrum of parity decision trees. CoRR, abs/1506.01055, 2015. URL: http://arxiv.org/abs/1506.01055.
  10. Philipp Brandes, Marcin Kardas, Marek Klonowski, Dominik Pajkak, and Roger Wattenhofer. Approximating the Size of a Radio Network in Beeping Model. In Jukka Suomela, editor, Structural Information and Communication Complexity, pages 358-373, 2016. Google Scholar
  11. Joshua Brody and Elad Verbin. The Coin Problem and Pseudorandomness for Branching Programs. In Symposium on Foundations of Computer Science (FOCS), pages 30-39, 2010. Google Scholar
  12. Harry Buhrman and Ronald de Wolf. Complexity measures and decision tree complexity: a survey. Theor. Comput. Sci., 288(1):21-43, 2002. Google Scholar
  13. Ioannis Caragiannis, Clemente Galdi, and Christos Kaklamanis. Basic Computations in Wireless Networks. In Algorithms and Computation, 2005. Google Scholar
  14. Keren Censor-Hillel, Bernhard Haeupler, Nancy A. Lynch, and Muriel Médard. Bounded-Contention Coding for the additive network model. Distributed Computing, 28(5):297-308, 2015. Google Scholar
  15. Binbin Chen, Ziling Zhou, and Haifeng Yu. Understanding RFID Counting Protocols. In Annual International Conference on Mobile Computing and Networking (MobiCom), pages 291-302, 2013. Google Scholar
  16. Gil Cohen, Anat Ganor, and Ran Raz. Two Sides of the Coin Problem. In Approximation, Randomization, and Combinatorial Optimization (APPROX/RANDOM), pages 618-629, 2014. Google Scholar
  17. Alejandro Cornejo and Fabian Kuhn. Deploying Wireless Networks with Beeps. In International Conference on Distributed Computing (DISC), pages 148-162, 2010. Google Scholar
  18. Fabien Dufoulon, Janna Burman, and Joffroy Beauquier. Beeping a Deterministic Time-Optimal Leader Election. In International Symposium on Distributed Computing (DISC), pages 20:1-20:17, 2018. Google Scholar
  19. Klaus-Tycho Förster, Jochen Seidel, and Roger Wattenhofer. Deterministic Leader Election in Multi-hop Beeping Networks. In International Symposium on Distributed Computing (DISC), pages 212-226, 2014. Google Scholar
  20. Merrick L. Furst, James B. Saxe, and Michael Sipser. Parity, Circuits, and the Polynomial-Time Hierarchy. Mathematical Systems Theory, 17(1):13-27, 1984. Google Scholar
  21. Seth Gilbert and Calvin Newport. The Computational Power of Beeps. In Distributed Computing, pages 31-46, 2015. Google Scholar
  22. John Hastad. Almost Optimal Lower Bounds for Small Depth Circuits. Advances in Computing Research, 5:143-170, 1989. Google Scholar
  23. Stephan Holzer and Nancy A. Lynch. Brief announcement: Beeping a maximal independent set fast, 2017. Google Scholar
  24. Bojun Huang and Thomas Moscibroda. Conflict Resolution and Membership Problem in Beeping Channels. In International Symposium on Distributed Computing (DISC), pages 314-328, 2013. Google Scholar
  25. Tomasz Jurdziński, Mirosław Kutyłowski, and Jan Zatopiański. Energy-Efficient Size Approximation of Radio Networks with No Collision Detection. In Computing and Combinatorics, pages 279-289, 2002. Google Scholar
  26. Jedrzej Kabarowski, Mirosław Kutyłowski, and Wojciech Rutkowski. Adversary Immune Size Approximation of Single-Hop Radio Networks. In Theory and Applications of Models of Computation, 2006. Google Scholar
  27. Marek Klonowski and Kamil Wolny. Immune Size Approximation Algorithms in Ad Hoc Radio Network. In Wireless Sensor Networks, 2012. Google Scholar
  28. Gillat Kol, Rotem Oshman, and Dafna Sadeh. Interactive Compression for Multi-Party Protocol. In International Symposium on Distributed Computing (DISC), pages 31:1-31:15, 2017. Google Scholar
  29. Zhiyu Liu and Maurice Herlihy. Approximate Local Sums and Their Applications in Radio Networks. In Distributed Computing, pages 243-257, 2014. Google Scholar
  30. Yves Métivier, John Michael Robson, and Akka Zemmari. On Distributed Computing with Beeps. CoRR, abs/1507.02721, 2015. URL: http://arxiv.org/abs/1507.02721.
  31. 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
  32. Calvin Newport and Chaodong Zheng. Approximate Neighbor Counting in Radio Networks. In International Conference on Principles of Distributed Systems (OPODIS), pages 26:1-26:16, 2018. Google Scholar
  33. Calvin C. Newport. Radio Network Lower Bounds Made Easy. In International Conference on Distributed Computing (DISC), pages 258-272, 2014. Google Scholar
  34. David Peleg. Time-Efficient Broadcasting in Radio Networks: A Review. In Distributed Computing and Internet Technology (ICDCIT), pages 1-18, 2007. Google Scholar
  35. Alexander A. Razborov. Lower bounds on the size of constant-depth networks over a complete basis with logical addition. Mathematicheskie Zametki, 41(4):598-607, 1987. Google Scholar
  36. Alex Scott, Peter Jeavons, and Lei Xu. Feedback from nature: an optimal distributed algorithm for maximal independent set selection. In Symposium on Principles of Distributed Computing (PODC), pages 147-156, 2013. Google Scholar
  37. Ronen Shaltiel and Emanuele Viola. Hardness amplification proofs require majority. In Symposium on Theory of Computing (STOC), pages 589-598, 2008. Google Scholar
  38. Roman Smolensky. On Representations by Low-Degree Polynomials. In Symposium on Foundations of Computer Science (FOCS), pages 130-138, 1993. Google Scholar
  39. John P. Steinberger. The Distinguishability of Product Distributions by Read-Once Branching Programs. In Conference on Computational Complexity (CCC), pages 248-254, 2013. Google Scholar
  40. Andrew Chi-Chih Yao. Separating the Polynomial-Time Hierarchy by Oracles. In Symposium on Foundations of Computer Science (STOC), pages 1-10, 1985. Google Scholar
  41. Zhiqiang Zhang and Yaoyun Shi. On the parity complexity measures of Boolean functions. Theor. Comput. Sci., 411(26-28):2612-2618, 2010. 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