Book chapter
Lessons from the Congested Clique Applied to MapReduce
Structural Information and Communication Complexity, pp.149-164
Lecture Notes in Computer Science, Springer International Publishing
2014
DOI: 10.1007/978-3-319-09620-9_13
Abstract
The main results of this paper are (I) a simulation algorithm which, under quite general constraints, transforms algorithms running on the Congested Clique into algorithms running in the MapReduce model, and (II) a distributed O(Δ)-coloring algorithm running on the Congested Clique which has an expected running time of O(1) rounds, if Δ ≥ Θ(log4n); and O(logloglogn) rounds otherwise. Applying the simulation theorem to the Congested Clique O(Δ)-coloring algorithm yields an O(1)-round O(Δ)-coloring algorithm in the MapReduce model.
Our simulation algorithm illustrates a natural correspondence between per-node bandwidth in the Congested Clique model and memory per machine in the MapReduce model. In the Congested Clique (and more generally, any network in the \documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$\mathcal{CONGEST}$\end{document} model), the major impediment to constructing fast algorithms is the O(logn) restriction on message sizes. Similarly, in the MapReduce model, the combined restrictions on memory per machine and total system memory have a dominant effect on algorithm design. In showing a fairly general simulation algorithm, we highlight the similarities and differences between these models.
Details
- Title: Subtitle
- Lessons from the Congested Clique Applied to MapReduce
- Creators
- James W. Hegeman - University of IowaSriram V. Pemmaraju - University of Iowa
- Resource Type
- Book chapter
- Publication Details
- Structural Information and Communication Complexity, pp.149-164
- Publisher
- Springer International Publishing; Cham
- Series
- Lecture Notes in Computer Science
- DOI
- 10.1007/978-3-319-09620-9_13
- eISSN
- 1611-3349
- ISSN
- 0302-9743
- Language
- English
- Date published
- 2014
- Academic Unit
- Computer Science
- Record Identifier
- 9984259436302771
Metrics
11 Record Views