Document Open Access Logo

New Distributed Algorithms in Almost Mixing Time via Transformations from Parallel Algorithms

Authors Mohsen Ghaffari, Jason Li

PDF
Thumbnail PDF

File

LIPIcs.DISC.2018.31.pdf
  • Filesize: 488 kB
  • 16 pages

Document Identifiers

Author Details

Mohsen Ghaffari
  • ETH Zurich, Switzerland
Jason Li
  • Carnegie Mellon University, USA, http://cs.cmu.edu/~jmli

Cite As Get BibTex

Mohsen Ghaffari and Jason Li. New Distributed Algorithms in Almost Mixing Time via Transformations from Parallel Algorithms. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 31:1-31:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.DISC.2018.31

Abstract

We show that many classical optimization problems - such as (1 +/- epsilon)-approximate maximum flow, shortest path, and transshipment - can be computed in tau_{mix}(G)* n^o(1) rounds of distributed message passing, where tau_{mix}(G) is the mixing time of the network graph G. This extends the result of Ghaffari et al. [PODC'17], whose main result is a distributed MST algorithm in tau_{mix}(G)* 2^O(sqrt{log n log log n}) rounds in the CONGEST model, to a much wider class of optimization problems. For many practical networks of interest, e.g., peer-to-peer or overlay network structures, the mixing time tau_{mix}(G) is small, e.g., polylogarithmic. On these networks, our algorithms bypass the Omega(sqrt n+D) lower bound of Das Sarma et al. [STOC'11], which applies for worst-case graphs and applies to all of the above optimization problems. For all of the problems except MST, this is the first distributed algorithm which takes o(sqrt n) rounds on a (nontrivial) restricted class of network graphs.
Towards deriving these improved distributed algorithms, our main contribution is a general transformation that simulates any work-efficient PRAM algorithm running in T parallel rounds via a distributed algorithm running in T * tau_{mix}(G)* 2^O(sqrt{log n}) rounds. Work- and time-efficient parallel algorithms for all of the aforementioned problems follow by combining the work of Sherman [FOCS'13, SODA'17] and Peng and Spielman [STOC'14]. Thus, simulating these parallel algorithms using our transformation framework produces the desired distributed algorithms.
The core technical component of our transformation is the algorithmic problem of solving multi-commodity routing - that is, roughly, routing n packets each from a given source to a given destination - in random graphs. For this problem, we obtain a new algorithm running in 2^O(sqrt{log n}) rounds, improving on the 2^O(sqrt{log n log log n}) round algorithm of Ghaffari, Kuhn, and Su [PODC'17]. As a consequence, for the MST problem in particular, we obtain an improved distributed algorithm running in tau_{mix}(G)* 2^O(sqrt{log n}) rounds.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
Keywords
  • Distributed Graph Algorithms
  • Mixing Time
  • Random Graphs
  • Multi-Commodity Routing

Metrics

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

References

  1. Noga Alon and Joel H Spencer. The probabilistic method. John Wiley &Sons, 2004. Google Scholar
  2. John Augustine, Gopal Pandurangan, Peter Robinson, Scott Roche, and Eli Upfal. Enabling robust and efficient distributed computation in dynamic peer-to-peer networks. In Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium on, pages 350-369. IEEE, 2015. Google Scholar
  3. Baruch Awerbuch and Christian Scheideler. The hyperring: a low-congestion deterministic data structure for distributed environments. In Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, pages 318-327. Society for Industrial and Applied Mathematics, 2004. Google Scholar
  4. Ruben Becker, Andreas Karrenbauer, Sebastian Krinninger, and Christoph Lenzen. Near-optimal approximate shortest paths and transshipment in distributed and streaming models. arXiv preprint arXiv:1607.05127, 2016. Google Scholar
  5. Soumyottam Chatterjee, Reza Fathi, Gopal Pandurangan, and Nguyen Dinh Pham. Fast and efficient distributed computation of hamiltonian cycles in random graphs. arXiv preprint arXiv:1804.08819, 2018. Google Scholar
  6. Colin Cooper and Alan Frieze. Random walks on random graphs. In International Conference on Nano-Networks, pages 95-106. Springer, 2008. Google Scholar
  7. Don Coppersmith, Prabhakar Raghavan, and Martin Tompa. Parallel graph algorithms that are efficient on average. In Foundations of Computer Science, 1987., 28th Annual Symposium on, pages 260-269. IEEE, 1987. Google Scholar
  8. David Culler, Richard Karp, David Patterson, Abhijit Sahay, Klaus Erik Schauser, Eunice Santos, Ramesh Subramonian, and Thorsten Von Eicken. Logp: Towards a realistic model of parallel computation. ACM Sigplan Notices, 28(7):1-12, 1993. Google Scholar
  9. Paul Erdös and Alfréd Rényi. On random graphs, i. Publicationes Mathematicae (Debrecen), 6:290-297, 1959. Google Scholar
  10. Carlo Fantozzi, Andrea Pietracaprina, and Geppino Pucci. A general pram simulation scheme for clustered machines. International Journal of Foundations of Computer Science, 14(06):1147-1164, 2003. Google Scholar
  11. Steven Fortune and James Wyllie. Parallelism in random access machines. In Proc. of the Symp. on Theory of Comp. (STOC), pages 114-118. ACM, 1978. Google Scholar
  12. Mohsen Ghaffari and Bernhard Haeupler. Distributed algorithms for planar networks ii: Low-congestion shortcuts, mst, and min-cut. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pages 202-219. Society for Industrial and Applied Mathematics, 2016. Google Scholar
  13. Mohsen Ghaffari, Fabian Kuhn, and Hsin-Hao Su. Distributed mst and routing in almost mixing time. In Proceedings of the ACM Symposium on Principles of Distributed Computing, pages 131-140. ACM, 2017. Google Scholar
  14. Leslie M Goldschlager. A unified approach to models of synchronous parallel machines. In Proc. of the Symp. on Theory of Comp. (STOC), pages 89-94. ACM, 1978. Google Scholar
  15. Richard M Karp. A survey of parallel algorithms for shared-memory machines. Technical report, University of California at Berkeley, 1988. Google Scholar
  16. Richard M Karp, Michael Luby, and F Meyer auf der Heide. Efficient pram simulation on a distributed memory machine. Algorithmica, 16(4-5):517-542, 1996. Google Scholar
  17. K Krzywdziński and Katarzyna Rybarczyk. Distributed algorithms for random graphs. Theoretical Computer Science, 605:95-105, 2015. Google Scholar
  18. Vipin Kumar, Ananth Grama, Anshul Gupta, and George Karypis. Introduction to parallel computing: design and analysis of algorithms, volume 400. Benjamin/Cummings Redwood City, 1994. Google Scholar
  19. Richard E Ladner and Michael J Fischer. Parallel prefix computation. Journal of the ACM (JACM), 27(4):831-838, 1980. Google Scholar
  20. Ching Law and Kai-Yeung Siu. Distributed construction of random expander networks. In INFOCOM 2003. Twenty-Second Annual Joint Conference of the IEEE Computer and Communications. IEEE Societies, volume 3, pages 2133-2143. IEEE, 2003. Google Scholar
  21. Tom Leighton, Bruce Maggs, and Satish Rao. Universal packet routing algorithms. In Foundations of Computer Science, 1988., 29th Annual Symposium on, pages 256-269. IEEE, 1988. Google Scholar
  22. Eythan Levy, Guy Louchard, and Jordi Petit. A distributed algorithm to find hamiltonian cycles in g(n,p) random graphs. In Workshop on Combinatorial and Algorithmic aspects of networking, pages 63-74. Springer, 2004. Google Scholar
  23. Peter Mahlmann and Christian Schindelhauer. Peer-to-peer networks based on random transformations of connected regular undirected graphs. In Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, pages 155-164. ACM, 2005. Google Scholar
  24. Gopal Pandurangan, Prabhakar Raghavan, and Eli Upfal. Building low-diameter peer-to-peer networks. Selected Areas in Communications, IEEE Journal on, 21(6):995-1002, 2003. Google Scholar
  25. Gopal Pandurangan, Peter Robinson, and Amitabh Trehan. Dex: self-healing expanders. In Parallel and Distributed Processing Symposium, 2014 IEEE 28th International, pages 702-711. IEEE, 2014. Google Scholar
  26. Gopal Pandurangan and Amitabh Trehan. Xheal: localized self-healing using expanders. In Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing, pages 301-310. ACM, 2011. Google Scholar
  27. David Peleg. Distributed Computing: A Locality-sensitive Approach. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2000. Google Scholar
  28. Richard Peng and Daniel A Spielman. An efficient parallel solver for sdd linear systems. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 333-342. ACM, 2014. Google Scholar
  29. Andrea Pietracaprina and Geppino Pucci. The complexity of deterministic pram simulation on distributed memory machines. Theory of Computing Systems, 30(3):231-247, 1997. Google Scholar
  30. Walter J Savitch and Michael J Stimson. Time bounded random access machines with parallel processing. Journal of the ACM (JACM), 26(1):103-118, 1979. Google Scholar
  31. Jonah Sherman. Nearly maximum flows in nearly linear time. In Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium on, pages 263-269. IEEE, 2013. Google Scholar
  32. Jonah Sherman. Generalized preconditioning and undirected minimum-cost flow. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 772-780. SIAM, 2017. Google Scholar
  33. Ion Stoica, Robert Morris, David Karger, M Frans Kaashoek, and Hari Balakrishnan. Chord: A scalable peer-to-peer lookup service for internet applications. ACM SIGCOMM Computer Communication Review, 31(4):149-160, 2001. Google Scholar
  34. Leslie G Valiant. A bridging model for parallel computation. Communications of the ACM, 33(8):103-111, 1990. 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