Análise de complexidade de tempo para o modelo Map-Reduce

Estou tentando redesenhar meu algoritmo para executar no paradigma Hadoop / MapReduce. Fiquei me perguntando se existe alguma abordagem holística para medir a complexidade do tempo para algoritmos nas plataformas de Big Data.

Como um exemplo simples, a média de n (= 1 bilhão) de números pode ser feita em O (n) + C (assumindo que a divisão seja uma operação em tempo constante). Se eu quebrar esse algoritmo massivamente paralelelizável para Map Reduce, dividindo dados em k nós, minha complexidade de tempo simplesmente se tornaria O (n / k) + C + C '. Aqui, C 'pode ser assumido como a sobrecarga do tempo de planejamento da tarefa de inicialização. Observe que não havia embaralhamento envolvido, e o trabalho do redutor era quase trivial.

Estou interessado em uma análise mais completa do algoritmo com loops iterativos sobre dados e envolva operações pesadas de embaralhamento e redutor. Quero incorporar, se possível, as operações de E / S e as transferências de dados na rede.

S. Arora, B. Barak, Abordagem moderna da complexidade computacional, o capítulo 13 é um bom recurso introdutório para este tópico:

A complexidade da comunicação diz respeito ao seguinte cenário. Existem dois jogadores com poder computacional ilimitado, cada um com uma$n$ entrada de bits, digamos $x$ e $y$. Nenhum dos dois conhece a opinião do outro e deseja calcular de forma colaborativa$f(x, y)$ onde a função $f : \{0, 1\}^n \times \{0, 1\}^n \rightarrow \{0, 1\}$é conhecido por ambos. Além disso, eles previram essa situação (por exemplo, uma das partes poderia ser uma espaçonave e a outra a estação base na Terra), então já havia - antes que soubessem suas informações.$x, y$- concordou com um protocolo de comunicação. O custo desse protocolo é o número de bits comunicados pelos players para a pior escolha de entradas$x, y$.

Veja que você está certo, mas sabe que é muito difícil dizer uma complexidade de tempo específica da redução de mapas. Depende da consulta. Mas nesse caso, deve ser o (nlogn / k) + c + c 'por causa de k nós. Essas curtas consultas, incluindo uma fase de mapeamento de um mapa que reduz a técnica, seguem um conceito Btree. Portanto, a partir desse local para cálculos internos, podemos dizer que sua complexidade de tempo é> o (nlogn) + c + c '.

Corrija minhas sugestões, por favor.