Abstrakt. De viktigaste resultaten av detta dokument är (I) en simuleringsalgoritm som, under ganska allmänna begränsningar, omvandlar algoritmer som körs på den överbelastade klichén till algoritmer som körs i MapReduce-modellen, och (II) en distribuerad O-färgsalgoritm som körs på den överbelastade klichén som har en förväntad körtid för O(1)-rundor, om  till ≥  till (log 4 n); och O(logglogglogglogg n) rundor annars. Applicering av simuleringsteoremet till den överbelastade Clique O-färgningsalgoritmen ger en O(1)-runda O-färgningsalgoritm i MapReduce-modellen. Vår simuleringsalgoritm illustrerar en naturlig korrelation mellan pernoden bandbredd i den överbelastade Clique-modellen och minnet per maskin i MapReduce-modellen. I den överbelastade Clique (och mer allmänt, vilket nätverk som helst i CON GE ST-modellen) är det största hindret för att bygga snabba algoritmer begränsningen O(log n) för meddelandestorlekar. I MapReduce-modellen har de kombinerade begränsningarna för minne per maskin och totalt systemminne en dominerande effekt på algoritmdesignen. Genom att visa en ganska allmän simuleringsalgoritm lyfter vi fram likheterna och skillnaderna mellan dessa modeller.
En koppling mellan den överbelastade klickmodellen och MapReduce-modellen diskuteras av Hegeman och Pemmaraju REF, där algoritmer ges för färgproblem.
Lessons from the Congested Clique Applied to MapReduce
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}