Document Open Access Logo

Derandomizing Local Distributed Algorithms under Bandwidth Restrictions

Authors Keren Censor-Hillel, Merav Parter, Gregory Schwartzman

PDF
Thumbnail PDF

File

LIPIcs.DISC.2017.11.pdf
  • Filesize: 0.53 MB
  • 16 pages

Document Identifiers

Author Details

Keren Censor-Hillel
Merav Parter
Gregory Schwartzman

Cite As Get BibTex

Keren Censor-Hillel, Merav Parter, and Gregory Schwartzman. Derandomizing Local Distributed Algorithms under Bandwidth Restrictions. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 11:1-11:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.DISC.2017.11

Abstract

This paper addresses the cornerstone family of local problems in distributed computing, and investigates the curious gap between randomized and deterministic solutions under bandwidth restrictions.

Our main contribution is in providing tools for derandomizing solutions to local problems, when the n nodes can only send O(log n)-bit messages in each round of communication. We combine bounded independence, which we show to be sufficient for some algorithms, with the method of conditional expectations and with additional machinery, to obtain the following results.

First, we show that in the Congested Clique model, which allows all-to-all communication, there is a deterministic maximal independent set (MIS) algorithm that runs in O(log^2 Delta) rounds, where Delta is the maximum degree. When Delta=O(n^(1/3)), the bound improves to O(log Delta).

Adapting the above to the CONGEST model gives an O(D log^2 n)-round deterministic MIS algorithm, where D is the diameter of the graph. Apart from a previous unproven claim of a O(D log^3 n)-round algorithm, the only known deterministic solutions for the CONGEST model are a coloring-based O(Delta + log^* n)-round algorithm, where Delta is the maximal degree in the graph, and a 2^O(sqrt(log n log log n))-round algorithm, which is super-polylogarithmic in n.

In addition, we deterministically construct a (2k-1)-spanner with O(kn^(1+1/k) log n) edges in O(k log n) rounds in the Congested Clique model. For comparison, in the more stringent CONGEST model, where the communication graph is identical to the input graph, the best deterministic algorithm for constructing a (2k-1)-spanner with O(kn^(1+1/k)) edges runs in O(n^(1-1/k)) rounds.

Subject Classification

Keywords
  • Local problems
  • congested clique
  • derandomization

Metrics

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

