Yo-Yo es un algoritmo distribuido destinado a la búsqueda mínima y la elección del líder en un gráfico genérico conectado no dirigido . [1] [2] A diferencia de Mega-Merger , tiene una terminación trivial y un análisis de costos.
Introducción
Yo-yo fue presentado por Nicola Santoro. [3] Procede por eliminación consecutiva y una técnica de reducción de gráficos llamada poda . El algoritmo se divide en una fase de preprocesamiento seguida de una repetición cíclica de una fase hacia adelante, llamada "Yo-" y una hacia atrás, llamada "-Yo".
Prerrequisitos
Yo-Yo builds elige un líder mínimo bajo las siguientes premisas:
- Fiabilidad total: ningún mensaje se pierde en la transmisión.
- Valores distintivos iniciales (ID): cada nodo tiene un identificador único.
- Canales de comunicaciones bidireccionales: cada borde es bidireccional, las comunicaciones pueden viajar en ambas direcciones.
No son necesarias más restricciones.
Algoritmo
Preprocesamiento
La fase de preprocesamiento se inicia con una transmisión. En el estado despierto, cada nodo envía su identificación a todos sus vecinos y orienta el borde hacia el nodo de mayor grado. Tenga en cuenta que este es solo un paso lógico, el canal bidireccional no se pierde en el procedimiento. Mediante convergecast, se notifica al iniciador de la terminación del preprocesamiento. Este proceso crea tres categorías de nodos:
- Fuentes: nodos con nodos salientes, pero no entrantes. Estos son los menos nodos de cada vecindario.
- Nodos intermedios: nodos con bordes entrantes y salientes. Estos no son ni el menor ni el mayor de los nodos de cada vecindario.
- Fregaderos: nodos con bordes entrantes, pero sin bordes salientes. Estos son los nodos más grandes de cada vecindario.
Yo-
La fase "Yo-" es iniciada por las fuentes. Una fuente envía su identificación a través de sus bordes entrantes y espera. Los nodos intermedios esperan recibir los identificadores respectivos de cada uno de sus bordes entrantes. Una vez que se recopilan todos los valores esperados, se realiza un cálculo mínimo y la identificación mínima se envía a través de los bordes salientes. Los fregaderos son pasivos en esta fase.
Los mensajes se envían a través de los bordes orientados y llegan a los sumideros, que desencadenan la fase "-Yo".
-Yo
Los sumideros inician la fase "-Yo" calculando la identificación mínima recibida y enviando un SÍ positivo o un NO negativo a través de sus bordes entrantes. Un SÍ se envía a través de los bordes que llevan la identificación mínima calculada, un NO a través de los bordes restantes. Los mensajes a pie hasta la estructura de las fuentes: las fuentes con al menos un entrante NO se convierten en muertos y pierden su condición de candidato.
La fase "-Yo" también comprende una fase de reestructuración en la que se acomodan las fuentes-intermedios-sumideros para las fuentes no candidatas. Los bordes que llevan un NO se invierten y los candidatos perdedores de la etapa actual se convierten en sumideros o nodos intermedios.
Poda
La poda es una técnica de optimización aplicada en la fase "-Yo", y su mensaje suele incorporarse con la respuesta positiva / negativa. Elimina bordes y nodos inútiles. Los primeros son aristas que reciben el mismo valor de bordes entrantes: trivialmente son inútiles y recortados por el nodo. Dichos bordes quedan muertos y se ignoran en las siguientes iteraciones. En cambio, este último reduce el número de nodos eliminando sumideros unarios, es decir, sumideros conborde entrante. Estos bordes se verán obligados a devolver el (único) mínimo recibido con una respuesta SÍ , por lo que no realizan ningún cálculo útil para el hallazgo mínimo.
Costo
La fase de preprocesamiento se compone de un intercambio a través de cada borde de los dos nodos incidentes en el borde. Por lo tanto, tenemos un costo de. Las fases de YoYo consisten en un escaneo hacia adelante y hacia atrás de la estructura, por lo tanto mensajes, donde es el número de aristas activas actuales. El número de iteraciones viene dado por el número de iteraciones útiles para eliminar cada fuente inicial. Por hipótesis, cada fuente está vinculada al menos a otra por un nodo intermedio: si este no fuera el caso, entonces un componente desconectado del gráfico, pero por definición el gráfico está conectado. En el peor de los casos intermediolos nodos se conectan en pares y en cada iteración se eliminan como máximo la mitad de las fuentes. Al reestructurar cada uno de los supervivienteslas fuentes ahora estarán conectadas en pares. Como en el caso anterior, a lo sumo la mitad sobrevivirá. Claramente, la terminación se cumple cuando solo queda una fuente. La reducción a la mitad impone un número de iteraciones sobre el último cálculo, es decir, la que se encuentra entre las dos fuentes supervivientes más lejanas, colocadas en . El costo total asciende a.
Terminación
La terminación está garantizada por el cambio en las direcciones realizadas en el tirón SÍ / NO . La reducción de fuentes en la fase "-Yo" es monótona: por la observación anterior cada fuente se compara con al menos otra fuente, y por la unicidad de las fuentes, una de ellas prevalece mientras que las otras mueren. Dado que el número de fuentes iniciales es finito, la reducción monótona conducirá a que quede una sola fuente.
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 .
- ^ Santoro, Nicola. "Diseño y Análisis de Algoritmos Distribuidos" . people.scs.carleton.ca . pag. 213 . Consultado el 13 de marzo de 2017 .