Document Open Access Logo

Beeping Shortest Paths via Hypergraph Bipartite Decomposition

Authors Fabien Dufoulon , Yuval Emek , Ran Gelles

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2023.45.pdf
  • Filesize: 0.83 MB
  • 24 pages

Document Identifiers

Author Details

Fabien Dufoulon
  • Department of Computer Science, University of Houston, TX, USA
Yuval Emek
  • Technion, Haifa, Israel
Ran Gelles
  • Bar-Ilan University, Ramat-Gan, Israel

Funding

  • Dufoulon, Fabien: Supported in part by NSF grants CCF-1717075, CCF-1540512, IIS-1633720, and BSF grant 2016419.
  • Emek, Yuval: Supported in part by the Technion Hiroshi Fujiwara Cyber Security Research Center and the Israel National Cyber Directorate.
  • Gelles, Ran: Supported in part by ISF grant No. 1078/17 and BSF grant No. 2020277.

Acknowledgements

We would like to thank Mohsen Ghaffari for pointing out that the work of Alon et al. [Alon et al., 1991] immediately gives a lower bound of Ω(log² n) to the HBD task.

Cite As Get BibTex

Fabien Dufoulon, Yuval Emek, and Ran Gelles. Beeping Shortest Paths via Hypergraph Bipartite Decomposition. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 45:1-45:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ITCS.2023.45

Abstract

Constructing a shortest path between two network nodes is a fundamental task in distributed computing. This work develops schemes for the construction of shortest paths in randomized beeping networks between a predetermined source node and an arbitrary set of destination nodes. Our first scheme constructs a (single) shortest path to an arbitrary destination in O(D log log n + log³ n) rounds with high probability. Our second scheme constructs multiple shortest paths, one per each destination, in O(D log² n + log³ n) rounds with high probability.
Our schemes are based on a reduction of the above shortest path construction tasks to a decomposition of hypergraphs into bipartite hypergraphs: We develop a beeping procedure that partitions the hyperedge set of a hypergraph H = (V_H, E_H) into k = Θ (log² n) disjoint subsets F₁ ∪ ⋯ ∪ F_k = E_H such that the (sub-)hypergraph (V_H, F_i) is bipartite in the sense that there exists a vertex subset U ⊆ V such that |U ∩ e| = 1 for every e ∈ F_i. This procedure turns out to be instrumental in speeding up shortest path constructions under the beeping model.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
Keywords
  • Beeping Networks
  • Shortest Paths
  • Hypergraph Bipartite Decomposition

Metrics

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

