Elección del líder

Se dice que un anillo es anónimo si cada procesador es idéntico. Más formalmente, el sistema tiene la misma máquina de estados para cada procesador. ^{[ 3 ]} No hay un algoritmo determinista para elegir un líder en anillos anónimos, incluso cuando el tamaño de la red es conocido por los procesos. ^{[ 3 ] [ 6 ]} Esto se debe a que no hay posibilidad de romper la simetría en un anillo anónimo si todos los procesos se ejecutan a la misma velocidad. El estado de los procesadores después de algunos pasos solo depende del estado inicial de los nodos vecinos. Por lo tanto, debido a que sus estados son idénticos y ejecutan los mismos procedimientos, en cada ronda cada procesador envía los mismos mensajes. Por consiguiente, el estado de cada procesador también cambia de forma idéntica y, como resultado, si un procesador es elegido como líder, también lo son todos los demás.

Para simplificar, aquí hay una demostración en anillos síncronos anónimos. Es una demostración por contradicción. Consideremos un anillo anónimo R con tamaño n>1. Supongamos que existe un algoritmo "A" para resolver la elección de líder en este anillo anónimo R. ^{[ 3 ]}

Lema : después de la ronda${\displaystyle k}$de la ejecución admisible de A en R, todos los procesos tienen los mismos estados.

Demostración. Demostración por inducción en${\displaystyle k}$.

Caso base:${\displaystyle k=0}$: todos los procesos están en el estado inicial, por lo que todos los procesos son idénticos.

Hipótesis de inducción: supongamos que el lema es verdadero para${\displaystyle k-1}$rondas.

Paso inductivo: en ronda${\displaystyle k}$, cada proceso envía el mismo mensaje${\displaystyle m_{r}}$a la derecha y enviar el mismo mensaje${\displaystyle m_{l}}$a la izquierda. Dado que todos los procesos están en el mismo estado después de la ronda${\displaystyle k-1}$En la ronda k, cada proceso recibirá el mensaje.${\displaystyle m_{r}}$desde el borde izquierdo, y recibirá el mensaje${\displaystyle m_{l}}$desde el borde derecho. Dado que todos los procesos reciben los mismos mensajes en la ronda${\displaystyle k}$, están en el mismo estado después de la ronda${\displaystyle k}$.

El lema anterior contradice el hecho de que, después de un número finito de rondas en una ejecución de A, un proceso entró en el estado elegido y otros procesos entraron en el estado no elegido.

Un método común para resolver el problema de la elección de líder en redes anónimas es el uso de algoritmos probabilísticos . En estos métodos, los procesadores suelen asumir identidades basadas en una función probabilística y las comunican al resto de la red. Finalmente, mediante la aplicación de un algoritmo, se selecciona un líder (con alta probabilidad).

anillo asíncrono

Fuente: ^{[ 3 ]}

Dado que no existe un algoritmo para anillos anónimos (demostrado anteriormente), los anillos asíncronos se considerarían anillos asíncronos no anónimos. En los anillos no anónimos, cada proceso tiene un identificador único.${\displaystyle id}$y no conocen el tamaño del anillo. La elección de líder en anillos asíncronos se puede resolver mediante algún algoritmo que utilice${\displaystyle O(n^{2})}$mensajes o${\displaystyle O(n\log n)}$mensajes.

En el${\displaystyle O(n^{2})}$algoritmo, cada proceso envía un mensaje con su${\displaystyle id}$hacia el borde izquierdo. Luego espera hasta que llegue un mensaje del borde derecho. Si el${\displaystyle id}$en el mensaje es mayor que su propio${\displaystyle id}$, entonces reenvía el mensaje al borde izquierdo; de lo contrario, ignora el mensaje y no hace nada. Si el${\displaystyle id}$en el mensaje es igual a su propio${\displaystyle id}$, luego envía un mensaje a la izquierda anunciando que ha sido elegido. Otros procesos reenvían el anuncio a la izquierda y se convierten en no electos. Está claro que el límite superior es${\displaystyle O(n^{2})}$para este algoritmo.

