Document Open Access Logo

Fast Hybrid Network Algorithms for Shortest Paths in Sparse Graphs

Authors Michael Feldmann, Kristian Hinnenthal, Christian Scheideler

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2020.31.pdf
  • Filesize: 496 kB
  • 16 pages

Document Identifiers

Author Details

Michael Feldmann
  • Universität Paderborn, Germany
Kristian Hinnenthal
  • Universität Paderborn, Germany
Christian Scheideler
  • Universität Paderborn, Germany

Funding

This work is supported by the German Research Foundation (DFG) within the CRC 901 "On-The-Fly Computing" (project number 160364472-SFB901).

Cite AsGet BibTex

Michael Feldmann, Kristian Hinnenthal, and Christian Scheideler. Fast Hybrid Network Algorithms for Shortest Paths in Sparse Graphs. In 24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, pp. 31:1-31:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.OPODIS.2020.31

Abstract

We consider the problem of computing shortest paths in hybrid networks, in which nodes can make use of different communication modes. For example, mobile phones may use ad-hoc connections via Bluetooth or Wi-Fi in addition to the cellular network to solve tasks more efficiently. Like in this case, the different communication modes may differ considerably in range, bandwidth, and flexibility. We build upon the model of Augustine et al. [SODA '20], which captures these differences by a local and a global mode. Specifically, the local edges model a fixed communication network in which O(1) messages of size O(log n) can be sent over every edge in each synchronous round. The global edges form a clique, but nodes are only allowed to send and receive a total of at most O(log n) messages over global edges, which restricts the nodes to use these edges only very sparsely. We demonstrate the power of hybrid networks by presenting algorithms to compute Single-Source Shortest Paths and the diameter very efficiently in sparse graphs. Specifically, we present exact O(log n) time algorithms for cactus graphs (i.e., graphs in which each edge is contained in at most one cycle), and 3-approximations for graphs that have at most n + O(n^{1/3}) edges and arboricity O(log n). For these graph classes, our algorithms provide exponentially faster solutions than the best known algorithms for general graphs in this model. Beyond shortest paths, we also provide a variety of useful tools and techniques for hybrid networks, which may be of independent interest.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
Keywords
  • hybrid networks
  • overlay networks
  • sparse graphs
  • cactus graphs

Metrics

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

Related Versions

References

  1. Dana Angluin, James Aspnes, Jiang Chen, Yinghua Wu, and Yitong Yin. Fast Construction of Overlay Networks. In Proc. of the 17th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 145-154, 2005. Google Scholar
  2. Mikhail Atallah and Uzi Vishkin. Finding euler tours in parallel. J. of Computer and System Sciences, 29(3):330-337, 1984. Google Scholar
  3. John Augustine, Keerti Choudhary, Avi Cohen, David Peleg, Sumathi Sivasubramaniam, and Suman Sourav. Distributed graph realizations, 2020. URL: http://arxiv.org/abs/2002.05376.
  4. John Augustine, Mohsen Ghaffari, Robert Gmyr, Kristian Hinnenthal, Fabian Kuhn, Jason Li, and Christian Scheideler. Distributed computation in node-capacitated networks. In Proc. of the 31st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 69-79, 2019. Google Scholar
  5. John Augustine, Kristian Hinnenthal, Fabian Kuhn, Christian Scheideler, and Philipp Schneider. Shortest paths in a hybrid network model. In Proc. of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1280-1299, 2020. Google Scholar
  6. John Augustine and Sumathi Sivasubramaniam. Spartan: A framework for sparse robust addressable networks. In 2018 IEEE International Parallel and Distributed Processing Symposium (IPDPS), pages 1060-1069, 2018. Google Scholar
  7. Leonid Barenboim and Michael Elkin. Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition. Distributed Computing, 22(5-6):363-379, 2010. Google Scholar
  8. Surender Baswana and Sandeep Sen. A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs. Random Structures & Algorithms, 30(4):532-563, 2007. Google Scholar
  9. Boaz Ben-Moshe, Amit Dvir, Michael Segal, and Arie Tamir. Centdian computation in cactus graphs. J. of Graph Algorithms and Applications, 16(2):199-224, 2012. Google Scholar
  10. Tao Chen, Xiaofeng Gao, and Guihai Chen. The features, hardware, and architectures of data center networks: A survey. J. of Parallel and Distributed Computing, 96:45-74, 2016. Google Scholar
  11. Yong Cui, Hongyi Wang, and Xiuzhen Cheng. Channel allocation in wireless data center networks. In Proc. of IEEE INFOCOM, pages 1395-1403, 2011. Google Scholar
  12. Hristo N. Djidjev, Grammati E. Pantziou, and Christos D. Zaroliagis. Computing shortest paths and distances in planar graphs. In International Colloquium on Automata, Languages, and Programming (ICALP), pages 327-338, 1991. Google Scholar
  13. Nathan Farrington, George Porter, Sivasankar Radhakrishnan, Hamid Hajabdolali Bazzaz, Vikram Subramanya, Yeshaiahu Fainman, George Papen, and Amin Vahdat. Helios: a hybrid electrical/optical switch architecture for modular data centers. In Proc. of the ACM SIGCOMM 2010 conference, pages 339-350, 2010. Google Scholar
  14. Michael Feldmann, Kristian Hinnenthal, and Christian Scheideler. Fast hybrid network algorithms for shortest paths in sparse graphs, 2020. URL: http://arxiv.org/abs/2007.01191.
  15. Jie Gao and Li Zhang. Well-separated pair decomposition for the unit-disk graph metric and its applications. SIAM J. Comput., 35(1):151-169, 2005. Google Scholar
  16. Robert Gmyr, Kristian Hinnenthal, Christian Scheideler, and Christian Sohler. Distributed monitoring of network properties: The power of hybrid networks. In Proc. of the 44th International Colloquium on Algorithms, Languages, and Programming (ICALP), pages 137:1-137:15, 2017. Google Scholar
  17. Thorsten Götte, Kristian Hinnenthal, and Christian Scheideler. Faster construction of overlay networks. In International Colloquium on Structural Information and Communication Complexity, pages 262-276. Springer, 2019. Google Scholar
  18. Thorsten Götte, Kristian Hinnenthal, Christian Scheideler, and Julian Werthmann. Time-optimal construction of overlay networks, 2020. URL: http://arxiv.org/abs/2009.03987.
  19. Joseph JaJa. An Introduction to Parallel Algorithms, volume 17. Addison Wesley, 1992. Google Scholar
  20. Daniel Jung, Christina Kolb, Christian Scheideler, and Jannik Sundermeier. Competitive routing in hybrid communication networks. In ALGOSENSORS, volume 11410, pages 15-31, 2018. Google Scholar
  21. Haim Kaplan, Wolfgang Mulzer, Liam Roditty, and Paul Seiferth. Routing in unit disk graphs. Algorithmica, 80(3):830-848, 2018. Google Scholar
  22. Udit Narayana Kar and Debarshi Kumar Sanyal. An overview of device-to-device communication in cellular networks. ICT Express, 4(3):203-208, 2018. Google Scholar
  23. Fabian Kuhn and Philipp Schneider. Computing shortest paths and diameter in the hybrid network model. In 2020 ACM Symposium on Principles of Distributed Computing (PODC), pages 109-118, 2020. Google Scholar
  24. Yu-Feng Lan and Yue-Li Wang. An optimal algorithm for solving the 1-median problem on weighted 4-cactus graphs. European Journal of Operational Research, 122(3):602-610, 2000. Google Scholar
  25. Jason Li. Faster parallel algorithm for approximate shortest path. In Proc. of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 308-321, 2020. Google Scholar
  26. Danupon Nanongkai. Distributed approximation algorithms for weighted shortest paths. In Proc. of the 46th Annual ACM Symposium on Theory of Computing (STOC), pages 565-573, 2014. Google Scholar
  27. C. St. J. A. Nash-Williams. Decomposition of Finite Graphs Into Forests. J. of the London Mathematical Society, 39(1):12-12, 1964. Google Scholar
  28. David Peleg. Distributed Computing: A Locality-Sensitive Approach. Society for Industrial and Applied Mathematics, 2000. Google Scholar
  29. Peter Robinson. Being fast means being chatty: The local information cost of graph spanners, 2020. URL: http://arxiv.org/abs/2003.09895.
  30. Michael Rossberg and Guenter Schaefer. A survey on automatic configuration of virtual private networks. Computer Networks, 55(8):1684-1699, 2011. Google Scholar
  31. Robert E. Tarjan and Uzi Vishkin. An Efficient Parallel Biconnectivity Algorithm. SIAM J. on Computing, 14(4):862-874, 1985. Google Scholar
  32. Anis Tell, Wale Babalola, George Kalebiala, and Krishna Chinta. Sd-wan: A modern hybrid-wan to enable digital transformation for businesses. IDC White Paper, April 2018. Google Scholar
  33. Jeffrey D. Ullman and Mihalis Yannakakis. High-probability parallel transitive-closure algorithms. SIAM J. on Computing, 20(1):100-125, 1991. 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