Improved Deterministic Distributed Construction of Spanners

Authors Ofer Grossman, Merav Parter



PDF
Thumbnail PDF

File

LIPIcs.DISC.2017.24.pdf
  • Filesize: 0.59 MB
  • 16 pages

Document Identifiers

Author Details

Ofer Grossman
Merav Parter

Cite AsGet BibTex

Ofer Grossman and Merav Parter. Improved Deterministic Distributed Construction of Spanners. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 24:1-24:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.DISC.2017.24

Abstract

Graph spanners are fundamental graph structures with a wide range of applications in distributed networks. We consider a standard synchronous message passing model where in each round O(log n) bits can be transmitted over every edge (the CONGEST model). The state of the art of deterministic distributed spanner constructions suffers from large messages. The only exception is the work of Derbel et al., which computes an optimal-sized (2k-1)-spanner but uses O(n^(1-1/k)) rounds. In this paper, we significantly improve this bound. We present a deterministic distributed algorithm that given an unweighted n-vertex graph G = (V,E) and a parameter k > 2, constructs a (2k-1)-spanner with O(k n^(1+1/k)) edges within O(2^k n^(1/2 - 1/k)) rounds for every even k. For odd k, the number of rounds is O(2^k n^(1/2 - 1/(2k))). For the weighted case, we provide the first deterministic construction of a 3-spanner with O(n^(3/2)) edges that uses O(log n)-size messages and ~O(1) rounds. If the vertices have IDs in [1,Theta(n)], the spanner is computed in only 2 rounds!
Keywords
  • spanners
  • clustering
  • deterministic algorithms
  • congest model

Metrics

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

References

  1. Leonid Barenboim, Michael Elkin, and Cyril Gavoille. A fast network-decomposition algorithm and its applications to constant-time distributed computation. TCS, 2016. Google Scholar
  2. 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
  3. Keren Censor-Hillel, Merav Parter, and Gregory Schwartzman. Derandomizing local distributed algorithms under bandwidth restrictions. CoRR, abs/1608.01689, 2016. Google Scholar
  4. Yi-Jun Chang, Tsvi Kopelowitz, and Seth Pettie. An exponential separation between randomized and deterministic complexity in the local model. In FOCS, 2016. Google Scholar
  5. Bilel Derbel and Cyril Gavoille. Fast deterministic distributed algorithms for sparse spanners. Theoretical Computer Science, 2008. Google Scholar
  6. Bilel Derbel, Cyril Gavoille, and David Peleg. Deterministic distributed construction of linear stretch spanners in polylogarithmic time. In DISC, pages 179-192. Springer, 2007. Google Scholar
  7. Bilel Derbel, Cyril Gavoille, David Peleg, and Laurent Viennot. On the locality of distributed sparse spanner construction. In PODC, pages 273-282, 2008. Google Scholar
  8. Bilel Derbel, Cyril Gavoille, David Peleg, and Laurent Viennot. Local computation of nearly additive spanners. In DISC, 2009. Google Scholar
  9. Bilel Derbel, Mohamed Mosbah, and Akka Zemmari. Sublinear fully distributed partition with applications. Theory of Computing Systems, 47(2):368-404, 2010. Google Scholar
  10. Manuela Fischer and Mohsen Ghaffari. Deterministic distributed matching: Simpler, faster, better. arXiv preprint arXiv:1703.00900, 2017. Google Scholar
  11. Manuela Fischer, Mohsen Ghaffari, and Khun Fabian. Deterministic distributed edge-coloring via hypergraph maximal matching. arXiv preprint arXiv:1704.02767, 2017. Google Scholar
  12. Ofer Grossman and Merav Pater. Improved deterministic distributed construction of spanners. arXiv preprint arXiv:1708.01011, 2017. Google Scholar
  13. Michal Hanckowiak, Michal Karonski, and Alessandro Panconesi. On the distributed complexity of computing maximal matchings. SIDMA, 15(1):41-57, 2001. Google Scholar
  14. David Peleg. Distributed Computing: A Locality-sensitive Approach. SIAM, 2000. Google Scholar
  15. Seth Pettie. Distributed algorithms for ultrasparse spanners and linear size skeletons. Distributed Computing, 22(3):147-166, 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