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

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

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)

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

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)