En el${\displaystyle O(n\log n)}$El algoritmo se ejecuta por fases.${\displaystyle k}$En la fase 1, un proceso determinará si es el ganador entre el lado izquierdo.${\displaystyle 2^{k}}$y lado derecho${\displaystyle 2^{k}}$vecinos. Si es un ganador, entonces el proceso puede pasar a la siguiente fase. En la fase${\displaystyle 0}$, cada proceso${\displaystyle P}$necesita determinar si es un ganador o no enviando un mensaje con su${\displaystyle id}$a los vecinos de la izquierda y de la derecha (los vecinos no reenvían el mensaje). El vecino responde y${\displaystyle ACK}$solo si el${\displaystyle id}$en el mensaje es más grande que el del vecino${\displaystyle id}$, de lo contrario responde un${\displaystyle ACK_{fault}}$. Si${\displaystyle P}$recibe dos${\displaystyle ACK}$s, uno desde la izquierda, uno desde la derecha, luego${\displaystyle P}$es el ganador en la fase${\displaystyle 0}$. En fase${\displaystyle k}$, los ganadores en fase${\displaystyle k-1}$necesita enviar un mensaje con su${\displaystyle id}$hacia${\displaystyle 2^{k}}$izquierda y${\displaystyle 2^{k}}$vecinos correctos. Si los vecinos en el camino reciben el${\displaystyle id}$en el mensaje más grande que su${\displaystyle id}$, entonces reenvíe el mensaje al siguiente vecino, de lo contrario responda un${\displaystyle ACK_{fault}}$. Si el${\displaystyle 2^{k}}$El vecino recibe el${\displaystyle id}$más grande que su${\displaystyle id}$, luego devuelve un${\displaystyle ACK}$, de lo contrario responde un${\displaystyle ACK_{fault}}$. Si el proceso recibe dos${\displaystyle ACK}$s, entonces es el ganador en la fase${\displaystyle k}$. En la última fase, el ganador final recibirá su propio${\displaystyle id}$en el mensaje, luego termina y envía un mensaje de terminación a los otros procesos. En el peor de los casos, cada fase tiene como máximo${\displaystyle {\frac {n}{2^{k}+1}}}$ganadores, donde${\displaystyle k}$es el número de fase. Hay${\displaystyle \lceil \log(n-1)\rceil }$fases en total. Cada ganador envía en el orden de${\displaystyle 2^{k}}$mensajes en cada fase. Por lo tanto, la complejidad de los mensajes es${\displaystyle O(n\log n)}$.

En uno de los primeros trabajos, Chang y Roberts ^{[ 14 ]} propusieron un algoritmo uniforme en el que se selecciona como líder un procesador con el ID más alto. Cada procesador envía su ID en sentido horario. Un procesador recibe un mensaje y compara el ID con el suyo. Si el ID es mayor que el del procesador, lo deja pasar; de lo contrario, descarta el mensaje. Los autores demuestran que este algoritmo utiliza${\displaystyle O(n^{2})}$mensajes en el peor de los casos y${\displaystyle O(n\log n)}$en el caso promedio. Hirschberg y Sinclair ^{[ 15 ]} mejoraron este algoritmo con${\displaystyle O(n\log n)}$Se reduce la complejidad de los mensajes mediante la introducción de un esquema de paso de mensajes bidireccional.

Un algoritmo típico para resolver la elección de líder en una malla no orientada consiste en elegir solo uno de los cuatro nodos de las esquinas como líder. Dado que los nodos de las esquinas podrían desconocer el estado de otros procesos, el algoritmo debe primero activarlos. Un líder puede elegirse de la siguiente manera. ^{[ 17 ]}

1. Proceso de despertar : en el que${\displaystyle k}$Los nodos inician el proceso de elección. Cada iniciador envía un mensaje de activación a todos sus nodos vecinos. Si un nodo no es el iniciador, simplemente reenvía los mensajes a los demás nodos. En esta etapa, como máximo,${\displaystyle 3n+k}$Los mensajes se envían.
2. Proceso electoral : la elección en el anillo exterior toma como máximo dos etapas con${\displaystyle 6(a+b)-16}$mensajes.
3. Terminación : el líder envía un mensaje de terminación a todos los nodos. Esto requiere como máximo 2n mensajes.

La complejidad del mensaje es como máximo${\displaystyle 6(a+b)-16}$y si la malla tiene forma cuadrada,${\displaystyle O({\sqrt {n}})}$.

Una malla orientada es un caso especial donde los números de puerto son etiquetas de brújula, es decir, norte, sur, este y oeste. La elección del líder en una malla orientada es trivial. Solo necesitamos designar una esquina, por ejemplo, "norte" y "este", y asegurarnos de que ese nodo sepa que es el líder.

Un caso especial de arquitectura de malla es el toro, que es una malla con "envolvimiento". En esta estructura, cada nodo tiene exactamente 4 aristas de conexión. Un método para elegir un líder en dicha estructura se conoce como etapas electorales. De forma similar a los procedimientos en estructuras de anillo, este método elimina en cada etapa a los candidatos potenciales hasta que finalmente queda un nodo candidato. Este nodo se convierte en el líder y luego notifica a todos los demás procesos su terminación. ^{[ 16 ]} Este método puede utilizarse para lograr una complejidad de O(n). También se han introducido enfoques más prácticos para lidiar con la presencia de enlaces defectuosos en la red. ^{[ 18 ] [ 19 ]}

