¿Principales problemas no resueltos en sistemas distribuidos?

Inspirado por esta pregunta , ¿cuáles son los principales problemas y las soluciones existentes que necesitan mejoras en el dominio de sistemas distribuidos (teóricos).

¿Algo como protocolos de membresía, consistencia de datos?

Ver, por ejemplo, Ocho problemas abiertos en computación distribuida .

La complejidad del tiempo distribuido de numerosos problemas gráficos sigue siendo una pregunta abierta.

En general, los algoritmos de gráficos distribuidos son un área en la que esperaríamos tener (al menos asintóticamente) coincidencia de los límites superior e inferior para la complejidad del tiempo distribuido de los problemas de gráficos. Por ejemplo, para muchos problemas de optimización se conocen límites estrechos . Sin embargo, hay muchos problemas clásicos de ruptura de simetría que todavía no se conocen bien.

No sabemos, por ejemplo, cuántas rondas de comunicación se necesitan para encontrar un conjunto independiente máximo , una coincidencia máxima , una coloración de vértice adecuada con colores, o una coloración de bordes adecuada con 2 Δ - 1 colores en un gráfico con un grado máximo de Δ . Todos estos problemas son fáciles de resolver con algoritmos codiciosos centralizados, y existen algoritmos distribuidos eficientes para cada uno de estos problemas, pero no sabemos si alguno de los algoritmos actuales es óptimo.$\Delta+1$$2\Delta-1$$\Delta$

Por ejemplo, para todos estos problemas existen algoritmos deterministas distribuidos para el modelo LOCAL con tiempos de ejecución de , donde n es el número de nodos. Es bien sabido que estos problemas no pueden resolverse en el tiempo O ( Δ ) + o ( log ∗ n ) rondas, pero no se sabe si pueden resolverse en el tiempo o ( Δ ) + O ( log ∗ n $O(\Delta + \log^* n)$$n$$O(\Delta) + o(\log^* n)$$o(\Delta) + O(\log^* n)$rondas En general, no entendemos cómo los tiempos de ejecución dependen del grado máximo ; esto es lo que yo llamo el problema de coordinación local .

El papel de la aleatoriedad es otro problema importante. Por ejemplo, muchos de los problemas mencionados anteriormente se pueden resolver en tiempo de polylog con algoritmos aleatorios (es decir, el tiempo es polylog en para cualquier valor de Δ ), pero no se conocen algoritmos deterministas de tiempo de polylog para, por ejemplo, conjuntos independientes máximos . Estas preguntas, así como muchos otros problemas abiertos, se discuten con más detalle en la Sección 11 del libro reciente de Barenboim y Elkin .$n$$\Delta$

Arriba, me he centrado en preguntas que son específicas de la informática distribuida. También hay preguntas abiertas en algoritmos de gráficos distribuidos que tienen conexiones no triviales para abrir problemas en la informática teórica en general. Por ejemplo, los límites inferiores no constantes para el modelo de camarilla congestionado son una gran pregunta abierta en la computación distribuida; Recientemente se descubrió que tales límites inferiores también implicarían nuevos límites inferiores para ACC.

Problemas abiertos en "Algoritmos distribuidos para árboles de expansión mínima (MST)": (enumerados en [1])

1. En cuanto a la complejidad del tiempo ,

   Cerca del tiempo, los algoritmos óptimos y los límites inferiores aparecen en [2] y las referencias en este documento. La complejidad óptima del tiempo sigue siendo un problema abierto.

2. En cuanto a la complejidad del mensaje ,

   $O(m + n \log n)$

3. Con respecto al modelo síncrono :

   $O(\log \log n)$

$O(\log n)$

[1] Algoritmos distribuidos para árboles de expansión mínima por Sergio Rajsbaum en "Encyclopedia of Algorithms", 2008.

[2] MST distribuido para gráficos de diámetro constante por Lotker et al. Distrib. Comput., 2006.

$O(\log \log n)$

[4] Algoritmo de aproximación distribuido rápido para árboles de expansión mínima por Khan et al. DISCO 2006.

vea también (más recientemente) una presentación de diapositivas "Problemas informáticos no resueltos en computación distribuida" de 2012 por el investigador de Notre Dame Douglas Thain, quien dirige su laboratorio de computación cooperativa. tiene una inclinación más aplicada, pero las preguntas clave enumeradas inevitablemente conducen a áreas teóricas.

• El problema de Kiloscale: cualquier flujo de trabajo con suficiente concurrencia debería poder ejecutarse correctamente en núcleos 1K la primera vez y siempre sin la ayuda de un administrador de sistemas.

• El problema de detención: dado un flujo de trabajo que se ejecuta en mil nodos, haga que se detenga y limpie todos los estados asociados con total seguridad.

• El problema de dependencia:

  (1) Dado un programa, descubra todo lo que realmente necesita para ejecutarse en una máquina diferente.

  (2) Dado un proceso, descubra los recursos (distribuidos) que realmente usa mientras se ejecuta.

  (3) Extienda 1 y 2 a todo un flujo de trabajo.

• El problema del tamaño correcto: Dada una aplicación (estructurada) y un clúster, nube o cuadrícula, elija una asignación de recursos que logre un buen rendimiento a un costo aceptable.

• El problema de solución de problemas: cuando ocurre una falla en el medio de una pila de software de 100 capas, ¿cómo y cuándo informa / reintenta / ignora / suprime el error?

• El problema del diseño: ¿Cómo deberían diseñarse las aplicaciones para que sean adecuadas para la informática distribuida?