Hispanopedia Wiki
Articulo de referencia

Árbol de expansión mínima distribuido

Ejemplo de un MST: El árbol de expansión mínima de un grafo planar . Cada arista está etiquetada con su peso, que en este caso es aproximadamente proporcional a su longitud. El ...

Hispanopedia WikiContenido en espanolLectura gratuita
Ejemplo de un MST: El árbol de expansión mínima de un grafo planar . Cada arista está etiquetada con su peso, que en este caso es aproximadamente proporcional a su longitud.

El problema del árbol de expansión mínima distribuido (MST) consiste en 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 utilizarse para la difusión de mensajes . En particular, si el coste de que un mensaje atraviese una arista en un grafo es significativo, un MST puede minimizar el coste total de comunicación de un proceso fuente con todos los demás procesos de la red.

El problema fue sugerido y resuelto por primera vez enO(Vregistro⁡V){\displaystyle O(V\log V)}tiempo en 1983 por Gallager et al. , [ 1 ] dondeV{\displaystyle V}es el número de vértices en el grafo . Posteriormente, la solución se mejoró aO(V){\displaystyle O(V)}[ 2 ] y finalmente [ 3 ] [ 4 ]O(Vregistro∗⁡V+D){\displaystyle O({\sqrt {V}}\log ^{*}V+D)}donde D es el diámetro de la red o del grafo. Finalmente se ha demostrado que un límite inferior para la complejidad temporal de la solución es [ 5 ].Ω(Vregistro⁡V+D).{\displaystyle \Omega \left({{\frac {\sqrt {V}}{\log V}}+D}\right).}

Descripción general

El gráfico de entradaGRAMO(V,mi){\displaystyle G(V,E)}se considera una red, donde los vérticesV{\displaystyle V}son nodos y bordes de computación independientesmi{\displaystyle E}son enlaces de comunicación. Los enlaces tienen ponderación como en el problema clásico.

