Yo-yo (algoritmo)

Yo-Yo es un algoritmo distribuido destinado a la búsqueda del mínimo y la elección del líder en un grafo no dirigido conectado genérico . ^{[ 1 ] [ 2 ]} A diferencia de Mega-Merger , tiene una terminación y un análisis de costos triviales.

Yo-yo fue introducido por Nicola Santoro. ^{[ 3 ]} Procede mediante eliminación consecutiva y una técnica de reducción de grafos 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 fase hacia atrás, llamada "-Yo".

Yo-Yo Builds elige un líder mínimo bajo las siguientes premisas:

• Fiabilidad total: No se pierde ningún mensaje durante la transmisión.
• Valores distintivos iniciales (ID): Cada nodo tiene un identificador único.
• Canales de comunicación bidireccionales: Cada extremo es bidireccional, por lo que las comunicaciones pueden viajar en ambas direcciones.

No son necesarias restricciones adicionales.

La fase de preprocesamiento se compone de un intercambio a través de cada arista de los dos nodos incidentes en la arista. Por lo tanto, tenemos un costo de${\displaystyle \sum _{v\in V}deg(v)=2m}$Las fases Yo-Yo consisten en un escaneo hacia adelante y hacia atrás de la estructura, por lo tanto${\displaystyle 2m_{i}}$mensajes, donde${\displaystyle m_{i}}$es el número de aristas activas actuales. El número de iteraciones viene dado por el número de iteraciones necesarias para eliminar cada fuente inicial. Por hipótesis, cada fuente está vinculada a al menos otra mediante un nodo intermedio: si no fuera así, entonces sería un componente desconectado del grafo, pero por definición el grafo está conectado. En el peor de los casos, intermedio${\displaystyle n_{i}}$Los nodos están conectados en pares y en cada iteración se elimina como máximo la mitad de las fuentes. Al reestructurar cada uno de los supervivientes${\displaystyle n_{i+1}}$Ahora las fuentes estarán conectadas en pares. Como en el caso anterior, sobrevivirá como máximo la mitad. Claramente, la terminación se alcanza cuando solo queda una fuente. La reducción a la mitad impone una${\displaystyle log_{2}n}$número de iteraciones sobre el último cálculo, es decir, el que se encuentra entre las dos fuentes supervivientes más alejadas, situado en${\displaystyle diam(G)}$El coste total asciende a${\displaystyle 2m\log {n}}$.

La terminación está garantizada por el cambio de dirección realizado en la prueba 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 debido a la unicidad de las fuentes, una de ellas prevalece mientras que las demás se desactivan. Dado que el número de fuentes iniciales es finito, la reducción monótona dará como resultado que quede una sola fuente.