References

  1. Noga Alon, László Babai, and Alon Itai. A fast and simple randomized parallel algorithm for the maximal independent set problem. Journal of algorithms, 7(4):567-583, 1986. Google Scholar
  2. Baruch Awerbuch, Andrew V. Goldberg, Michael Luby, and Serge A. Plotkin. Network decomposition and locality in distributed computation. In FOCS, pages 364-369, 1989. Google Scholar
  3. Leonid Barenboim. Deterministic (Δ + 1)-coloring in sublinear (in Δ) time in static, dynamic, and faulty networks. J. ACM, 63(5):47:1-47:22, 2016. Google Scholar
  4. Leonid Barenboim and Michael Elkin. Distributed graph coloring: Fundamentals and recent developments. Synthesis Lectures on Distributed Computing Theory, 4(1):1-171, 2013. Google Scholar
  5. Leonid Barenboim, Michael Elkin, and Cyril Gavoille. A fast network-decomposition algorithm and its applications to constant-time distributed computation. In SIROCCO, pages 209-223, 2015. Google Scholar
  6. Leonid Barenboim, Michael Elkin, and Fabian Kuhn. Distributed (delta+1)-coloring in linear (in delta) time. SIAM J. Comput., 43(1):72-95, 2014. Google Scholar
  7. Leonid Barenboim, Michael Elkin, Seth Pettie, and Johannes Schneider. The locality of distributed symmetry breaking. J. ACM, 63(3):20:1-20:45, 2016. 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. Bonnie Berger and John Rompel. Simulating (log cn)-wise independence in nc. Journal of the ACM (JACM), 38(4):1026-1046, 1991. Google Scholar
  10. Sebastian Brandt, Orr Fischer, Juho Hirvonen, Barbara Keller, Tuomo Lempiäinen, Joel Rybicki, Jukka Suomela, and Jara Uitto. A lower bound for the distributed lovász local lemma. In STOC, pages 479-488, 2016. Google Scholar
  11. Keren Censor-Hillel, Petteri Kaski, Janne H. Korhonen, Christoph Lenzen, Ami Paz, and Jukka Suomela. Algebraic methods in the congested clique. In PODC, pages 143-152, 2015. Google Scholar
  12. Keren Censor-Hillel, Merav Parter, and Gregory Schwartzman. Derandomizing local distributed algorithms under bandwidth restrictions. arXiv preprint arXiv:1608.01689, 2016. URL: https://arxiv.org/abs/1608.01689.
  13. Karthekeyan Chandrasekaran, Navin Goyal, and Bernhard Haeupler. Deterministic algorithms for the lovász local lemma. SIAM Journal on Computing, 42(6):2132-2155, 2013. Google Scholar
  14. Yi-Jun Chang, Tsvi Kopelowitz, and Seth Pettie. An exponential separation between randomized and deterministic complexity in the LOCAL model. In FOCS, pages 615-624, 2016. Google Scholar
  15. Bilel Derbel and Cyril Gavoille. Fast deterministic distributed algorithms for sparse spanners. Theor. Comput. Sci., 399(1-2):83-100, 2008. Google Scholar
  16. Bilel Derbel, Cyril Gavoille, and David Peleg. Deterministic distributed construction of linear stretch spanners in polylogarithmic time. In DISC, pages 179-192, 2007. Google Scholar
  17. 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
  18. Bilel Derbel, Cyril Gavoille, David Peleg, and Laurent Viennot. Local computation of nearly additive spanners. In DISC, pages 176-190, 2009. Google Scholar
  19. Bilel Derbel, Mohamed Mosbah, and Akka Zemmari. Sublinear fully distributed partition with applications. Theory of Computing Systems, 47(2):368-404, 2010. Google Scholar
  20. Danny Dolev, Christoph Lenzen, and Shir Peled. "tri, tri again": Finding triangles and small subgraphs in a distributed setting - (extended abstract). In DISC, pages 195-209, 2012. Google Scholar
  21. Andrew Drucker, Fabian Kuhn, and Rotem Oshman. On the power of the congested clique model. In PODC, pages 367-376, 2014. Google Scholar
  22. Michael Elkin. A faster distributed protocol for constructing a minimum spanning tree. J. Comput. Syst. Sci., 72(8):1282-1308, 2006. Google Scholar
  23. Michael Elkin. A near-optimal distributed fully dynamic algorithm for maintaining sparse spanners. In PODC, pages 185-194, 2007. Google Scholar
  24. Laurent Feuilloley and Pierre Fraigniaud. Randomized local network computing. In SPAA, pages 340-349, 2015. Google Scholar
  25. François Le Gall. Further algebraic algorithms in the congested clique model and applications to graph-theoretic problems. In DISC, pages 57-70, 2016. Google Scholar
  26. Mohsen Ghaffari. An improved distributed algorithm for maximal independent set. In SODA, pages 270-277, 2016. Google Scholar
  27. Mohsen Ghaffari and Merav Parter. Mst in log-star rounds of congested clique. In PODC, pages 19-28, 2016. Google Scholar
  28. Mark Goldberg and Thomas Spencer. A new parallel algorithm for the maximal independent set problem. SIAM Journal on Computing, 18(2):419-427, 1989. Google Scholar
  29. Yijie Han. A fast derandomization scheme and its applications. SIAM Journal on Computing, 25(1):52-82, 1996. Google Scholar
  30. James W. Hegeman, Gopal Pandurangan, Sriram V. Pemmaraju, Vivek B. Sardeshmukh, and Michele Scquizzato. Toward optimal bounds in the congested clique: Graph connectivity and MST. In PODC, pages 91-100, 2015. Google Scholar
  31. James W. Hegeman and Sriram V. Pemmaraju. Lessons from the congested clique applied to mapreduce. In SIROCCO, pages 149-164, 2014. Google Scholar
  32. James W. Hegeman, Sriram V. Pemmaraju, and Vivek Sardeshmukh. Near-constant-time distributed algorithms on a congested clique. In DISC, pages 514-530, 2014. Google Scholar
  33. Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. A deterministic almost-tight distributed algorithm for approximating single-source shortest paths. In STOC, pages 489-498, 2016. Google Scholar
  34. Stephan Holzer and Nathan Pinsker. Approximation of distances and shortest paths in the broadcast congest clique. In OPODIS, pages 6:1-6:16, 2015. Google Scholar
  35. Amos Israeli and Alon Itai. A fast and simple randomized parallel algorithm for maximal matching. Inf. Process. Lett., 22(2):77-80, 1986. Google Scholar
  36. Richard M Karp and Avi Wigderson. A fast parallel algorithm for the maximal independent set problem. In STOC, pages 266-272, 1984. Google Scholar
  37. Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer. Local computation: Lower and upper bounds. J. ACM, 63(2):17, 2016. Google Scholar
  38. Christoph Lenzen. Optimal deterministic routing and sorting on the congested clique. In PODC, pages 42-50, 2013. Google Scholar
  39. Christoph Lenzen and Roger Wattenhofer. Tight bounds for parallel randomized load balancing: extended abstract. In STOC, pages 11-20, 2011. Google Scholar
  40. Nathan Linial. Locality in distributed graph algorithms. SIAM Journal on Computing, 21(1):193-201, 1992. Google Scholar
  41. Zvi Lotker, Elan Pavlov, Boaz Patt-Shamir, and David Peleg. MST construction in O(log log n) communication rounds. In SPAA, pages 94-100, 2003. Google Scholar
  42. Michael Luby. A simple parallel algorithm for the maximal independent set problem. SIAM journal on computing, 15(4):1036-1053, 1986. Google Scholar
  43. Michael Luby. Removing randomness in parallel computation without a processor penalty. Journal of Computer and System Sciences, 47(2):250-286, 1993. Google Scholar
  44. Michael Mitzenmacher and Eli Upfal. Probability and computing - randomized algorithms and probabilistic analysis. Cambridge University Press, 2005. Google Scholar
  45. Rajeev Motwani, Joseph Naor, and Moni Naor. The probabilistic method yields deterministic parallel algorithms. J. Comput. Syst. Sci., 49(3):478-516, 1994. Google Scholar
  46. Danupon Nanongkai. Distributed approximation algorithms for weighted shortest paths. In STOC, pages 565-573, 2014. Google Scholar
  47. Moni Naor and Larry J. Stockmeyer. What can be computed locally? SIAM J. Comput., 24(6):1259-1277, 1995. Google Scholar
  48. Alessandro Panconesi and Aravind Srinivasan. Improved distributed algorithms for coloring and network decomposition problems. In STOC, pages 581-592, 1992. Google Scholar
  49. Alessandro Panconesi and Aravind Srinivasan. On the complexity of distributed network decomposition. J. Algorithms, 20(2):356-374, 1996. Google Scholar
  50. Grammati Pantziou, Paul Spirakis, and Christos Zaroliagis. Fast parallel approximations of the maximum weighted cut problem through derandomization. In FSTTCS, pages 20-29, 1989. Google Scholar
  51. Boaz Patt-Shamir and Marat Teplitsky. The round complexity of distributed sorting: extended abstract. In PODC, pages 249-256, 2011. Google Scholar
  52. Seth Pettie. Distributed algorithms for ultrasparse spanners and linear size skeletons. Distributed Computing, 22(3):147-166, 2010. Google Scholar
  53. Liam Roditty, Mikkel Thorup, and Uri Zwick. Deterministic constructions of approximate distance oracles and spanners. In ICALP, pages 261-272, 2005. Google Scholar
  54. Anand Srivastav and Lasse Kliemann. Parallel algorithms via the probabilistic method. In Handbook of Parallel Computing - Models, Algorithms and Applications. Chapman and Hall/CRC, 2007. Google Scholar
  55. Jukka Suomela. Survey of local algorithms. ACM Comput. Surv., 45(2):24, 2013. Google Scholar
  56. Salil P. Vadhan. Pseudorandomness. Foundations and Trends in Theoretical Computer Science, 7(1-3):1-336, 2012. 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