Logo image
Back
Lessons from the Congested Clique applied to Map Reduce
Journal article   Open access   Peer reviewed

Lessons from the Congested Clique applied to Map Reduce

James W. Hegeman and Sriram V. Pemmaraju
Theoretical computer science, Vol.608, pp.268-281
12/10/2015
DOI: 10.1016/j.tcs.2015.09.029
url
https://doi.org/10.1016/j.tcs.2015.09.029View
Published (Version of record) Open Access

Abstract

The main result of this paper is a simulation algorithm which, under quite general constraints, transforms algorithms running in the Congested Clique model into algorithms running in the MapReduce model. As a case study of applying this simulation algorithm, we first present a distributed O (Delta)-coloring algorithm running on the Congested Clique in O (1) rounds, if Delta >= log(2) n, and O (log log logn) rounds otherwise. Applying the simulation theorem to this Congested Clique O (A)-coloring algorithm yields an O(1)-round O (Delta)-coloring algorithm in the MapReduce model. We apply our simulation algorithm to other Congested Clique algorithms including the 2-ruling set and metric facility location algorithms of Berns et al. (ICALP 2012). 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 CONGEST 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. (C) 2015 Elsevier B.V. All rights reserved.
 Computer Science Computer Science, Theory & Methods Science & Technology Technology

Details

Metrics

23 Record Views
36 Times Cited - Web of Science
Logo image