Árbol de expansión mínimo distribuido

El problema del árbol de expansión mínima distribuida (MST) implica la construcción de un árbol de expansión mínima mediante un algoritmo distribuido, en una red donde los nodos se comunican mediante el paso de mensajes. Es radicalmente diferente del problema secuencial clásico, aunque el enfoque más básico se asemeja al algoritmo de Borůvka. Una aplicación importante de este problema es encontrar un árbol que pueda usarse para la difusión. En particular, si el costo de que un mensaje pase a través de un borde en un grafo es significativo, un MST puede minimizar el costo total de que un proceso fuente se comunique con todos los demás procesos en la red.

El problema fue sugerido y resuelto por primera vez ${\displaystyle O(V\log V)}$ tiempo en 1983 por Gallager et al., donde ${\displaystyle V}$ es el número de vértices en el gráfico. Posteriormente, se mejoró la solución para ${\displaystyle O(V)}$ y finalmente ${\displaystyle O({\sqrt {V}\log ^{*}V+D)}$ Donde D es la red, o diámetro del gráfico. Un límite inferior en la complejidad del tiempo de la solución ha demostrado ser ${\displaystyle \Omega \left({\frac {\sqrt {V}{\log} V}+D}\right). }$

El gráfico de entrada ${\displaystyle G(V,E)}$ se considera una red, donde los vértices ${\displaystyle V}$ son nodos y bordes de computación independientes ${\displaystyle E}$ son enlaces de comunicación. Los enlaces son ponderados como en el problema clásico.

Al comienzo del algoritmo, los nodos sólo conocen los pesos de los enlaces que están conectados a ellos. (Es posible considerar modelos en los que sepan más, por ejemplo, los enlaces de sus vecinos.)

Como resultado del algoritmo, cada nodo sabe cuáles de sus enlaces pertenecen al árbol de expansión mínimo y cuáles no.

El modelo de paso de mensajes es uno de los modelos más utilizados en computación distribuida. En este modelo, cada proceso se modela como un nodo de un grafo. Cada canal de comunicación entre dos procesos es un borde del grafo.

Dos algoritmos que se utilizan habitualmente para el problema clásico del árbol de expansión mínimo son el algoritmo de Prim y el algoritmo de Kruskal. Sin embargo, resulta difícil aplicar estos dos algoritmos en el modelo de paso de mensajes distribuido. Los principales desafíos son:

• Tanto el algoritmo de Prim como el algoritmo de Kruskal requieren procesar un nodo o un vértice a la vez, lo que dificulta hacer que funcionen en paralelo. Por ejemplo, el algoritmo de Kruskal procesa los bordes a su vez, decidiendo si incluir el borde en el MST basado en si formaría un ciclo con todos los bordes previamente elegidos.
• Tanto el algoritmo de Prim como el algoritmo de Kruskal requieren procesos para conocer el estado de todo el gráfico, que es muy difícil de descubrir en el modelo de paso de mensajes.

Debido a estas dificultades, se necesitaban nuevas técnicas para algoritmos MST distribuidos en el modelo de paso de mensajes. Algunas tienen similitudes con el algoritmo de Borůvka para el problema MST clásico.

El algoritmo GHS de Gallager, Humblet y Spira es uno de los algoritmos más conocidos en la teoría de la computación distribuida. Este algoritmo construye un MST en el modelo de paso de mensajes asíncrono.

El algoritmo GHS requiere varias suposiciones.

• El gráfico de entrada está conectado y no dirigido.
• Cada borde del gráfico de entrada tiene diferentes pesos finitos. Esta suposición no es necesaria si hay un método consistente para romper los lazos entre los pesos del borde.
• Cada nodo conoce inicialmente el peso de cada incidente de borde a ese nodo.
• Inicialmente, cada nodo está en un estado inactivo. Cada nodo despierta espontáneamente o se despierta mediante la recepción de cualquier mensaje de otro nodo.
• Los mensajes se pueden transmitir independientemente en ambas direcciones en un borde y llegar después de un retraso impredecible pero finito, sin error.
• Cada borde entrega mensajes en orden FIFO.

Definir un fragmento de un MST ${\displaystyle T}$ ser un sub-árbol ${\displaystyle T}$. Es decir, un fragmento es un conjunto conectado de nodos y bordes de ${\displaystyle T}$. Los MST tienen dos propiedades importantes en relación con los fragmentos:

1. Dado un fragmento de un MST ${\displaystyle T}$, vamos ${\displaystyle e}$ ser un borde de salida de peso mínimo del fragmento. Entonces únete ${\displaystyle e}$ y su nodo adyacente al fragmento produce otro fragmento de un MST.
2. Si todos los bordes de un gráfico conectado tienen diferentes pesos, entonces el MST del gráfico es único.

Estas dos propiedades forman la base para demostrar la exactitud del algoritmo GHS. En general, el algoritmo GHS es un algoritmo ascendente en el sentido de que comienza permitiendo que cada nodo individual sea un fragmento y luego une fragmentos hasta que queda un solo fragmento. Las propiedades anteriores implican que el fragmento restante debe ser un MST.

El algoritmo GHS asigna un nivel a cada fragmento, que es un número entero no decreciente con valor inicial 0. Además, cada fragmento con un nivel distinto de cero tiene un ID, que es el ID de la arista central del fragmento, que se selecciona cuando se construye el fragmento. Durante la ejecución del algoritmo, cada nodo puede clasificar cada una de sus aristas incidentes en tres categorías:

• Subdivisión Los bordes son los que se han determinado ser parte del MST.
• Rechazado Los bordes son los que se han determinado no ser parte del MST.
• Básica Los bordes son todos los bordes que no son bordes de rama ni bordes rechazados.

En los fragmentos de nivel 0, cada nodo despertado hará lo siguiente:

1. Elija su borde de incidencia mínimo y marque ese borde como borde de rama.
2. Enviar un mensaje a través del borde de la rama para notificar al nodo en el otro lado.
3. Espera un mensaje del otro extremo del borde.

El borde elegido por los dos nodos que conecta se convierte en el borde central y se le asigna el nivel 1.

En fragmentos de nivel distinto de cero, se ejecuta un algoritmo independiente en cada nivel. Este algoritmo se puede dividir en tres etapas: difusión, convergencia y cambio de núcleo.

Los dos nodos adyacentes al núcleo transmiten mensajes al resto de los nodos del fragmento. Los mensajes se envían a través del borde de la rama, pero no a través del núcleo. Cada mensaje de difusión contiene el ID y el nivel del fragmento. Al final de esta etapa, cada nodo ha recibido el nuevo ID y nivel del fragmento.

En esta etapa, todos los nodos del fragmento cooperan para encontrar el límite mínimo de peso saliente del fragmento. Los bordes salientes son bordes que se conectan a otros fragmentos. Los mensajes enviados en esta etapa están en la dirección opuesta de la etapa de emisión. Iniciado por todas las hojas (los nodos que tienen sólo un borde de rama), se envía un mensaje a través del borde de rama. El mensaje contiene el peso mínimo del borde saliente del incidente que encontró (o el infinito si no se encontró tal borde). La manera de encontrar el límite mínimo saliente será discutida más adelante. Para cada nodo de hoja, dado el número de sus bordes de rama como ${\displaystyle n}$, después de recibir ${\displaystyle n-1}$ mensajes convergentes, se recogerá el peso mínimo de los mensajes y se comparará con los pesos de sus bordes salientes de incidentes. El peso más pequeño será enviado hacia la rama de la que recibió la emisión.

Después de completar la etapa anterior, los dos nodos conectados por el núcleo pueden informarse entre sí de los mejores bordes que recibieron. Luego pueden identificar el borde saliente mínimo de todo el fragmento. Se enviará un mensaje desde el núcleo al borde saliente mínimo a través de una ruta de bordes de ramificación. Finalmente, se enviará un mensaje a través del borde saliente elegido para solicitar la combinación de los dos fragmentos que el borde conecta. Dependiendo de los niveles de esos dos fragmentos, se realiza una de dos operaciones combinadas para formar un nuevo fragmento; los detalles se analizan a continuación.

Como se mencionó anteriormente, cada nodo necesita encontrar su peso mínimo que sale del borde del incidente después de la recepción de un mensaje de transmisión desde el núcleo. Si no ${\displaystyle n}$ recibe una emisión, elegirá su límite mínimo de peso básico y enviará un mensaje al nodo ${\displaystyle n'}$ en el otro lado con la identificación y nivel de su fragmento. Entonces, nodo ${\displaystyle n'}$ decidirá si el borde es un borde saliente y enviar un mensaje para notificar el nodo ${\displaystyle n}$ del resultado. La decisión se toma de acuerdo con lo siguiente:

1. ${\fnMitit {\fnMitit {\fnh} {\fnh} {\fnh} {\fnh} {\fn\fnh}} {\fn\fnh}} {\fn\fn\fn\fnh}} {\fn\fn\fn\fnHFF}} {\fn\fn\fnHFF}}}}}}}}}}}} {\\\\\\fnh}}}}}}}}}\\\\\\\\\fnH00}}}}}}}}}}}}}}}\\\\\\\\\\\\\\\\\\\\\fnhnh}}}}}}}}\\\\\\\\\\\\\\\\fnhnHhnhnhnhnhnhnhnhnhnhnhnHFF}\fnhnhnhnhnhnh$. Es decir, nodos ${\displaystyle n}$ y ${\displaystyle n'}$ pertenecen al mismo fragmento, por lo que el borde no está saliendo.
2. ${\fnMitit {\fnMitit {\fnh} {\fnh} {\fnh} {\fnh}_ {\fnh} {\fn\fnh}} {\fn\fn\fn\fn\fnh}}$ y ${\displaystyle {\Mathit {Level}(n)\leq {\matit {Level}(n')}$. Es decir, nodos ${\displaystyle n}$ y ${\displaystyle n'}$ pertenecen a los diferentes fragmentos, por lo que el borde está saliendo.
3. ${\fnMitit {\fnMitit {\fnh} {\fnh} {\fnh} {\fnh}_ {\fnh} {\fn\fnh}} {\fn\fn\fn\fn\fnh}}$ y ${\displaystyle {\Mathit {Level}(n)} {\Mathit {Level}(n')}$. No podemos hacer ninguna conclusión. La razón es que los dos nodos pueden pertenecer al mismo fragmento ya, pero nodo ${\displaystyle n'}$ no ha descubierto este hecho todavía debido a la demora de un mensaje de transmisión. En este caso, el algoritmo permite nodo ${\displaystyle n'}$ posponer la respuesta hasta que su nivel sea superior o igual al nivel que recibió del nodo ${\displaystyle n}$.

Vamos. ${\displaystyle F}$ y ${\displaystyle F.$ sean los dos fragmentos que necesitan ser combinados. Hay dos maneras de hacer esto:

• Merge: Esta operación ocurre si ambos ${\displaystyle F}$ y ${\displaystyle F.$ compartir un peso mínimo común borde saliente, y ${\displaystyle {\mathit {Level}(F)={\mathit {Level}(F')}$. El nivel del fragmento combinado será ${\displaystyle {\Mathit {Level}(F)+1}$.
• Absorb: Esta operación ocurre si ${\displaystyle {\Mathit {Level} {\fnMitit {\fnMitit}}(F')}$. El fragmento combinado tendrá el mismo nivel que el ${\displaystyle F.$.

Además, cuando se produce una operación "Absorb", ${\displaystyle F}$ debe estar en la etapa de cambiar el núcleo, mientras ${\displaystyle F.$ puede estar en una etapa arbitraria. Por lo tanto, las operaciones "Absorb" pueden realizarse de manera diferente dependiendo del estado de ${\displaystyle F.$. Vamos. ${\displaystyle e}$ ser el borde que ${\displaystyle F}$ y ${\displaystyle F.$ querer combinar con, y dejar ${\displaystyle n}$ y ${\displaystyle n'}$ los dos nodos conectados ${\displaystyle e}$ dentro ${\displaystyle F}$ y ${\displaystyle F.$, respectivamente. Hay dos casos a considerar:

1. Node ${\displaystyle n'}$ ha recibido mensaje de transmisión pero no ha enviado un mensaje convergente de vuelta al núcleo. En este caso, fragmento ${\displaystyle F}$ puede simplemente unirse al proceso de emisión ${\displaystyle F.$. Específicamente, imagen ${\displaystyle F}$ y ${\displaystyle F.$ ya se han combinado para formar un nuevo fragmento ${\displaystyle F'}$, así que queremos encontrar el límite mínimo de peso saliente ${\displaystyle F'}$. Para hacer eso, nodo ${\displaystyle n'}$ puede iniciar una transmisión ${\displaystyle F}$ para actualizar el fragmento de identificación de cada nodo en ${\displaystyle F}$ y recoger el peso mínimo saliente en ${\displaystyle F}$.
2. Node ${\displaystyle n'}$ ya ha enviado un mensaje convergente de vuelta al núcleo. Antes del nodo ${\displaystyle n'}$ envió un mensaje convergente, debe haber elegido un peso mínimo de salida. Como hemos discutido anteriormente, ${\displaystyle n'}$ lo hace eligiendo su límite mínimo de peso básico, enviando un mensaje de prueba al otro lado del borde elegido, y esperando la respuesta. Suppose ${\displaystyle e'}$ es el borde elegido, podemos concluir lo siguiente:
   1. ${\displaystyle e'\neq e}$
   2. ${\fnMitit {\fnMitit {\fnMitit} {\fnMitit}(e)}$

   La segunda declaración sigue si la primera sostiene. Para la primera declaración, supongamos ${\displaystyle n'}$ eligió el borde ${\displaystyle e}$ y envió un mensaje de prueba ${\displaystyle n}$ via borde ${\displaystyle e}$. Entonces, nodo ${\displaystyle n}$ retrasará la respuesta (según el caso 3 de "Encontrar el límite de salida de peso mínimo"). Entonces, es imposible que ${\displaystyle n'}$ ya ha enviado su mensaje convergente. En las conclusiones 1 y 2, podemos concluir que es seguro absorber ${\displaystyle F}$ en ${\displaystyle F.$ desde entonces ${\displaystyle e'}$ sigue siendo el límite mínimo de salida para informar después ${\displaystyle F}$ es absorbido.

Como se mencionó anteriormente, los fragmentos se combinan ya sea mediante operación "Merge" o "Absorb". La operación "Absorb" no cambia el nivel máximo entre todos los fragmentos. La operación "Merge" puede aumentar el nivel máximo en 1. En el peor de los casos, todos los fragmentos se combinan con operaciones "Merge", por lo que el número de fragmentos disminuye en la mitad de cada nivel. Por lo tanto, el número máximo de niveles es ${\displaystyle O(\log V)}$, donde ${\displaystyle V}$ es el número de nodos.

El algoritmo GHS tiene una propiedad muy interesante: los fragmentos de nivel más bajo no se bloquearán, aunque algunas operaciones en fragmentos de nivel inferior pueden estar bloqueadas. Esta propiedad implica que el algoritmo terminará eventualmente con un árbol de expansión mínimo.

An ${\displaystyle O(\log n)}$- algoritmo de aproximación fue desarrollado por Maleq Khan y Gopal Pandurangan. Este algoritmo funciona ${\displaystyle O(D+L\log n)}$ tiempo, donde ${\displaystyle L.$ es el diámetro del camino más corto local del gráfico.