El protocolo Shout construye un árbol de expansión sobre un grafo genérico y elige su raíz como líder. El algoritmo tiene un coste total lineal con respecto a la cardinalidad de las aristas.

Esta técnica es similar a encontrar un Árbol de Expansión Mínima (MST) en el que la raíz del árbol se convierte en el líder. La idea es que los nodos individuales se "fusionan" entre sí para formar estructuras más grandes. El resultado de este algoritmo es un árbol (un grafo sin ciclos) cuya raíz es el líder de todo el sistema. El costo del método de mega-fusión es${\displaystyle O(m+n\log n)}$donde m es el número de aristas y n es el número de nodos.

Yo-yo (algoritmo) es un algoritmo de búsqueda de mínimo que consta de dos partes: una fase de preprocesamiento y una serie de iteraciones. ^{[ 16 ]} En la primera fase o configuración , cada nodo intercambia su id con todos sus vecinos y, según el valor, orienta sus aristas incidentes. Por ejemplo, si el nodo x tiene un id menor que y, x se orienta hacia y. Si un nodo tiene un id menor que todos sus vecinos, se convierte en una fuente . Por el contrario, un nodo con todas las aristas internas (es decir, con un id mayor que todos sus vecinos) es un sumidero . Todos los demás nodos son nodos internos . Una vez que todas las aristas están orientadas, comienza la fase de iteración . Cada iteración es una etapa electoral en la que se eliminarán algunos candidatos. Cada iteración tiene dos fases: YO- y –YO . En esta fase, las fuentes comienzan el proceso para propagar a cada sumidero los valores más pequeños de las fuentes conectadas a ese sumidero.

Yo-

1. Una fuente (mínimo local) transmite su valor a todos sus vecinos externos.
2. Un nodo interno espera a recibir un valor de todos sus vecinos internos. Calcula el mínimo y lo envía a su vecino externo.
3. Un sumidero (un nodo sin arista saliente) recibe todos los valores y calcula su mínimo.

-yo

1. Un fregadero envía SÍ a los vecinos que vieron el valor más pequeño y NO a los demás.
2. Un nodo interno envía SÍ a todos los nodos vecinos de los que recibió el valor más pequeño y NO a los demás. Si recibe solo un NO, envía NO a todos.
3. Una fuente espera hasta recibir todos los votos. Si todos son SÍ, sobrevive; si no, deja de ser candidata.
4. Cuando un nodo x envía NO a un nodo vecino y, la dirección lógica de esa arista se invierte.
5. Cuando un nodo y recibe NO de un vecino saliente, invierte la dirección de ese enlace.

Tras la etapa final, cualquier fuente que reciba un NO deja de ser una fuente y se convierte en un sumidero. Además, se introduce una etapa adicional, la poda , para eliminar los nodos inútiles, es decir, aquellos cuya existencia no influye en las siguientes iteraciones.

1. Si un fregadero está lleno de hojas, entonces es inútil y por lo tanto se retira.
2. Si, durante la fase YO, un nodo recibe el mismo valor de más de un nodo vecino, les pedirá a todos menos a uno que eliminen el enlace que los conecta.

Este método tiene un coste total de O(m log n) mensajes. Su complejidad real de mensajes, incluyendo la poda, es un problema de investigación abierto y se desconoce.

En las redes de radio, los n nodos pueden, en cada ronda, elegir entre transmitir o recibir un mensaje. Si no hay detección de colisiones, un nodo no puede distinguir entre el silencio y la recepción de más de un mensaje a la vez. Si hay detección de colisiones , un nodo puede detectar más de un mensaje entrante simultáneamente, aunque en ese caso no se pueda decodificar el mensaje en sí. En el modelo de pitidos , los nodos solo pueden distinguir entre el silencio y al menos un mensaje mediante la detección de portadora .

Los tiempos de ejecución conocidos para redes de un solo salto varían desde un valor constante (esperado con detección de colisiones) hasta O(n log n) rondas (determinista y sin detección de colisiones). En redes de múltiples saltos , los tiempos de ejecución conocidos difieren desde aproximadamente O((D+ log n)(log ² log n)) rondas (con alta probabilidad en el modelo de pitidos), O(D log n) (determinista en el modelo de pitidos), O(n) (determinista con detección de colisiones) hasta O(n log ^3/2 n (log log n) ^0.5 ) rondas (determinista y sin detección de colisiones).