Lessons from the congested clique applied to MapReduce

DOI10.1016/J.TCS.2015.09.029MaRDI QIDQ896148zbMATH OpenOpenAlexFDO

Authors James W. Hegeman, Sriram Pemmaraju

Publication date 11 December 2015

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2015.09.029

zbMATH Keywords

distributed algorithmsgraph coloringMapReducecongested clique

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Coloring of graphs and hypergraphs (05C15) Distributed algorithms (68W15)

Recommendations

• Lessons from the Congested Clique Applied to MapReduce
• scientific article; zbMATH DE number 6297759
• \((\Delta+1)\) coloring in the congested clique model
• On the power of the congested clique model
• Randomized (Delta+1)-Coloring in O(log* Delta) Congested Clique Rounds

Cites work

• scientific article; zbMATH DE number 44281 (Why is no real title available?)
• scientific article; zbMATH DE number 6297759 (Why is no real title available?)
• A Distributed Algorithm for the Facility Location Problem
• A Plant and Warehouse Location Problem
• Approximation of distances and shortest paths in the broadcast congest clique
• Distributed Computing: A Locality-Sensitive Approach
• Distributed MST for constant diameter graphs
• Distributed approximation algorithms for weighted shortest paths
• Facility location, distributed approximation
• Minimum-Weight Spanning Tree Construction in O(log log n) Communication Rounds
• On the power of the congested clique model
• Optimal deterministic routing and sorting on the congested clique
• Rapid randomized pruning for fast greedy distributed algorithms
• Return of the primal-dual, distributed metric facility location
• Simple distributed +1-coloring of graphs
• Super-fast 3-ruling sets
• Super-fast distributed algorithms for metric facility location
• Symmetry breaking depending on the chromatic number or the neighborhood growth
• The communication complexity of distributed task allocation
• The round complexity of distributed sorting, extended abstract
• Toward optimal bounds in the congested clique, graph connectivity and MST
• ``Tri, tri again: finding triangles and small subgraphs in a distributed setting (extended abstract)

Cited in

(17)

• Distributed computing with the Cloud
• scientific article; zbMATH DE number 7561635 (Why is no real title available?)
• Distributed Computing with the Cloud
• Streaming graph algorithms in the massively parallel computation model
• Equivalence classes and conditional hardness in massively parallel computations
• Congested clique algorithms for graph spanners
• Large-scale distributed algorithms for facility location with outliers
• Randomized (Delta+1)-Coloring in O(log* Delta) Congested Clique Rounds
• Sparsifying congested cliques and core-periphery networks
• Lessons from the Congested Clique Applied to MapReduce
• Distributed approximation algorithms for Steiner tree in the CONGESTED CLIQUE
• Constant-round spanners and shortest paths in congested clique and MPC
• Distributed PageRank computation with improved round complexities
• Sorting, searching, and simulation in the MapReduce framework
• \((\Delta+1)\) coloring in the congested clique model
• Fast approximate shortest paths in the congested clique
• The message complexity of distributed graph optimization

Describes a project that uses

Uses Software

• MapReduce

This page was built for publication: Lessons from the congested clique applied to MapReduce

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