Al inicio del algoritmo, los nodos solo conocen los pesos de los enlaces que están conectados a ellos. (Es posible considerar modelos en los que conozcan más información, 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ínima y cuáles no.

MST en el modelo de paso de mensajes

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

Dos algoritmos comúnmente utilizados para el problema clásico del árbol de expansión mínima 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 de Kruskal requieren procesar un nodo o vértice a la vez, lo que dificulta su ejecución en paralelo. Por ejemplo, el algoritmo de Kruskal procesa las aristas una por una, decidiendo si incluirlas en el árbol de expansión mínima (MST) en función de si formarían un ciclo con todas las aristas seleccionadas previamente.
  • Tanto el algoritmo de Prim como el de Kruskal requieren que los procesos conozcan el estado de todo el grafo, lo cual es muy difícil de descubrir en el modelo de paso de mensajes.

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

Algoritmo GHS

El algoritmo GHS [ 1 ] 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.

Supuestos

El algoritmo GHS requiere varias suposiciones.

  • El grafo de entrada es conexo y no dirigido.
  • Cada arista del grafo de entrada tiene pesos finitos distintos. Esta suposición no es necesaria si existe un método consistente para resolver los empates entre los pesos de las aristas.
  • Inicialmente, cada nodo conoce el peso de cada arista incidente a ese nodo.
  • Inicialmente, cada nodo se encuentra en estado inactivo. Cada nodo se activa espontáneamente o al recibir un mensaje de otro nodo.
  • Los mensajes pueden transmitirse de forma independiente en ambas direcciones a través de un borde y llegar tras un retraso impredecible pero finito, sin errores.
  • Cada arista entrega los mensajes en orden FIFO ( primero en entrar, primero en salir).

Propiedades de los MST

Defina un fragmento de un MSTT{\displaystyle T}ser un subárbol deT{\displaystyle T}. Es decir, un fragmento es un conjunto conectado de nodos y aristas deT{\displaystyle T}. Los MST tienen dos propiedades importantes en relación con los fragmentos: [ 1 ]

  1. Dado un fragmento de un MSTT{\displaystyle T}, dejarmi{\displaystyle e}ser un borde saliente de peso mínimo del fragmento. Luego unirmi{\displaystyle e}y su nodo adyacente no fragmentario al fragmento produce otro fragmento de un MST.
  2. Si todas las aristas de un grafo conexo tienen pesos diferentes, entonces el árbol de expansión mínima (MST) del grafo es único.

Estas dos propiedades constituyen la base para demostrar la corrección del algoritmo GHS. En general, el algoritmo GHS es un algoritmo ascendente, ya que comienza considerando cada nodo individual como un fragmento y luego une los fragmentos hasta que queda uno solo. Las propiedades mencionadas implican que el fragmento restante debe ser un árbol de expansión mínima (MST).

Descripción del algoritmo

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

  • Los bordes de las ramas son aquellos que se han determinado que forman parte del MST.
  • Las aristas rechazadas son aquellas que se ha determinado que no forman parte del MST.
  • Las aristas básicas son todas aquellas que no son ni aristas de ramificación ni aristas rechazadas.

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

  1. Seleccione su borde incidente de peso mínimo y márquelo como borde de ramificación.
  2. Envía un mensaje a través del borde de la rama para notificar al nodo del otro lado.
  3. Espere un mensaje del otro extremo de la red.

La arista elegida por los dos nodos que conecta se convierte en la arista central y se le asigna el nivel 1.

En los 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.

Transmisión

Los dos nodos adyacentes al núcleo envían mensajes de difusión al resto de los nodos del fragmento. Los mensajes se envían a través 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 finalizar esta etapa, cada nodo ha recibido el nuevo ID y nivel del fragmento.

Convergecast

En esta etapa, todos los nodos del fragmento cooperan para encontrar la arista saliente de peso mínimo del fragmento. Las aristas salientes son aristas que conectan con otros fragmentos. Los mensajes enviados en esta etapa van en la dirección opuesta a la etapa de difusión. Inicializado por todas las hojas (los nodos que tienen solo una arista de rama), se envía un mensaje a través de la arista de rama. El mensaje contiene el peso mínimo de la arista saliente incidente que encontró (o infinito si no se encontró ninguna arista). La forma de encontrar la arista saliente mínima se discutirá más adelante. Para cada nodo que no sea una hoja, dado el número de sus aristas de rama comonorte{\displaystyle n}, después de recibirnorte−1{\displaystyle n-1}Al procesar los mensajes convergecast, se selecciona el peso mínimo entre los mensajes y se compara con los pesos de sus aristas salientes incidentes. El peso más pequeño se envía hacia la rama desde la que se recibió la difusión.

Cambiar el núcleo

Tras completar la etapa anterior, los dos nodos conectados por el núcleo pueden informarse mutuamente sobre las mejores aristas recibidas. A continuación, identifican la arista saliente mínima de todo el fragmento. El núcleo envía un mensaje a dicha arista a través de una ruta de ramificaciones. Finalmente, se envía un mensaje a través de la arista saliente seleccionada para solicitar la combinación de los dos fragmentos que conecta. Según el nivel de estos fragmentos, se realiza una de dos operaciones de combinación para formar un nuevo fragmento; los detalles se explican más adelante.

Encontrar el borde de salida del incidente de peso mínimo

Como se mencionó anteriormente, cada nodo necesita encontrar su borde de incidente saliente de peso mínimo después de recibir un mensaje de difusión del núcleo. Si el nodonorte{\displaystyle n}Cuando recibe una transmisión, seleccionará su arista básica de peso mínimo y enviará un mensaje al nodo.norte′{\displaystyle n'}en el otro lado con su ID y nivel de fragmento. Luego, nodonorte′{\displaystyle n'}decidirá si el borde es un borde saliente y enviará un mensaje de vuelta para notificar al nodo.norte{\displaystyle n}del resultado. La decisión se toma de acuerdo con lo siguiente:

  1. FragramometrominortetID(norte)=FragramometrominortetID(norte′){\displaystyle {\mathit {Fragmento}}_{\mathit {ID}}(n)={\mathit {Fragmento}}_{\mathit {ID}}(n')}. Es decir, nodosnorte{\displaystyle n}ynorte′{\displaystyle n'}pertenecen al mismo fragmento, por lo que la arista no es saliente.
  2. FragramometrominortetID(norte)≠FragramometrominortetID(norte′){\displaystyle {\mathit {Fragmento}}_{\mathit {ID}}(n)\neq {\mathit {Fragmento}}_{\mathit {ID}}(n')}yLmivmil(norte)≤Lmivmil(norte′){\displaystyle {\mathit {Nivel}}(n)\leq {\mathit {Nivel}}(n')}. Es decir, nodosnorte{\displaystyle n}ynorte′{\displaystyle n'}pertenecen a los diferentes fragmentos, por lo que el borde es saliente.
  3. FragramometrominortetID(norte)≠FragramometrominortetID(norte′){\displaystyle {\mathit {Fragmento}}_{\mathit {ID}}(n)\neq {\mathit {Fragmento}}_{\mathit {ID}}(n')}yLmivmil(norte)>Lmivmil(norte′){\displaystyle {\mathit {Level}}(n)>{\mathit {Level}}(n')}No podemos llegar a ninguna conclusión. La razón es que los dos nodos pueden pertenecer al mismo fragmento, pero el nodonorte′{\displaystyle n'}aún no ha descubierto este hecho debido al retraso de un mensaje de difusión. En este caso, el algoritmo permite que el nodonorte′{\displaystyle n'}posponer la respuesta hasta que su nivel sea mayor o igual al nivel que recibió del nodonorte{\displaystyle n}.

Combinando dos fragmentos

DejarF{\displaystyle F}yF′{\displaystyle F'}sean los dos fragmentos que necesitan combinarse. Hay dos maneras de hacerlo: [ 1 ] [ 6 ]

  • Fusionar : Esta operación ocurre si ambosF{\displaystyle F}yF′{\displaystyle F'}comparten un borde de salida de peso mínimo común yLmivmil(F)=Lmivmil(F′){\displaystyle {\mathit {Nivel}}(F)={\mathit {Nivel}}(F')}. El nivel del fragmento combinado seráLmivmil(F)+1{\displaystyle {\mathit {Nivel}}(F)+1}.
  • Absorber : Esta operación ocurre siLmivmil(F)<Lmivmil(F′){\displaystyle {\mathit {Nivel}}(F)<{\mathit {Nivel}}(F')}. El fragmento combinado tendrá el mismo nivel queF′{\displaystyle F'}.

Además, cuando se produce una operación de "Absorber",F{\displaystyle F}debe estar en la etapa de cambio del núcleo, mientras queF′{\displaystyle F'}puede estar en una etapa arbitraria. Por lo tanto, las operaciones de "Absorber" pueden realizarse de manera diferente según el estado deF′{\displaystyle F'}. Dejarmi{\displaystyle e}ser el borde queF{\displaystyle F}yF′{\displaystyle F'}quieren combinarse con, y dejarnorte{\displaystyle n}ynorte′{\displaystyle n'}sean los dos nodos conectados pormi{\displaystyle e}enF{\displaystyle F}yF′{\displaystyle F'}, respectivamente. Hay dos casos a considerar:

  1. Nodonorte′{\displaystyle n'}ha recibido un mensaje de difusión pero no ha enviado un mensaje convergecast de vuelta al núcleo. En este caso, el fragmentoF{\displaystyle F}puede simplemente unirse al proceso de transmisión deF′{\displaystyle F'}. Específicamente, nosotros tomamos imágenesF{\displaystyle F}yF′{\displaystyle F'}ya se han combinado para formar un nuevo fragmentoF″{\displaystyle F''}, por lo que queremos encontrar el borde saliente de peso mínimo deF″{\displaystyle F''}. Para ello, nodonorte′{\displaystyle n'}puede iniciar una transmisión aF{\displaystyle F}para actualizar el ID de fragmento de cada nodo enF{\displaystyle F}y recolectar el borde saliente de peso mínimo enF{\displaystyle F}.
  2. Nodonorte′{\displaystyle n'}ya ha enviado un mensaje convergecast de vuelta al núcleo. Antes del nodonorte′{\displaystyle n'}Si se envió un mensaje convergecast, debe haber seleccionado un borde saliente de peso mínimo. Como comentamos anteriormente,norte′{\displaystyle n'}lo hace eligiendo su arista básica de peso mínimo, enviando un mensaje de prueba al otro lado de la arista elegida y esperando la respuesta. Supongamos quemi′{\displaystyle e'}Si el borde elegido es el correcto, podemos concluir lo siguiente:
    1. mi′≠mi{\displaystyle e'\neq e}
    2. wmiigramoht(mi′)<wmiigramoht(mi){\displaystyle {\mathit {weight}}(e')<{\mathit {weight}}(e)}
    La segunda afirmación se deduce si la primera es cierta. Para la primera afirmación, supongamos que...norte′{\displaystyle n'}eligió el bordemi{\displaystyle e}y envió un mensaje de prueba anorte{\displaystyle n}a través del bordemi{\displaystyle e}. Luego, nodonorte{\displaystyle n}retrasará la respuesta (según el caso 3 de "Encontrar el borde saliente de incidente de peso mínimo"). Entonces, es imposible quenorte′{\displaystyle n'}ya ha enviado su mensaje convergecast. Por las conclusiones 1 y 2 mencionadas anteriormente, podemos concluir que es seguro absorberlo.F{\displaystyle F}enF′{\displaystyle F'}desdemi′{\displaystyle e'}sigue siendo el borde saliente mínimo a informar despuésF{\displaystyle F}es absorbido.

Número máximo de niveles

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

Propiedad Progress

El algoritmo GHS posee la ventaja de que los fragmentos de nivel más bajo no se bloquean, aunque algunas operaciones en los fragmentos de niveles superiores sí pueden bloquearse. Esta propiedad implica que el algoritmo finalizará con un árbol de expansión mínimo.

Algoritmos de aproximación

UnO(registro⁡norte){\displaystyle O(\log n)}El algoritmo de aproximación fue desarrollado por Maleq Khan y Gopal Pandurangan. [ 7 ] Este algoritmo se ejecuta enO(D+Lregistro⁡norte){\displaystyle O(D+L\log n)}tiempo, dondeL{\displaystyle L}es el diámetro del camino más corto local [ 7 ] del grafo.

Referencias

  1. 1 2 3 4 5 Robert G. Gallager , Pierre A. Humblet y PM Spira, "Un algoritmo distribuido para árboles de expansión de peso mínimo", ACM Transactions on Programming Languages ​​and Systems , vol. 5, n.º 1, págs. 66–77, enero de 1983.
  2. ↑ Baruch Awerbuch . “Algoritmos distribuidos óptimos para el árbol de expansión de peso mínimo, conteo, elección de líder y problemas relacionados”, Actas del 19º Simposio ACM sobre Teoría de la Computación (STOC) , Ciudad de Nueva York, Nueva York, mayo de 1987.
  3. ↑ Juan Garay, Shay Kutten y David Peleg , “Un algoritmo distribuido de tiempo sublineal para árboles de expansión de peso mínimo (resumen extendido)”, Actas del Simposio IEEE sobre Fundamentos de la Informática (FOCS), 1993.
  4. ↑ Shay Kutten y David Peleg , “Fast Distributed Construction of Smallk-Dominating Sets and Applications”, Journal of Algorithms , Volumen 28, Número 1, julio de 1998, Páginas 40-66.
  5. ↑ David Peleg y Vitaly Rubinovich “Una cota inferior casi ajustada sobre la complejidad temporal de la construcción de árboles de expansión mínima distribuidos”, SIAM Journal on Computing , 2000, y IEEE Symposium on Foundations of Computer Science (FOCS) , 1999.
  6. 1 2 Nancy A. Lynch. Algoritmos distribuidos. Morgan Kaufmann, 1996.
  7. 1 2 Maleq Khan y Gopal Pandurangan. "Un algoritmo de aproximación distribuida rápida para árboles de expansión mínima,"" Distributed Computing , vol. 20, no. 6, pp. 391–402, abril de 2008.
Lecturas relacionadas
6 articulos
Gráfico planarGráfico planarEn teoría de grafos , un grafo plano es un grafo que se puede incrustar en el plano , es decir, se puede dibujar en el plano de tal manera que sus ...árbol de expansión mínimaárbol de expansión mínimaEn teoría de grafos , un árbol de expansión mínima ( MST ) o árbol de expansión de peso mínimo es un subconjunto de las aristas de un grafo no diri...{\estilo de visualización v}Algoritmo distribuidoUn algoritmo distribuido es un algoritmo diseñado para ejecutarse en hardware de computadora construido a partir de procesadores interconectados . ...El algoritmo de BorůvkaEl algoritmo de BorůvkaEl algoritmo de Borůvka es un algoritmo voraz para encontrar un árbol de expansión mínima en un grafo, o un bosque de expansión mínima en el caso d...Radiodifusión (redes)Radiodifusión (redes)En redes informáticas , telecomunicaciones y teoría de la información , la difusión es un método de transmisión de un mensaje a todos los destinata...Teoría de grafosTeoría de grafosEn matemáticas , la teoría de grafos es el estudio de los grafos , que son estructuras matemáticas utilizadas para modelar relaciones por pares ent...