Megafusión

Algoritmo distribuido en teoría de grafos

La megafusión es un algoritmo distribuido cuyo objetivo es resolver el problema de elección en gráficos genéricos conectados no dirigidos . ^{[1] [2]}

Introducción

Mega-Merger fue desarrollado por Robert Gray Gallager en el MIT en 1983. Aplica un enfoque distribuido de divide y vencerás combinado con una estrategia de conquista basada en rangos. El algoritmo suele presentarse a través de una analogía de aldea-ciudad. Cada nodo del gráfico indica una aldea, mientras que los bordes que los conectan son las carreteras y un árbol de expansión con raíz en un subgráfico es una ciudad. El gráfico completo es entonces una megaciudad. Mega-Merger empuja a las aldeas a unirse para formar ciudades según el rango y los bordes de cada una. Las ciudades se forman entonces por alianzas o por conquista/absorción.

Prerrequisitos

Mega-Merger construye un árbol de expansión mínimo sobre gráficos conectados siempre que:

• Fiabilidad total: ningún mensaje se pierde durante la transmisión.
• UI (iniciador único): un solo nodo inicia el protocolo.
• Canales de comunicación bidireccionales: Cada borde es bidireccional, las comunicaciones pueden viajar en ambas direcciones.

No son necesarias más restricciones.

Algoritmo

