Yo-Yo es un algoritmo distribuido destinado a la búsqueda mínima y la elección de 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.
Yo-yo fue presentado por Nicola Santoro. [3] Procede mediante 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 otra hacia atrás, llamada "-Yo".
Yo-Yo builds elige un líder mínimo bajo las siguientes premisas:
No son necesarias más restricciones.
La fase de preprocesamiento se inicia con una transmisión. En 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 sólo un paso lógico, el canal bidireccional no se pierde en el procedimiento. Mediante convergecast se notifica al iniciador la terminación del preprocesamiento. Este proceso crea tres categorías de nodos:
La fase "Yo-" la inician las fuentes. Una fuente envía su identificación a través de sus bordes entrantes y espera. Los nodos intermedios esperan recibir los respectivos identificadores 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 reenvía a través de los bordes salientes. Los sumideros 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".
Los receptores 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. Se envía un SÍ 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 suben por la estructura hasta las fuentes: las fuentes con al menos un NO entrante quedan muertas y pierden su estatus de candidatas.
La fase "-Yo" también comprende una fase de reestructuración en la que las fuentes-intermedias-sumideros se acomodan 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.
La poda es una técnica de optimización que se aplica en la fase "-Yo", y su mensaje suele incorporarse con la respuesta positiva/negativa. Elimina bordes y nodos inútiles. Los primeros son bordes que reciben el mismo valor de los bordes entrantes: trivialmente son inútiles y el nodo los recorta. 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 con borde 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 encontrar el mínimo.
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 Yo-Yo consisten en un escaneo hacia adelante y hacia atrás de la estructura, por lo tanto mensajes, donde es el número de flancos activos 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 mediante 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, los nodos intermedios se conectan en pares y en cada iteración se eliminan como máximo la mitad de las fuentes. Al reestructurar, cada una de las fuentes supervivientes ahora estará conectada en pares. Como en el caso anterior, como mucho sobrevivirá la mitad. Claramente la terminación se cumple cuando sólo queda una fuente. La reducción a la mitad impone una serie de iteraciones sobre el último cálculo, es decir, el que se realiza entre las dos fuentes supervivientes más alejadas, situadas en . El costo total asciende a .
La terminación está garantizada por el interruptor en las direcciones realizadas en el tirón SÍ / NO . La reducción de fuentes en la fase "-Yo" es monótona: según la observación previa cada fuente se compara con al menos otra fuente, y por la unicidad de las fuentes, una de ellas prevalece mientras las otras mueren. Dado que el número de fuentes iniciales es finito, la reducción monótona dará lugar a que quede una única fuente.
