Document Open Access Logo

Approximation of Distances and Shortest Paths in the Broadcast Congest Clique

Authors Stephan Holzer, Nathan Pinsker

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2015.6.pdf
  • Filesize: 0.74 MB
  • 16 pages

Document Identifiers

Author Details

Stephan Holzer
Nathan Pinsker

Cite As Get BibTex

Stephan Holzer and Nathan Pinsker. Approximation of Distances and Shortest Paths in the Broadcast Congest Clique. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 6:1-6:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.OPODIS.2015.6

Abstract

We study the broadcast version of the CONGEST-CLIQUE model of distributed computing. This model operates in synchronized rounds; in each round, any node in a network of size n can send the same message (i.e. broadcast a message) of limited size to every other node in the network. Nanongkai presented in [STOC'14] a randomized (2+o(1))-approximation algorithm to compute all pairs shortest paths (APSP) in time ~{O}(sqrt{n}) on weighted graphs. We complement this result by proving that any randomized (2-o(1))-approximation of APSP and (2-o(1))-approximation of the diameter of a graph takes ~Omega(n) time in the worst case. This demonstrates that getting a negligible improvement in the approximation factor requires significantly more time. Furthermore this bound implies that already computing a (2-o(1))-approximation of all pairs shortest paths is among the hardest graph-problems in the broadcast-version of the CONGEST-CLIQUE model, as any graph-problem where each node receives a linear amount of input can be solved trivially in linear time in this model. This contrasts a recent (1+o(1))-approximation for APSP that runs in time O(n^{0.15715}) and an exact algorithm for APSP that runs in time ~O(n^{1/3}) in the unicast version of the CONGEST-CLIQUE model, a more powerful variant of the broadcast version. 

This lower bound in the broadcast CONGEST-CLIQUE model is derived by first establishing a new lower bound for (2-o(1))-approximating the diameter in weighted graphs in the CONGEST model, which is of independent interest. This lower bound is then transferred to the CONGEST-CLIQUE model. 

On the positive side we provide a deterministic version of Nanongkai's (2+o(1))-approximation algorithm for APSP. To do so we present a fast deterministic construction of small hitting sets. We also show how to replace another randomized part within Nanongkai's algorithm with a deterministic source-detection algorithm designed for the CONGEST model.

Subject Classification

Keywords
  • distributed computing
  • distributed algorithms
  • approximation algorithms

Metrics

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

References

  1. N. Alon, Y. Matias, and M. Szegedy. The space complexity of approximating the frequency moments. J. Comput. and Syst. Sciences, 58(1):137-147, 1999. Journal of Computer and System Sciences, 58(1):137-147, 1999. Google Scholar
  2. László Babai, Peter Frankl, and Janos Simon. Complexity classes in communication complexity theory (preliminary version). In Proceedings of the 27th annual IEEE Symposium on Foundations of Computer Science, FOCS 1986, Toronto, Ontario, Canada, 27-29 October 1986, pages 337-347, 1986. Google Scholar
  3. Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, and D. Sivakumar. An information statistics approach to data stream and communication complexity. Journal of Computer and System Science, 68(4):702-732, 2004. URL: http://dx.doi.org/10.1016/j.jcss.2003.11.006.
  4. Keren Censor-Hillel, Petteri Kaski, Janne Korhonen, Christoph Lenzen, Ami Paz, and Jukka Suomela. Algebraic methods in the congested clique. arXiv preprint 1503.04963, 2015. Google Scholar
  5. 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. SIAM Journal on Computing, 41(5):1235-1265, 2012. Google Scholar
  6. Jeffrey Dean and Sanjay Ghemawat. Mapreduce: simplified data processing on large clusters. Communications of the ACM (CACM), 51(1):107-113, 2008. Google Scholar
  7. Benjamin Dissler. Efficient multi-aggregation with applications to centrality computation. Semester thesis, ETH Zürich, Department of Information Technology and Electrical Engineering, Zürich, Switzerland, 2013. Google Scholar
  8. Shahar Dobzinski, Noam Nisan, and Sigal Oren. Economic efficiency requires interaction. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 233-242, 2014. Google Scholar
  9. Andrew Drucker, Fabian Kuhn, and Rotem Oshman. On the power of the congested clique model. In Proc. of the 33rd annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC 2014, Paris, France, July 15-18, 2014, pages 367-376, 2014. Google Scholar
  10. S. Frischknecht, S. Holzer, and R. Wattenhofer. Networks cannot compute their diameter in sublinear time. In Yuval Rabani, editor, Proc. of the 23rd Annual ACM-SIAM Symp. on Discrete Algorithms, SODA 2012, pages 1150-1162, 2012. Google Scholar
  11. O. Goldreich and A. Warning. Secure multi-party computation, 1998. Unpublished manuscript. Google Scholar
  12. James W. Hegeman and Sriram V. Pemmaraju. Lessons from the congested clique applied to mapreduce. In Magnús M. Halldórsson, editor, Structural Information and Communication Complexity - 21st International Colloquium, SIROCCO 2014, Takayama, Japan, July 23-25, 2014. Proceedings, volume 8576 of Lecture Notes in Computer Science, pages 149-164. Springer, 2014. Google Scholar
  13. James W. Hegeman, Sriram V. Pemmaraju, and Vivek Sardeshmukh. Near-constant-time distributed algorithms on a congested clique. In DISC, pages 514-530, 2014. URL: http://dx.doi.org/10.1007/978-3-662-45174-8_35.
  14. S. Holzer and R. Wattenhofer. Optimal distributed all pairs shortest paths and applications. In Darek Kowalski and Alessandro Panconesi, editors, Proceedings of the 31st annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC 2012, Funchal, Madeira, Portugal, July 16-18, 2012, pages 355-364, 2012. Google Scholar
  15. Stephan Holzer. Distance Computation, Information Dissemination, and Wireless Capacity in Networks, Diss. ETH No. 21444. Phd thesis, ETH Zurich, Zurich, Switzerland, 2013. Google Scholar
  16. Stephan Holzer and Nathan Pinsker. Approximation of distances and shortest paths in the broadcast congest clique. CoRR, abs/1412.3445, 2014. URL: http://arxiv.org/abs/1412.3445.
  17. Taisuke Izumi and Roger Wattenhofer. Time lower bounds for distributed distance oracles. In Principles of Distributed Systems, pages 60-75. Springer, 2014. Google Scholar
  18. Bala Kalyanasundaram and Georg Schnitger. The Probabilistic Communication Complexity of Set Intersection. SIAM Journal of Discrete Mathematics, 5(4):545-557, 1992. URL: http://dx.doi.org/10.1137/0405044.
  19. Hartmut Klauck, Danupon Nanongkai, Gopal Pandurangan, and Peter Robinson. The distributed complexity of large-scale graph processing. arXiv preprint arXiv:1311.6209 (to appear at SODA'15), 2013. Google Scholar
  20. E. Kushilevitz and N. Nisan. Communication complexity. Cambridge University Press, Cambridge, UK, 1997. Google Scholar
  21. C. Lenzen and D. Peleg. Efficient distributed source detection with limited bandwidth. In Panagiota Fatourou and Gadi Taubenfeld, editors, Proceedings of the 32nd annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC 2013, Montreal, Quebec, Canada, July 22-24, 2013, pages 375-382, 2013. Google Scholar
  22. Christoph Lenzen. Optimal deterministic routing and sorting on the congested clique. In Panagiota Fatourou and Gadi Taubenfeld, editors, Proceedings of the 32nd annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC 2013, Montreal, Quebec, Canada, July 22-24, 2013, pages 42-50, 2013. Google Scholar
  23. Zvi Lotker, Elan Pavlov, Boaz Patt-Shamir, and David Peleg. MST construction in O(log log n) communication rounds. In Proceedings of the 15th annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 2003, San Diego, California, USA, June 7-9,2003, pages 94-100, 2003. Google Scholar
  24. Grzegorz Malewicz, Matthew H Austern, Aart JC Bik, James C Dehnert, Ilan Horn, Naty Leiser, and Grzegorz Czajkowski. Pregel: a system for large-scale graph processing. In Ahmed K. Elmagarmid and Divyakant Agrawal, editors, Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2010, Indianapolis, Indiana, USA, June 6-10, 2010, pages 135-146. ACM, 2010. Google Scholar
  25. Danupon Nanongkai. Distributed approximation algorithms for weighted shortest paths. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing, STOC'14, pages 565-573, 2014. Google Scholar
  26. Danupon Nanongkai. Distributed approximation algorithms for weighted shortest paths. CoRR, abs/1403.5171, 2014. URL: http://arxiv.org/abs/1403.5171.
  27. Edmund B Nightingale, Jeremy Elson, Jinliang Fan, Owen S Hofmann, Jon Howell, and Yutaka Suzue. Flat datacenter storage. In OSDI, pages 1-15, 2012. Google Scholar
  28. Boaz Patt-Shamir and Marat Teplitsky. The round complexity of distributed sorting: Extended abstract. In Proceedings of the 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC'11, pages 249-256, New York, NY, USA, 2011. ACM. Google Scholar
  29. David Peleg. Distributed computing: a locality-sensitive approach. Society for Industrial and Applied Mathematics, Philadelphia, Pennsylvania, USA, 2000. Google Scholar
  30. Sriram V. Pemmaraju and Vivek B. Sardeshmukh. Algebrisation in distributed graph algorithms: Fast matrix multiplication in the congested clique. arXiv preprint 1412.2109, 2014. Google Scholar
  31. Alexander A. Razborov. On the Distributional Complexity of Disjointness. Theoretical Computer Science, 106(2):385-390, 1992. Google Scholar
  32. Roger Wattenhofer. Principles of Distributed Computing, Lecture 11, ETH Zurich, Zurich, Switzerland, http://dcg.ethz.ch/lectures/podc_allstars/lecture/chapter11.pdf, 2011. 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