El algoritmo asigna a cada aldea un nombre y un rango, el primero generalmente único. El segundo indica el número de fusiones amistosas por las que ha pasado la ciudad y, cuanto mayor sea, más poderosa se considera la ciudad. Además, a cada arista se le asigna un peso: cada aldea/ciudad tiene una arista de peso mínimo también llamada enlace de fusión , que es la arista cuyo recorrido tiene un costo mínimo. ${\displaystyle C}$ ${\displaystyle e_{merge}(C,C')}$

El algoritmo avanza en etapas consecutivas hasta que se forma una megaciudad. Cada ciudad C calcula su propio enlace de fusión y envía una solicitud de fusión a través de . La solicitud se gestiona de las siguientes maneras: ${\displaystyle e_{merge}(C,C')}$ ${\displaystyle C'}$

1. Fusión amistosa: si las ciudades comparten el mismo vínculo de fusión y tienen el mismo rango, se produce una fusión amistosa y las dos ciudades se fusionan en una sola. Se elige un nuevo nombre para la ciudad recién creada, se elige una aldea gobernante y se reorienta el camino desde el gobernante anterior hasta el nodo en el vínculo de fusión de modo que conduzca al nuevo líder. La nueva ciudad también aumenta su rango en uno. Tenga en cuenta que esta es la única forma en que dos ciudades pueden aumentar el rango de la otra. ${\displaystyle rank(C)=rank(C')\land e_{merge}(C,C')=e_{merge}(C',C)}$
2. Absorción: : Si la ciudad solicitante tiene un rango inferior, la ciudad receptora realiza un proceso de absorción : es absorbida como en la fusión amistosa, pero pierde su nombre y la ciudad resultante tiene el rango de . ${\displaystyle rank(C)<rank(C')}$ ${\displaystyle C}$ ${\displaystyle C'}$
3. Suspensión: : En tales casos congela la solicitud: espera ser absorbida por la regla 2 o fusionarse y aumentar su rango por encima del de para poder promulgar la regla 1 y absorber . ${\textstyle rank(C)=rank(C')\land e_{merge}(C,C')\neq e_{merge}(C',C)\lor rank(C)>rank(C')}$ ${\displaystyle C'}$ ${\displaystyle C}$ ${\displaystyle C}$

Mensajes externos

Ningún nodo del grafo tiene una lista de aldeas que pertenecen a su aldea, por lo tanto, cada vez que una ciudad quiere buscar aristas que conducen hacia afuera de ella, tiene que adoptar un protocolo de pregunta-respuesta . El gobernante de la ciudad envía un mensaje de difusión a través de su árbol de expansión, y cada nodo que lo recibe envía solicitudes a sus vecinos, excluyendo las aristas a sus hijos y padre. El protocolo de respuesta es el siguiente: ${\displaystyle x}$

• ${\displaystyle x.city=y.city}$:claramente el borde es un intra-borde en . e intercambian respuestas negativas. ${\displaystyle C}$ ${\displaystyle x}$ ${\displaystyle y}$
• ${\displaystyle x.city\neq y.city\land x.rank<y.rank}$: está pidiendo a una ciudad de mayor rango. Por la regla 2 podemos afirmar que no se produce absorción y que, de hecho, pertenece a otra ciudad. ${\displaystyle x}$ ${\displaystyle y}$
• ${\displaystyle x.city\neq y.city\land x.rank>y.rank}$:en este caso se retrasará la respuesta como indica la regla 3 . ${\displaystyle y}$

Propiedades

Mega-Merger posee varias propiedades:

• Rango monótono : Cada ciudad , excluidas las megaciudades, subirá de rango eventualmente. Por la regla 1 podría fusionarse amistosamente, aumentando su rango en ; por las reglas 2 y 3 tendrán un enlace de fusión (por hipótesis no es la megaciudad) o bien pedirá una ciudad de rango superior , siendo absorbida y aumentando su rango, o esperará hasta que alcance su nivel y realizará una fusión amistosa . ${\displaystyle C}$ ${\displaystyle C}$ ${\displaystyle 1}$ ${\displaystyle C}$ ${\displaystyle C}$ ${\displaystyle C'}$ ${\displaystyle C'}$
• ${\displaystyle rank(C)=K\implies |C|\geq 2^{k}}$: tenemos un aumento de nivel cada vez que se realiza una fusión amistosa . Calculamos por inducción: en el caso base, , exactamente una aldea está en . En el caso inductivo, dos ciudades operan una fusión amistosa, por lo tanto, por hipótesis inductiva. ${\displaystyle rank(C)=0}$ ${\displaystyle C}$ ${\displaystyle C',C''s.t.rank(C')=rank(C'')=k}$ ${\displaystyle |C'-C''|=|C'|+|C''|=2^{k}+2^{k}=2^{k+1}}$
• ${\displaystyle \max {rank(C)}\leq \log n}$:según la regla anterior las ciudades se construyen sobre una base exponencial , de ahí la inversa . ${\displaystyle 2}$ ${\displaystyle \log _{2}n}$
• Prevención de punto muerto : la megafusión no incurre en ningún punto muerto. Como se muestra en la regla 3, una ciudad puede esperar a que una ciudad de rango inferior responda en el enlace de fusión : para incurrir en un punto muerto, dicha ciudad tendría que esperar en , y en , y así sucesivamente hasta que se detecte un ciclo en la espera de en un enlace de fusión . Pero por hipótesis es el enlace de fusión de , por lo tanto, dicha cadena no puede existir. La otra situación que induce un punto muerto es una solicitud de a donde tiene un enlace de fusión diferente a . Aún así, como se muestra por el rango monótono, o aumentará su rango para absorber , o consumirá todos sus enlaces de fusión para ser la única ciudad en el gráfico con . Trivialmente, en tal caso, los dos enlaces de fusión coincidirían y se verían obligados a la absorción por la regla 2 . ${\displaystyle C}$ ${\displaystyle e}$ ${\displaystyle C'}$ ${\displaystyle C''}$ ${\displaystyle C''}$ ${\displaystyle C'''}$ ${\displaystyle C^{n}}$ ${\displaystyle C}$ ${\displaystyle e'}$ ${\displaystyle e}$ ${\displaystyle C}$ ${\displaystyle C}$ ${\displaystyle C'}$ ${\displaystyle C'}$ ${\displaystyle C}$ ${\displaystyle C'}$ ${\displaystyle C}$ ${\displaystyle C}$ ${\displaystyle C'}$

Terminación

La terminación se garantiza mediante prevención de bloqueo y confiabilidad total .

Costo

El análisis de costos tiene dos componentes: el costo de la etapa y el límite superior de la etapa. Una ciudad ejecuta una etapa solicitando un enlace de fusión a sus aldeas y aplicando una de las reglas anteriores según la situación deseada. Podemos dividir esta etapa en cinco pasos: ${\displaystyle C}$

1. Solicitud de difusión para el enlace de fusión a los nodos del árbol. ${\displaystyle \leq n}$
2. Cada nodo reenvía un mensaje a sus vecinos y espera sus respuestas. ${\displaystyle outside?}$ ${\displaystyle \leq n}$ ${\displaystyle \leq n}$
3. Luego, los nodos envían las respuestas al gobernante de la ciudad mediante convergecast para un total de mensajes. ${\displaystyle \leq n}$
4. Luego, la raíz decide si se debe fusionar el enlace y envía un mensaje al nodo elegido. Este mensaje, por lo general, debe pasar por varios nodos. ${\displaystyle height(Tree)\leq n}$

Estas cinco fases de solicitud, descubrimiento externo, comunicación y entrega tienen un costo total de . En cuanto a los mensajes desperdiciados entre nodos internos, cada nodo tiene como máximo 100 aristas internas, o si es una hoja, un total de mensajes internos desperdiciados. ${\displaystyle n+2n+n+n\leq 5n}$ ${\displaystyle outside?}$ ${\displaystyle x}$ ${\displaystyle deg(x)-2}$ ${\displaystyle deg(x)-1}$ ${\displaystyle x}$ ${\displaystyle 2m-n}$

Ahora, en cuanto a la cantidad de etapas, según la propiedad presentada anteriormente sobre el tamaño de las ciudades, cada ciudad de nivel tiene , por lo tanto, el rango más alto al que se puede llegar es . Como las ciudades pueden fusionarse/ser absorbidas solo una vez por etapa, tenemos un total de mensajes totales. ${\displaystyle k}$ ${\displaystyle \geq 2^{k}}$ ${\displaystyle log_{2}{n}}$ ${\displaystyle 2m+n+5n\log {n}}$

Exactitud

Mega-Merger crea un árbol de expansión mínimo fusionando subárboles a través de la ruta de costo mínimo, es decir, el enlace de fusión. Por definición de árbol de expansión mínimo, un árbol de expansión mínimo es un conjunto de árboles de expansión mínimos conectados a través de rutas de costo mínimo. Por construcción, Mega-Merger reenvía una solicitud a través de su enlace de fusión y, tarde o temprano, ese borde va a ser parte del árbol por prevención de interbloqueo .

Referencias

1. Gallager, Robert (1983). "Un algoritmo distribuido para el árbol de expansión mínimo" (PDF) . Instituto Tecnológico de Massachusetts .
2. Awerbuch, Baruch (1987). "Algoritmo distribuido óptimo para árboles de expansión de peso mínimo, conteo, elección de líder y otros problemas" (PDF) . Revista SIAM sobre informática .