References

  1. 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. URL: https://doi.org/10.1007/s00446-012-0175-7.
  2. 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. URL: https://doi.org/10.1126/science.1193210.
  3. Ron Aharoni and Ofra Kessler. On a possible extension of hall’s theorem to bipartite hypergraphs. Discrete Mathematics, 84(3):309-313, 1990. URL: https://doi.org/10.1016/0012-365X(90)90136-6.
  4. Noga Alon, Amotz Bar-Noy, Nathan Linial, and David Peleg. A lower bound for radio broadcast. Journal of Computer and System Sciences, 43(2):290-298, 1991. URL: https://doi.org/10.1016/0022-0000(91)90015-W.
  5. Yagel Ashkenazi, Ran Gelles, and Amir Leshem. Brief announcement: Noisy beeping networks. In 39th ACM Symposium on Principles of Distributed Computing (PODC 2020), pages 458-460, New York, NY, USA, 2020. Association for Computing Machinery. URL: https://doi.org/10.1145/3382734.3405705.
  6. Reuven Bar-Yehuda, Oded Goldreich, and Alon Itai. Efficient emulation of single-hop radio network with collision detection on multi-hop radio network with no collision detection. Distributed Computing, 5(2):67-71, September 1991. URL: https://doi.org/10.1007/BF02259748.
  7. J. Beauquier, J. Burman, F. Dufoulon, and S. Kutten. Fast beeping protocols for deterministic MIS and (Δ + 1)-coloring in sparse graphs. In IEEE INFOCOM 2018 - IEEE Conference on Computer Communications, pages 1754-1762, April 2018. URL: https://doi.org/10.1109/INFOCOM.2018.8486015.
  8. Joffroy Beauquier, Janna Burman, Peter Davies, and Fabien Dufoulon. Optimal multi-broadcast with beeps using group testing. In 26th International Colloquium on Structural Information and Communication Complexity (SIROCCO'19), pages 66-80, Cham, 2019. Springer International Publishing. URL: https://doi.org/10.1007/978-3-030-24922-9_5.
  9. A. Casteigts, Y. Métivier, J.M. Robson, and A. Zemmari. Design patterns in beeping algorithms: Examples, emulation, and analysis. Information and Computation, 264:32-51, 2019. URL: https://doi.org/10.1016/j.ic.2018.10.001.
  10. Bogdan S. Chlebus, Gianluca De Marco, and Muhammed Talo. Naming a channel with beeps. Fundamenta Informaticae, 153(3):199-219, 2017. URL: https://doi.org/10.3233/FI-2017-1537.
  11. Alejandro Cornejo and Fabian Kuhn. Deploying wireless networks with beeps. In Nancy A. Lynch and Alexander A. Shvartsman, editors, 24th International Symposium on Distributed Computing (DISC 2010), pages 148-162, 2010. URL: https://doi.org/10.1007/978-3-642-15763-9_15.
  12. Artur Czumaj and Peter Davies. Communicating with beeps. Journal of Parallel and Distributed Computing, 130:98-109, 2019. URL: https://doi.org/10.1016/j.jpdc.2019.03.020.
  13. Fabien Dufoulon, Janna Burman, and Joffroy Beauquier. Beeping a deterministic time-optimal leader election. In 32nd International Symposium on Distributed Computing (DISC 2018), volume 121 of LIPIcs, pages 20:1-20:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.DISC.2018.20.
  14. Fabien Dufoulon, Janna Burman, and Joffroy Beauquier. Can uncoordinated beeps tell stories? In 39th ACM Symposium on Principles of Distributed Computing (PODC 2020), pages 408-417. ACM, 2020. URL: https://doi.org/10.1145/3382734.3405699.
  15. Roland Flury and Roger Wattenhofer. Slotted programming for sensor networks. In Tarek F. Abdelzaher, Thiemo Voigt, and Adam Wolisz, editors, Proceedings of the 9th International Conference on Information Processing in Sensor Networks, IPSN 2010, April 12-16, 2010, Stockholm, Sweden, pages 24-34. ACM, 2010. Google Scholar
  16. Klaus-Tycho Förster, Jochen Seidel, and Roger Wattenhofer. Deterministic leader election in multi-hop beeping networks - (extended abstract). In 28th International Symposium on Distributed Computing (DISC 2014), pages 212-226. Springer, 2014. URL: https://doi.org/10.1007/978-3-662-45174-8_15.
  17. Mohsen Ghaffari and Bernhard Haeupler. Near optimal leader election in multi-hop radio networks. In 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2013), pages 748-766. SIAM, 2013. URL: https://doi.org/10.1137/1.9781611973105.54.
  18. Stephan Holzer and Nancy Lynch. Brief announcement: beeping a maximal independent set fast. In 30th International Symposium on Distributed Computing (DISC 2016), pages 490-493. Springer Berlin, Heidelberg, 2016. URL: https://doi.org/10.1007/978-3-662-53426-7.
  19. 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. URL: https://doi.org/10.1016/j.tcs.2019.09.020.
  20. Kokouvi Hounkanli and Andrzej Pelc. Deterministic broadcasting and gossiping with beeps. arXiv preprint, 2015. URL: http://arxiv.org/abs/1508.06460.
  21. Kokouvi Hounkanli and Andrzej Pelc. Asynchronous broadcasting with bivalent beeps. In 23rd International Colloquium on Structural Information and Communication Complexity (SIROCCO 2016), volume 9988, pages 291-306. Springer International Publishing, 2016. URL: https://doi.org/10.1007/978-3-319-48314-6_19.
  22. Peter Jeavons, Alex Scott, and Lei Xu. Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring. Distributed Computing, 29(5):377-393, October 2016. URL: https://doi.org/10.1007/s00446-016-0269-8.
  23. W. Kautz and R. Singleton. Nonrandom binary superimposed codes. IEEE Transactions on Information Theory, 10(4):363-377, 1964. URL: https://doi.org/10.1109/TIT.1964.1053689.
  24. David Peleg. Distributed Computing: A Locality-Sensitive Approach. Society for Industrial and Applied Mathematics, USA, 2000. 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