¿Por qué no hemos podido desarrollar una teoría de complejidad unificada de la computación distribuida?

El campo de la computación distribuida se ha quedado lamentablemente corto en el desarrollo de una sola teoría matemática para describir algoritmos distribuidos. Existen varios 'modelos' y marcos de cómputo distribuido que simplemente no son compatibles entre sí. La gran explosión de propiedades temporales variables (asincronía, sincronía, sincronía parcial), varias primitivas de comunicación (transmisión de mensajes vs. memoria compartida, difusión vs. unidifusión), modelos de fallas múltiples (detención de fallas, recuperación de fallas, omisión de envío, bizantino, etc.) on) nos ha dejado con una cantidad intratable de modelos de sistemas, marcos y metodologías, que comparar los resultados de solvencia relativa y los límites inferiores entre estos modelos y marcos se ha vuelto arduo, intratable y, a veces, imposible.

Mi pregunta es muy simple, ¿por qué es así? ¿Qué es tan fundamentalmente diferente sobre la computación distribuida (de su contraparte secuencial) que no hemos podido cotejar la investigación en una teoría unificada de la computación distribuida? Con la computación secuencial, las máquinas de Turing, las funciones recursivas y el cálculo de Lambda se han convertido en equivalentes. ¿Fue solo un golpe de suerte o realmente hicimos un buen trabajo encapsulando la computación secuencial de una manera que aún no se ha logrado con la computación distribuida?

En otras palabras, ¿la informática distribuida es inherentemente inflexible a una teoría elegante (y si es así, ¿cómo y por qué?), O simplemente no somos lo suficientemente inteligentes como para descubrir tal teoría?

La única referencia que pude encontrar que aborda este problema es: " Evaluación de dos décadas de investigación de la teoría de la computación distribuida " por Fischer y Merritt DOI: 10.1007 / s00446-003-0096-6

Cualquier referencia o exposición sería realmente útil.

Mi opinión es que el modelo de computación de la máquina de Turing, motivado de manera abstracta, era una buena aproximación de la tecnología hasta hace muy poco, mientras que los modelos de computación distribuida, desde el primer momento, han sido motivados por el mundo real, que siempre es más complicado que las abstracciones.

Desde, por ejemplo, 1940-1995, el tamaño de las instancias problemáticas, la relativa "falta de importancia" del paralelismo y la concurrencia, y la macroescala de los dispositivos informáticos, todos "conspiraron" para mantener a las máquinas de Turing en una excelente aproximación de las computadoras del mundo real. Sin embargo, una vez que comience a tratar con conjuntos de datos masivos, la necesidad ubicua de concurrencia, biología a través de la lente algorítmica, etc., queda mucho menos claro si existe un modelo de cómputo "intuitivo". Quizás los problemas difíciles en un modelo no son difíciles, estrictamente menos computacionalmente complejos, en otro. Así que creo que la complejidad computacional convencional finalmente se está poniendo al día (!) Con la computación distribuida, al comenzar a considerar múltiples modelos de estructuras de cómputo y datos, motivados por consideraciones del mundo real.

Contestaré esto desde la perspectiva de los problemas gráficos clásicos (o problemas de entrada / salida): tenemos una red, cada nodo obtiene algo como entrada y cada nodo debe producir algo como salida. Supongo que esto está más cerca del mundo de la complejidad computacional tradicional.

Ciertamente yo soy parcial, pero creo que en este ajuste, no es un simple y modelo bastante usual de computación distribuida: algoritmos distribuidos síncronos , con la definición que el tiempo = número de rondas sincrónicos funcionando . En la terminología de Peleg, este es el modelo LOCAL .

Este modelo es agradable ya que tiene muy pocas "partes móviles", no tiene parámetros, etc. Sin embargo, es muy concreto: tiene sentido decir que el tiempo de ejecución de un algoritmo es exactamente 15 en este modelo. Y puede probar límites inferiores incondicionales, teóricos de la información: desde esta perspectiva, la complejidad distribuida de muchos problemas gráficos (por ejemplo, la coloración de gráficos) se entiende bastante bien.

Este modelo también proporciona un enfoque unificado para muchos aspectos de la informática distribuida:

• Transmisión de mensajes vs. memoria compartida, difusión vs. unidifusión: irrelevante en este modelo.
• ¿Tu sistema del mundo real es asíncrono? No hay problema, solo conecte el -synchroniser. La complejidad del tiempo (con definiciones adecuadas) esencialmente no se ve afectada.$\alpha$
• ¿Desea tener un algoritmo para redes dinámicas, o desea recuperarse de fallas? Bueno, si su algoritmo síncrono es determinista, puede usarlo para construir un algoritmo autoestabilizador . Nuevamente, la complejidad del tiempo no se ve esencialmente afectada.

Ahora todo esto está bien siempre que estudie problemas que están "verdaderamente distribuidos" en el sentido de que el tiempo de ejecución de su algoritmo es menor que el diámetro del gráfico , es decir, ningún nodo necesita tener información completa sobre la estructura del grafico. Sin embargo, también hay muchos problemas que son inherentemente globales: el algoritmo más rápido en este modelo tiene un tiempo de ejecución lineal en el diámetro del gráfico. En el estudio de esos problemas, el modelo anterior ya no tiene ningún sentido, y luego tenemos que recurrir a otra cosa. Típicamente, uno comienza a prestar atención a la cantidad total de mensajes o bits comunicados en la red. Esa es una razón por la que obtenemos varios modelos diferentes.

Entonces, por supuesto, tenemos el problema de que la comunidad informática distribuida es en realidad dos comunidades diferentes, con sorprendentemente pocas cosas en común . Si agrupa todos los modelos de dos comunidades, sin duda parecerá un poco confuso ... Mi respuesta anterior está relacionada con solo la mitad de la comunidad; Confío en que otros completarán con respecto a la otra mitad.

Una idea romántica para capturar varios modelos de computación distribuida ha sido a través de la topología algebraica. La idea central es construir complejos simpliciales dejando que los puntos sean estados de proceso, cada uno etiquetado con una identificación de proceso. Este es un manual sobre el tema. La respuesta más cercana a su pregunta probablemente ha sido mencionada por Eli gafni en su artículo, Computación distribuida, Un atisbo de una teoría. En su artículo, muestra simulaciones de cómo comenzar con memoria compartida asíncrona para dos o tres procesadores (para fallo de parada y bizantino); muestra cómo puede aplicar esto al modelo de paso de mensajes. Es crucial para entender sus simulaciones la noción de ver una computación distribuida topológicamente

Creo que la situación se ve bastante diferente si se ve en contexto: a partir de los primeros trabajos y los resultados de imposibilidad en el acuerdo bizantino ( PSL80 LSP82 FLP85), pronto quedó claro que los problemas fundamentales en la informática distribuida solo pueden resolverse con supuestos de sincronía estrictos y un alto grado de redundancia. Como estos límites teóricos incondicionales de los recursos se consideraron inviables para cualquier propósito práctico, la investigación se centró en el desarrollo de modelos más refinados que permitieran compensaciones cada vez más precisas de los supuestos (en garantías de temporización o modos de falla, por ejemplo) versus garantías (es decir, número de fallas simultáneas de qué tipo sobre qué tipo de componentes tolerado, por ejemplo, procesadores, enlaces) para dar a los diseñadores del sistema las herramientas para encontrar la compensación adecuada para el sistema en cuestión.