Distributed computation of large-scale graph problems

DOI10.1137/1.9781611973730.28MaRDI QIDQ5362982zbMATH OpenOpenAlexFDO

Authors Hartmut Klauck, Danupon Nanongkai, Gopal Pandurangan, Peter Robinson

Publication date 5 October 2017

Published in Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1311.6209

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Distributed algorithms (68W15) Network protocols (68M12)

Abstract: Motivated by the increasing need for fast processing of large-scale graphs, we study a number of fundamental graph problems in a message-passing model for distributed computing, called $k$-machine model, where we have $k$ machines that jointly perform computations on $n$-node graphs. The graph is assumed to be partitioned in a balanced fashion among the $k$ machines, a common implementation in many real-world systems. Communication is point-to-point via bandwidth-constrained links, and the goal is to minimize the round complexity, i.e., the number of communication rounds required to finish a computation. We present a generic methodology that allows to obtain efficient algorithms in the $k$-machine model using distributed algorithms for the classical CONGEST model of distributed computing. Using this methodology, we obtain algorithms for various fundamental graph problems such as connectivity, minimum spanning trees, shortest paths, maximal independent sets, and finding subgraphs, showing that many of these problems can be solved in $ildeO(n/k)$ rounds; this shows that one can achieve speedup nearly linear in $k$. To complement our upper bounds, we present lower bounds on the round complexity that quantify the fundamental limitations of solving graph problems distributively. We first show a lower bound of $Omega(n/k)$ rounds for computing a spanning tree of the input graph. This result implies the same bound for other fundamental problems such as computing a minimum spanning tree, breadth-first tree, or shortest paths tree. We also show a $ildeOmega(n/k^2)$ lower bound for connectivity, spanning tree verification and other related problems. The latter lower bounds follow from the development and application of novel results in a random-partition variant of the classical communication complexity model.

Recommendations

• Distributed verification and hardness of distributed approximation
• Distributed verification and hardness of distributed approximation
• Low-complexity distributed algorithms on large-scale graphs: a brief review
• Fast distributed PageRank computation

Cited in

(21)

• Communication complexity of approximate maximum matching in the message-passing model
• Near-optimal scheduling in the congested clique
• Extended dependency graphs and efficient distributed fixed-point computation
• Brief announcement: MapReduce algorithms for massive trees
• Equivalence classes and conditional hardness in massively parallel computations
• Message lower bounds via efficient network synchronization
• Large-scale distributed algorithms for facility location with outliers
• Message Lower Bounds via Efficient Network Synchronization
• Graph partitioning for scalable distributed graph computations
• Sub-logarithmic distributed algorithms for metric facility location
• Distributed approximation algorithms for Steiner tree in the CONGESTED CLIQUE
• Distributed subgraph finding: progress and challenges (invited talk)
• Sparse matrix multiplication and triangle listing in the congested clique model
• Distributed PageRank computation with improved round complexities
• Near-optimal clustering in the \(k\)-machine model
• Graph reconstruction in the congested clique
• Low-complexity distributed algorithms on large-scale graphs: a brief review
• Sparse matrix multiplication and triangle listing in the congested clique model
• Dynamic maximal matching in clique networks
• The message complexity of distributed graph optimization
• Time-message trade-offs in distributed algorithms

This page was built for publication: Distributed computation of large-scale graph problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5362982)