Lessons from the Congested Clique applied to MapReduce

详细信息    查看全文

• 作者：James W. Hegeman ^{james-hegeman@uiowa.edu" class="auth_mail" title="E-mail the corresponding author} ; Sriram V. Pemmaraju ; ^{sriram-pemmaraju@uiowa.edu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Congested Clique ; Distributed algorithms ; Graph coloring ; MapReduce
• 刊名：Theoretical Computer Science
• 出版年：2015
• 出版时间：10 December 2015
• 年：2015
• 卷：608
• 期：part_P3
• 页码：268-281
• 全文大小：495 K

文摘

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 class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397515008695&_mathId=si1.gif&_user=111111111&_pii=S0304397515008695&_rdoc=1&_issn=03043975&md5=38e9a1423056fcf851fc6cfbefaa9732" title="Click to view the MathML source">O(Δ)class="mathContainer hidden">class="mathCode">$O(\mathrm{\Delta })$-coloring algorithm running on the Congested Clique in class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397515008695&_mathId=si2.gif&_user=111111111&_pii=S0304397515008695&_rdoc=1&_issn=03043975&md5=80f8f8d84ce207017084fc9b3f2b623c" title="Click to view the MathML source">O(1)class="mathContainer hidden">class="mathCode">$O(1)$ rounds, if class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397515008695&_mathId=si3.gif&_user=111111111&_pii=S0304397515008695&_rdoc=1&_issn=03043975&md5=079f59f7730665dfd893c87fff2d781c" title="Click to view the MathML source">Δ≥log²⁡nclass="mathContainer hidden">class="mathCode">$\mathrm{\Delta }\ge {\log }^{2}n$, and class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397515008695&_mathId=si4.gif&_user=111111111&_pii=S0304397515008695&_rdoc=1&_issn=03043975&md5=1c5a53c00f1489b6acdd1fae25487fcc" title="Click to view the MathML source">O(log⁡log⁡log⁡n)class="mathContainer hidden">class="mathCode">$O(\log \log \log n)$ rounds otherwise. Applying the simulation theorem to this Congested Clique class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397515008695&_mathId=si1.gif&_user=111111111&_pii=S0304397515008695&_rdoc=1&_issn=03043975&md5=38e9a1423056fcf851fc6cfbefaa9732" title="Click to view the MathML source">O(Δ)class="mathContainer hidden">class="mathCode">$O(\mathrm{\Delta })$-coloring algorithm yields an class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397515008695&_mathId=si2.gif&_user=111111111&_pii=S0304397515008695&_rdoc=1&_issn=03043975&md5=80f8f8d84ce207017084fc9b3f2b623c" title="Click to view the MathML source">O(1)class="mathContainer hidden">class="mathCode">$O(1)$-round class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397515008695&_mathId=si1.gif&_user=111111111&_pii=S0304397515008695&_rdoc=1&_issn=03043975&md5=38e9a1423056fcf851fc6cfbefaa9732" title="Click to view the MathML source">O(Δ)class="mathContainer hidden">class="mathCode">$O(\mathrm{\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 class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397515008695&_mathId=si5.gif&_user=111111111&_pii=S0304397515008695&_rdoc=1&_issn=03043975&md5=3545df5a5c2f883f8063e550385a2490" title="Click to view the MathML source">CONGESTclass="mathContainer hidden">class="mathCode">$\mathcal{CONGEST}$ model), the major impediment to constructing fast algorithms is the class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397515008695&_mathId=si6.gif&_user=111111111&_pii=S0304397515008695&_rdoc=1&_issn=03043975&md5=e75bce3f9e2f6e62044920524ba8f484" title="Click to view the MathML source">O(log⁡n)class="mathContainer hidden">class="mathCode">$O(\log n)$ 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.