Lessons from the Congested Clique Applied to MapReduce
2014
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 Δ ≥ Θ(log4 n); 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.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
16
References
31
Citations
NaN
KQI