Tenga en cuenta que el modelo MR generalmente implica el cálculo completo de Turing en cada nodo, por lo que formalmente bajo este supuesto, todos los algoritmos computables se pueden mapear a MR.
Sin embargo, una pregunta relacionada interesante (y lo que sospecho que le interesa) es: ¿qué algoritmos pueden asignarse eficientemente a MR, y qué algoritmos pueden asignarse eficientemente a implementaciones de MR ‘realistas’?
Un artículo en SODA el año pasado por Karloff et. Alabama. [1] demostró que una gran clase de algoritmos en PRAM [2] puede ser simulada eficientemente por MR. Los detalles están en el documento y también están un poco detallados para repetirlos completamente aquí.
- ¿Cuál es la diferencia entre quicksort y mergesort?
- ¿Cuáles son los algoritmos más utilizados en los que puedo confiar para mejorar mis habilidades de resolución de problemas?
- ¿Qué es un algoritmo de hashing seguro?
- ¿De dónde obtienen los algoritmos comerciales sus datos sin procesar?
- ¿Puede crear un puntero 2D dinámico que almacene elementos ingresados por el usuario como una matriz y lo muestre antes y después de liberarlo?
El documento define DMRC como la clase de tareas de MR deterministas eficientes, y lo hace al restringir cada nodo a un tamaño de entrada que es ‘sustancialmente sublineal’ al tamaño de la entrada total (capturando la idea de que MR funciona en entradas enormes) y de manera similar restringir el número de máquinas (para evitar la paralelización trivial en n-vías) y el número de rondas de MR (para evitar hacer un paso por ronda de MR).
[matemática] DMRC \ subconjunto P [/ matemática], pero actualmente no sabemos (aunque es muy sospechoso) si [matemática] P \ subconjunto DMRC [/ matemática]
Con respecto a la clase [matemáticas] NC [/ matemáticas] de problemas computables de manera eficiente en PRAM, los autores muestran que un gran subconjunto de [matemáticas] DMRC [/ matemáticas] está en [matemáticas] NC [/ matemáticas], pero que [matemáticas] DMRC \ not \ subset NC [/ math].
Finalmente, los autores dan un enfoque de bloques de construcción para construir algoritmos eficientes para DMRC. El documento ofrece una serie de aplicaciones para tales bloques de construcción, para problemas como la conectividad st y los momentos de frecuencia informática.
[1] http://research.yahoo.com/pub/2945
[2] http://en.wikipedia.org/wiki/Par…
