Document Open Access Logo

Distributed Distance Approximation

Authors Bertie Ancona, Keren Censor-Hillel, Mina Dalirrooyfard, Yuval Efron, Virginia Vassilevska Williams

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2020.30.pdf
  • Filesize: 0.56 MB
  • 17 pages

Document Identifiers

Author Details

Bertie Ancona
  • MIT, Cambridge, MA, USA
Keren Censor-Hillel
  • Technion, Haifa, Israel
Mina Dalirrooyfard
  • MIT, Cambridge, MA, USA
Yuval Efron
  • Technion, Haifa, Israel
Virginia Vassilevska Williams
  • MIT, Cambridge, MA, USA

Funding

This project has received funding from the European Research Council (ERC) under the European Unions Horizon 2020 research and innovation programme under grant agreement No 755839.

Cite As Get BibTex

Bertie Ancona, Keren Censor-Hillel, Mina Dalirrooyfard, Yuval Efron, and Virginia Vassilevska Williams. Distributed Distance Approximation. In 24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, pp. 30:1-30:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.OPODIS.2020.30

Abstract

Diameter, radius and eccentricities are fundamental graph parameters, which are extensively studied in various computational settings. Typically, computing approximate answers can be much more efficient compared with computing exact solutions. In this paper, we give a near complete characterization of the trade-offs between approximation ratios and round complexity of distributed algorithms for approximating these parameters, with a focus on the weighted and directed variants.
Furthermore, we study bi-chromatic variants of these parameters defined on a graph whose vertices are colored either red or blue, and one focuses only on distances for pairs of vertices that are colored differently. Motivated by applications in computational geometry, bi-chromatic diameter, radius and eccentricities have been recently studied in the sequential setting [Backurs et al. STOC'18, Dalirrooyfard et al. ICALP'19]. We provide the first distributed upper and lower bounds for such problems. 
Our technical contributions include introducing the notion of approximate pseudo-center, which extends the pseudo-centers of [Choudhary and Gold SODA'20], and presenting an efficient distributed algorithm for computing approximate pseudo-centers. On the lower bound side, our constructions introduce the usage of new functions into the framework of reductions from 2-party communication complexity to distributed algorithms.

Subject Classification

ACM Subject Classification
  • Theory of computation
Keywords
  • Distributed Computing
  • Distance Computation
  • Algorithms
  • Lower Bounds

Metrics

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

Related Versions

References

  1. Amir Abboud, Keren Censor-Hillel, and Seri Khoury. Near-linear lower bounds for distributed distance computations, even in sparse networks. In Distributed Computing - 30th International Symposium, DISC 2016, Paris, France, September 27-29, 2016. Proceedings, pages 29-42, 2016. URL: https://doi.org/10.1007/978-3-662-53426-7_3.
  2. Amir Abboud, Keren Censor-Hillel, Seri Khoury, and Ami Paz. Smaller cuts, higher lower bounds. CoRR, abs/1901.01630, 2019. URL: http://arxiv.org/abs/1901.01630.
  3. Amir Abboud, Virginia Vassilevska Williams, and Joshua Wang. Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs. In Proceedings of the Twenty-seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '16, pages 377-391, Philadelphia, PA, USA, 2016. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=2884435.2884463.
  4. Pankaj K. Agarwal, Herbert Edelsbrunner, and Otfried Schwarzkopf. Euclidean minimum spanning trees and bichromatic closest pairs. Discret. Comput. Geom., 6:407-422, 1991. URL: https://doi.org/10.1007/BF02574698.
  5. Udit Agarwal and Vijaya Ramachandran. New and simplified distributed algorithms for weighted all pairs shortest paths. CoRR, abs/1810.08544, 2018. URL: http://arxiv.org/abs/1810.08544.
  6. Udit Agarwal and Vijaya Ramachandran. Distributed weighted all pairs shortest paths through pipelining. In 2019 IEEE International Parallel and Distributed Processing Symposium, IPDPS 2019, Rio de Janeiro, Brazil, May 20-24, 2019, pages 23-32. IEEE, 2019. URL: https://doi.org/10.1109/IPDPS.2019.00014.
  7. Udit Agarwal and Vijaya Ramachandran. Faster deterministic all pairs shortest paths in congest model. In Christian Scheideler and Michael Spear, editors, SPAA '20: 32nd ACM Symposium on Parallelism in Algorithms and Architectures, Virtual Event, USA, July 15-17, 2020, pages 11-21. ACM, 2020. URL: https://doi.org/10.1145/3350755.3400256.
  8. Udit Agarwal, Vijaya Ramachandran, Valerie King, and Matteo Pontecorvi. A deterministic distributed algorithm for exact weighted all-pairs shortest paths in õ(n 3/2 ) rounds. In Calvin Newport and Idit Keidar, editors, Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC 2018, Egham, United Kingdom, July 23-27, 2018, pages 199-205. ACM, 2018. URL: https://doi.org/10.1145/3212734.3212773.
  9. Anonymous authors. Improved hardness of approximation of diameter in the congest model. In submission, 2020. Google Scholar
  10. Nir Bachrach, Keren Censor-Hillel, Michal Dory, Yuval Efron, Dean Leitersdorf, and Ami Paz. Hardness of distributed optimization. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Canada, July 29 - August 2, 2019, pages 238-247, 2019. URL: https://doi.org/10.1145/3293611.3331597.
  11. Arturs Backurs, Liam Roditty, Gilad Segal, Virginia Vassilevska Williams, and Nicole Wein. Towards tight approximation bounds for graph diameter and eccentricities. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, pages 267-280, New York, NY, USA, 2018. ACM. URL: https://doi.org/10.1145/3188745.3188950.
  12. Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, and D. Sivakumar. An information statistics approach to data stream and communication complexity. J. Comput. Syst. Sci., 68(4):702-732, 2004. URL: https://doi.org/10.1016/j.jcss.2003.11.006.
  13. Ruben Becker, Andreas Karrenbauer, Sebastian Krinninger, and Christoph Lenzen. Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models. In Andréa W. Richa, editor, 31st International Symposium on Distributed Computing (DISC 2017), volume 91 of Leibniz International Proceedings in Informatics (LIPIcs), pages 7:1-7:16, Dagstuhl, Germany, 2017. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.DISC.2017.7.
  14. Aaron Bernstein and Danupon Nanongkai. Distributed exact weighted all-pairs shortest paths in near-linear time. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, pages 334-342, New York, NY, USA, 2019. ACM. URL: https://doi.org/10.1145/3313276.3316326.
  15. Massimo Cairo, Roberto Grossi, and Romeo Rizzi. New bounds for approximating extremal distances in undirected graphs. In Proceedings of the Twenty-seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '16, pages 363-376, Philadelphia, PA, USA, 2016. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=2884435.2884462.
  16. Keren Censor-Hillel and Michal Dory. Distributed spanner approximation. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC 2018, Egham, United Kingdom, July 23-27, 2018, pages 139-148, 2018. URL: https://doi.org/10.1145/3212734.3212758.
  17. Keren Censor-Hillel, Michal Dory, Janne H. Korhonen, and Dean Leitersdorf. Fast approximate shortest paths in the congested clique. In Peter Robinson and Faith Ellen, editors, Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Canada, July 29 - August 2, 2019, pages 74-83. ACM, 2019. URL: https://doi.org/10.1145/3293611.3331633.
  18. Keren Censor-Hillel, Petteri Kaski, Janne H. Korhonen, Christoph Lenzen, Ami Paz, and Jukka Suomela. Algebraic methods in the congested clique. Distributed Comput., 32(6):461-478, 2019. URL: https://doi.org/10.1007/s00446-016-0270-2.
  19. Keren Censor-Hillel, Seri Khoury, and Ami Paz. Quadratic and near-quadratic lower bounds for the CONGEST model. In 31st International Symposium on Distributed Computing, DISC 2017, October 16-20, 2017, Vienna, Austria, pages 10:1-10:16, 2017. URL: https://doi.org/10.4230/LIPIcs.DISC.2017.10.
  20. Shiri Chechik and Doron Mukhtar. Reachability and shortest paths in the broadcast CONGEST model. In Jukka Suomela, editor, 33rd International Symposium on Distributed Computing, DISC 2019, October 14-18, 2019, Budapest, Hungary, volume 146 of LIPIcs, pages 11:1-11:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.DISC.2019.11.
  21. Shiri Chechik and Doron Mukhtar. Single-source shortest paths in the CONGEST model with improved bound. In Yuval Emek and Christian Cachin, editors, PODC '20: ACM Symposium on Principles of Distributed Computing, Virtual Event, Italy, August 3-7, 2020, pages 464-473. ACM, 2020. URL: https://doi.org/10.1145/3382734.3405729.
  22. Keerti Choudhary and Omer Gold. Extremal distances in directed graphs: Tight spanners and near-optimal approximation algorithms. In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 495-514. SIAM, 2020. URL: https://doi.org/10.1137/1.9781611975994.30.
  23. Artur Czumaj and Christian Konrad. Detecting cliques in CONGEST networks. In 32nd International Symposium on Distributed Computing, DISC 2018, New Orleans, LA, USA, October 15-19, 2018, pages 16:1-16:15, 2018. URL: https://doi.org/10.4230/LIPIcs.DISC.2018.16.
  24. Mina Dalirrooyfard, Virginia Vassilevska Williams, Nikhil Vyas, and Nicole Wein. Tight approximation algorithms for bichromatic graph diameter and related problems. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, volume 132 of LIPIcs, pages 47:1-47:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.47.
  25. Atish Das Sarma, Stephan Holzer, Liah Kor, Amos Korman, Danupon Nanongkai, Gopal Pandurangan, David Peleg, and Roger Wattenhofer. Distributed verification and hardness of distributed approximation. In Proceedings of the Forty-third Annual ACM Symposium on Theory of Computing, STOC '11, pages 363-372, New York, NY, USA, 2011. ACM. URL: https://doi.org/10.1145/1993636.1993686.
  26. Michael Dinitz and Yasamin Nazari. Massively parallel approximate distance sketches. In Pascal Felber, Roy Friedman, Seth Gilbert, and Avery Miller, editors, 23rd International Conference on Principles of Distributed Systems, OPODIS 2019, December 17-19, 2019, Neuchâtel, Switzerland, volume 153 of LIPIcs, pages 35:1-35:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.OPODIS.2019.35.
  27. Michal Dory and Merav Parter. Exponentially faster shortest paths in the congested clique. CoRR, abs/2003.03058, 2020. URL: http://arxiv.org/abs/2003.03058.
  28. Andrew Drucker, Fabian Kuhn, and Rotem Oshman. On the power of the congested clique model. In ACM Symposium on Principles of Distributed Computing, PODC '14, Paris, France, July 15-18, 2014, pages 367-376, 2014. URL: https://doi.org/10.1145/2611462.2611493.
  29. Adrian Dumitrescu and Sumanta Guha. Extreme distances in multicolored point sets. J. Graph Algorithms Appl., 8:27-38, 2004. URL: https://doi.org/10.7155/jgaa.00080.
  30. Michael Elkin. Distributed exact shortest paths in sublinear time. In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 757-770. ACM, 2017. URL: https://doi.org/10.1145/3055399.3055452.
  31. Michael Elkin and Ofer Neiman. Hopsets with constant hopbound, and applications to approximate shortest paths. SIAM J. Comput., 48(4):1436-1480, 2019. URL: https://doi.org/10.1137/18M1166791.
  32. Michael Elkin and Ofer Neiman. Linear-size hopsets with small hopbound, and constant-hopbound hopsets in RNC. In Christian Scheideler and Petra Berenbrink, editors, The 31st ACM on Symposium on Parallelism in Algorithms and Architectures, SPAA 2019, Phoenix, AZ, USA, June 22-24, 2019, pages 333-341. ACM, 2019. URL: https://doi.org/10.1145/3323165.3323177.
  33. Orr Fischer, Tzlil Gonen, Fabian Kuhn, and Rotem Oshman. Possibilities and impossibilities for distributed subgraph detection. In Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures, SPAA 2018, Vienna, Austria, July 16-18, 2018, pages 153-162, 2018. URL: https://doi.org/10.1145/3210377.3210401.
  34. Sebastian Forster and Danupon Nanongkai. A faster distributed single-source shortest paths algorithm. In Mikkel Thorup, editor, 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 686-697. IEEE Computer Society, 2018. URL: https://doi.org/10.1109/FOCS.2018.00071.
  35. Silvio Frischknecht, Stephan Holzer, and Roger Wattenhofer. Networks cannot compute their diameter in sublinear time. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012, pages 1150-1162, 2012. URL: https://doi.org/10.1137/1.9781611973099.91.
  36. François Le Gall. Further algebraic algorithms in the congested clique model and applications to graph-theoretic problems. In Cyril Gavoille and David Ilcinkas, editors, Distributed Computing - 30th International Symposium, DISC 2016, Paris, France, September 27-29, 2016. Proceedings, volume 9888 of Lecture Notes in Computer Science, pages 57-70. Springer, 2016. URL: https://doi.org/10.1007/978-3-662-53426-7_5.
  37. Mohsen Ghaffari and Jason Li. Improved distributed algorithms for exact shortest paths. In Ilias Diakonikolas, David Kempe, and Monika Henzinger, editors, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 431-444. ACM, 2018. URL: https://doi.org/10.1145/3188745.3188948.
  38. Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. A deterministic almost-tight distributed algorithm for approximating single-source shortest paths. In Daniel Wichs and Yishay Mansour, editors, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 489-498. ACM, 2016. URL: https://doi.org/10.1145/2897518.2897638.
  39. Stephan Holzer, David Peleg, Liam Roditty, and Roger Wattenhofer. Brief announcement: Distributed 3/2-approximation of the diameter. In Distributed Computing - 28th International Symposium, DISC 2014, pages 562-564, 2014. Google Scholar
  40. Stephan Holzer, David Peleg, Liam Roditty, and Roger Wattenhofer. Distributed 3/2-approximation of the diameter. In Distributed Computing - 28th International Symposium, DISC 2014, Austin, TX, USA, October 12-15, 2014. Proceedings, pages 562-564, 2014. URL: http://link.springer.com/content/pdf/bbm%3A978-3-662-45174-8%2F1.pdf.
  41. Stephan Holzer and Nathan Pinsker. Approximation of Distances and Shortest Paths in the Broadcast Congest Clique. In Emmanuelle Anceaume, Christian Cachin, and Maria Potop-Butucaru, editors, 19th International Conference on Principles of Distributed Systems (OPODIS 2015), volume 46 of Leibniz International Proceedings in Informatics (LIPIcs), pages 1-16, Dagstuhl, Germany, 2016. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.OPODIS.2015.6.
  42. Stephan Holzer and Roger Wattenhofer. Optimal distributed all pairs shortest paths and applications. In ACM Symposium on Principles of Distributed Computing, PODC '12, Funchal, Madeira, Portugal, July 16-18, 2012, pages 355-364, 2012. URL: https://doi.org/10.1145/2332432.2332504.
  43. Chien-Chung Huang, Danupon Nanongkai, and Thatchaphol Saranurak. Distributed exact weighted all-pairs shortest paths in õ(n^5/4) rounds. In Chris Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 168-179. IEEE Computer Society, 2017. URL: https://doi.org/10.1109/FOCS.2017.24.
  44. Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-sat. J. Comput. Syst. Sci., 62(2):367-375, 2001. URL: https://doi.org/10.1006/jcss.2000.1727.
  45. T. S. Jayram, Ravi Kumar, and D. Sivakumar. Two applications of information complexity. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing, June 9-11, 2003, San Diego, CA, USA, pages 673-682, 2003. URL: https://doi.org/10.1145/780542.780640.
  46. Naoki Katoh and Kazuo Iwano. Finding k farthest pairs and k closest/farthest bichromatic pairs for points in the plane. Int. J. Comput. Geometry Appl., 5:37-51, 1995. URL: https://doi.org/10.1142/S0218195995000040.
  47. Eyal Kushilevitz and Noam Nisan. Communication Complexity. Cambridge University Press, New York, NY, USA, 1997. Google Scholar
  48. Christoph Lenzen and Boaz Patt-Shamir. Fast routing table construction using small messages: extended abstract. In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, editors, Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013, pages 381-390. ACM, 2013. URL: https://doi.org/10.1145/2488608.2488656.
  49. Christoph Lenzen, Boaz Patt-Shamir, and David Peleg. Distributed distance computation and routing with small messages. Distributed Comput., 32(2):133-157, 2019. URL: https://doi.org/10.1007/s00446-018-0326-6.
  50. Christoph Lenzen and David Peleg. Efficient distributed source detection with limited bandwidth. In ACM Symposium on Principles of Distributed Computing, PODC '13, Montreal, QC, Canada, July 22-24, 2013, pages 375-382, 2013. URL: https://doi.org/10.1145/2484239.2484262.
  51. Jason Li and Merav Parter. Planar diameter via metric compression. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 152-163, 2019. URL: https://doi.org/10.1145/3313276.3316358.
  52. Danupon Nanongkai. Distributed approximation algorithms for weighted shortest paths. In David B. Shmoys, editor, Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 565-573. ACM, 2014. URL: https://doi.org/10.1145/2591796.2591850.
  53. David Peleg, Liam Roditty, and Elad Tal. Distributed algorithms for network diameter and girth. In Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part II, pages 660-672, 2012. URL: https://doi.org/10.1007/978-3-642-31585-5_58.
  54. David Peleg and Vitaly Rubinovich. A near-tight lower bound on the time complexity of distributed minimum-weight spanning tree construction. SIAM J. Comput., 30(5):1427-1442, 2000. URL: https://doi.org/10.1137/S0097539700369740.
  55. A.A. Razborov. On the distributional complexity of disjointness. Theoretical Computer Science, 106(2):385-390, 1992. URL: https://doi.org/10.1016/0304-3975(92)90260-M.
  56. Virginia Vassilevska Williams. On some fine-grained questions in algorithms and complexity. In Proceedings of the International Congress of Mathematicians (ICM 2018), pages 3447-3487, 2018. URL: https://doi.org/10.1142/9789813272880_0188.
  57. Andrew Chi-Chih Yao. On constructing minimum spanning trees in k-dimensional spaces and related problems. SIAM J. Comput., 11(4):721-736, 1982. URL: https://doi.org/10.1137/0211059.
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