La megafusión es un algoritmo distribuido destinado a resolver el problema de la elección 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 mezclado con una estrategia de conquista basada en rangos. El algoritmo generalmente se presenta a través de una analogía pueblo-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 enraizado en un subgráfico es una ciudad. Entonces, todo el gráfico es una megaciudad. Mega-Merger empuja a las aldeas a unirse para formar ciudades de acuerdo con el rango y los límites de cada uno. Las ciudades se forman entonces por alianzas o por conquista / absorción.
Prerrequisitos
Mega-Merger crea un árbol de expansión mínimo sobre los gráficos conectados proporcionados:
- Fiabilidad total: ningún mensaje se pierde en la transmisión.
- UI (iniciador único): un solo 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 aldea un nombre y un rango, el primero generalmente ú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 , que es el borde cuyo recorrido tiene un costo mínimo.
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 es manejada por de las siguientes formas:
- 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. Se elige un nuevo nombre para la ciudad recién creada, se elige una aldea gobernante y el camino desde el gobernante anterior al nodo en el enlace de fusión se reorienta de manera que conduce al nuevo líder. La nueva ciudad también tiene su rango aumentado en uno. Tenga en cuenta que esta es la única forma en que dos ciudades pueden aumentar el rango de la otra.
- Absorción: : Si la ciudad solicitante tiene un rango más bajo, la ciudad en el extremo receptor promulga un proceso de absorción : se absorbe como en la fusión amistosa, pero pierde su nombre y la ciudad resultante tiene el rango de .
- Suspensión: : En esos casos congela la solicitud: espera ser absorbida por la regla 2 o fusionarse y aumentar su rango por encima del depara poder promulgar la regla 1 y absorber.
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 y respuesta . El gobernante de la ciudad envía un mensaje de difusión a través de su árbol de expansión, y cada nodorecibirlo envía solicitudes a sus vecinos, excluyendo los bordes a sus hijos y padres. El protocolo de respuesta es el siguiente:
- : claramente el borde es un intra-borde en . y intercambiar respuestas negativas.
- : está pidiendo a una ciudad de rango superior. Por la regla 2 podemos afirmar que no ocurre absorción, y de hecho pertenece a otra ciudad.
- : en este caso retrasará la respuesta según la regla 3 .
Propiedades
Mega-Merger tiene varias propiedades:
- Rango monótono : cada ciudad, excluida la megaciudad, eventualmente subirá de rango. Por la regla 1 podría fusionarse amistosamente, elevando su rango en ; por la regla 2 y 3 tendrá un enlace de fusión (por hipótesis no es la megaciudad) o le preguntará a una ciudad de rango superior , siendo absorbido y aumentando su rango, o esperar hasta alcanza su nivel y opera una fusión amistosa .
- : tenemos un aumento de nivel cada vez que se opera una fusión amistosa . Calculamos por inducción: en el caso base,, exactamente un pueblo está en . En el caso inductivo, dos ciudades operar una fusión amistosa, por lo tanto por hipótesis inductiva.
- : según la regla anterior, las ciudades se construyen sobre una base exponencial , de ahí la inversa .
- Prevención de interbloqueo: Mega-Merger no incurre en ningún interbloqueo. Como muestra la regla 3, una ciudad puede esperar a que una ciudad de rango inferior responda en el enlace de combinación : para incurrir en un callejón sin salida tal ciudad tendría que esperar , y en y así sucesivamente hasta que se detecte un ciclo en Esperando que en un enlace de fusión . Pero por hipótesis es el enlace de fusión de , por lo tanto, tal cadena no puede existir. La otra situación que induce a un punto muerto es una solicitud de a dónde tiene un enlace de combinación diferente al . Aún así, como lo muestra el rango monótono aumentará su rango para absorber , o consumirá todos sus enlaces de combinación para ser la única ciudad en el gráfico con . Trivialmente, en tal caso, los dos enlaces de fusión coincidirían yse vería obligado a absorberlo por la regla 2 .
Terminación
La terminación se otorga mediante prevención de interbloqueo y total confiabilidad .
Costo
El análisis de costos tiene dos componentes, el costo de la etapa y el límite superior de la etapa. Una ciudadpromulga 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:
- Solicitud de difusión para un enlace de fusión al nodos en el árbol.
- Cada nodo reenvía un mensaje a su vecinos y espera a sus respuestas.
- Luego, los nodos envían las respuestas al gobernante de la ciudad por convergecast para un total de mensajes.
- Luego, la raíz decide sobre un enlace de fusión y envía un mensaje al nodo elegido. Trivialmente, este mensaje deberá viajar nodos.
Estas cinco fases de solicitud, descubrimiento externo, comunicación y entrega tienen un costo total de . En cuanto a los mensajes desperdiciados en el entre los nodos internos, cada nodo tiene como máximo bordes internos, o Si es una hoja, para un total de mensajes internos desperdiciados.
Ahora el número de etapas. Por la propiedad presentada anteriormente sobre el tamaño de las ciudades, cada ciudad de nivel posee , por lo que el rango más grande alcanzable es . Dado que las ciudades pueden fusionarse / absorberse solo una vez por etapa, tenemos un total demensajes totales.
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 que tarde o temprano ese borde será parte del árbol mediante la prevención de interbloqueo .
Referencias
- ^ Gallager, Robert (1983). "Un algoritmo distribuido para un árbol de expansión mínimo" (PDF) . Instituto de Tecnología de Massachusetts .
- ^ Awerbuch, Baruch (1987). "Algoritmo distribuido óptimo para árbol de expansión de peso mínimo, recuento, elección de líder y otros problemas" (PDF) . Revista SIAM de Computación .