Megafusión

Algoritmo distribuido en teoría de grafos

La megafusión es un algoritmo distribuido destinado a resolver el problema electoral en un gráfico genérico conectado no dirigido . ^{[1] [2]}

Introducción

Mega-Merger fue desarrollado por Robert Gray Gallager en el MIT en 1983. Aplica un enfoque distribuido de dividir y conquistar combinado con una estrategia de conquista basada en rangos. El algoritmo suele presentarse mediante una analogía entre pueblo y ciudad. Cada nodo en el gráfico indica una aldea, mientras que los bordes que los conectan son las carreteras y un árbol de expansión arraigado en un subgráfico es una ciudad. Todo el gráfico es entonces una megaciudad. Mega-Merger empuja a las aldeas a unirse para formar ciudades de acuerdo con el rango y las ventajas de cada una. Las ciudades se forman entonces mediante alianzas o mediante conquista/absorción.

Requisitos previos

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

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

No son necesarias más restricciones.

Algoritmo

El algoritmo asigna a cada pueblo un nombre y un rango, el primero suele ser único. Este último indica el número de fusiones amistosas por las que ha pasado la ciudad, y cuanto más grande es, más poderosa se considera una ciudad. Además, a cada borde se le asigna un peso: cada pueblo/ciudad tiene un borde de peso mínimo, también llamado enlace de fusión , es decir, el borde 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 . La solicitud se maneja de las siguientes maneras: ${\displaystyle e_{merge}(C,C')}$ ${\displaystyle C'}$

1. Fusión amistosa : si las ciudades comparten el mismo enlace de fusión y tienen el mismo rango, se produce una fusión amistosa y las dos ciudades se fusionan en una. Se elige un nuevo nombre para la ciudad recién creada, se elige una aldea gobernante y el camino desde el gobernante anterior hasta el nodo en el enlace de fusión se reorienta de manera 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 en el extremo receptor 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 a 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 en el gráfico tiene una lista de aldeas que pertenecen a su aldea, por lo tanto, cada vez que una ciudad quiere buscar bordes que conduzcan fuera de ella, debe 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 los bordes a sus hijos y padres. El protocolo de respuesta es el siguiente: ${\displaystyle x}$

• ${\displaystyle x.city=y.city}$: claramente el borde es un intra-borde en . e intercambiar respuestas negativas. ${\displaystyle C}$ ${\displaystyle x}$ ${\displaystyle y}$
• ${\displaystyle x.city\neq y.city\land x.rank<y.rank}$: está preguntando a una ciudad de mayor rango. Por la regla 2 podemos afirmar que no se produce absorción, y efectivamente 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 según la regla 3 . ${\displaystyle y}$

Propiedades

Mega-Merger tiene varias propiedades:

• Rango monótono : cada ciudad , excluidas las megaciudades, eventualmente ascenderá de rango. Por la regla 1 podrían fusionarse amigos, elevando su rango en ; según las reglas 2 y 3 tendrá un enlace de fusión (por hipótesis no es la megaciudad), preguntará a una ciudad de rango superior , será absorbida y aumentará su rango, o esperará hasta alcanzar su nivel y operará 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 opera una fusión amistosa . Calculamos por inducción: en el caso base, exactamente hay una aldea en . En el caso inductivo, dos ciudades operan una fusión amistosa, por 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í lo inverso . ${\displaystyle 2}$ ${\displaystyle \log _{2}n}$
• Prevención de punto muerto : Mega-Merger 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 , y seguir , y así sucesivamente hasta que se detecte un ciclo de espera. en un enlace de fusión . Pero por hipótesis es el eslabón de fusión de , por lo tanto, dicha cadena no puede existir. La otra situación que provoca un punto muerto es una solicitud desde hacia donde tiene un enlace de fusión diferente al de . Aún así, como lo muestra el rango monótono, aumentará su rango para absorber o consumirá todos sus enlaces de fusión para ser la única ciudad en el gráfico con . En tal caso, trivialmente, los dos vínculos de fusión coincidirían y se verían obligados a absorberse 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 interbloqueo y total confiabilidad .

Costo

El análisis de costos tiene dos componentes, el costo de etapa y el límite superior de etapa. Una ciudad representa una etapa solicitando un enlace de fusión de sus aldeas y aplicando una de las reglas anteriores de acuerdo con 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 obtener un total de mensajes. ${\displaystyle \leq n}$
4. Luego, la raíz decide sobre un enlace de fusión y envía un mensaje al nodo elegido. Trivialmente, este mensaje deberá viajar por los nodos. ${\displaystyle height(Tree)\leq n}$

Estas cinco fases de solicitud, descubrimiento externo, comunicación y entrega tienen un coste total de . En cuanto a los mensajes desperdiciados entre nodos internos, cada nodo tiene como máximo bordes internos, o si es una hoja, para 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 el número de etapas. Según la propiedad presentada anteriormente sobre el tamaño de las ciudades, cada ciudad tiene un nivel , por lo tanto, el rango más alto alcanzable es . Dado que las ciudades pueden fusionarse/absorberse 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 será parte del árbol mediante la prevención de interbloqueo .

Referencias

1. Gallager, Robert (1983). "Un algoritmo distribuido para árbol de expansión mínima" (PDF) . Instituto de Tecnología de Massachusetts .
2. Awerbuch, Baruch (1987). "Algoritmo distribuido óptimo para árbol de extensión de peso mínimo, conteo, elección de líder y otros problemas" (PDF) . Revista SIAM de Computación .