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

congested cliquedistributed algorithmsgraph coloringMapReduce

Mathematics Subject Classification ID

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

• ``Tri, tri again: finding triangles and small subgraphs in a distributed setting (extended abstract)
• 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 approximation algorithms for weighted shortest paths
• Distributed Computing: A Locality-Sensitive Approach
• Distributed MST for constant diameter graphs
• Facility location, distributed approximation
• scientific article; zbMATH DE number 44281 (Why is no real title available?)
• scientific article; zbMATH DE number 6297759 (Why is no real title available?)
• 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

Cited in

(18)

• Fast approximate shortest paths in the congested clique
• Equivalence classes and conditional hardness in massively parallel computations
• Sparsifying congested cliques and core-periphery networks
• Sorting, searching, and simulation in the MapReduce framework
• \((\Delta+1)\) coloring in the congested clique model
• Randomized (Delta+1)-Coloring in O(log* Delta) Congested Clique Rounds
• Congested clique algorithms for graph spanners
• Large-scale distributed algorithms for facility location with outliers
• Distributed arboricity-dependent graph coloring via all-to-all communication
• Lessons from the Congested Clique Applied to MapReduce
• Distributed approximation algorithms for Steiner tree in the CONGESTED CLIQUE
• Distributed computing with the Cloud
• Distributed PageRank computation with improved round complexities
• Distributed Computing with the Cloud
• The message complexity of distributed graph optimization
• Streaming graph algorithms in the massively parallel computation model
• Constant-round spanners and shortest paths in congested clique and MPC
• Optimal (degree+1)-coloring in congested clique

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)