En computación distribuida , la elección de líder es el proceso de designar un único proceso como organizador de alguna tarea distribuida entre varias computadoras (nodos). Antes de que la tarea haya comenzado, todos los nodos de la red desconocen qué nodo actuará como "líder" (o coordinador ) de la tarea o no pueden comunicarse con el coordinador actual. Sin embargo, después de que se haya ejecutado un algoritmo de elección de líder, cada nodo de la red reconoce un nodo particular y único como el líder de la tarea.
Los nodos de la red se comunican entre sí para decidir cuál de ellos pasará a ser el líder. Para ello, necesitan algún método que rompa la simetría entre ellos. Por ejemplo, si cada nodo tiene identidades únicas y comparables, los nodos pueden comparar sus identidades y decidir que el nodo con la identidad más alta es el líder.
La definición de este problema se atribuye a menudo a LeLann, quien lo formalizó como un método para crear un nuevo token en una red de token ring en la que el token se ha perdido.
Los algoritmos de elección de líder están diseñados para ser económicos en términos de total de bytes transmitidos y tiempo. El algoritmo sugerido por Gallager, Humblet y Spira [1] para grafos generales no dirigidos ha tenido un fuerte impacto en el diseño de algoritmos distribuidos en general y ganó el Premio Dijkstra por un artículo influyente en computación distribuida.
Se han sugerido muchos otros algoritmos para diferentes tipos de grafos de red, como anillos no dirigidos, anillos unidireccionales, grafos completos, cuadrículas, grafos de Euler dirigidos y otros. Korach, Kutten y Moran sugirieron un método general que desvincula la cuestión de la familia de grafos del diseño del algoritmo de elección de líder . [2]
El problema de la elección de líder es que cada procesador eventualmente decide si es líder o no, sujeto a la restricción de que exactamente un procesador decida que es el líder. [3] Un algoritmo resuelve el problema de elección de líder si:
Un algoritmo válido de elección de líder debe cumplir las siguientes condiciones: [4]
Un algoritmo para la elección de líder puede variar en los siguientes aspectos: [5]
Una red en anillo es una topología de grafo conectado en la que cada nodo está conectado exactamente a otros dos nodos, es decir, para un grafo con n nodos, hay exactamente n aristas que conectan los nodos. Un anillo puede ser unidireccional, lo que significa que los procesadores solo se comunican en una dirección (un nodo solo podría enviar mensajes hacia la izquierda o solo enviar mensajes hacia la derecha), o bidireccional, lo que significa que los procesadores pueden transmitir y recibir mensajes en ambas direcciones (un nodo podría enviar mensajes hacia la izquierda y hacia la derecha).
Se dice que un anillo es anónimo si todos los procesadores son idénticos. Más formalmente, el sistema tiene la misma máquina de estados para cada procesador. [3] No existe un algoritmo determinista para elegir un líder en anillos anónimos, incluso cuando los procesos conocen el tamaño de la red. [3] [6] Esto se debe al hecho de 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. Entonces, como sus estados son idénticos y ejecutan los mismos procedimientos, en cada ronda cada procesador envía los mismos mensajes. Por lo tanto, el estado de cada procesador también cambia de manera idéntica y, como resultado, si un procesador es elegido como líder, también lo son todos los demás.
Para simplificar, a continuación se presenta una prueba en anillos sincrónicos anónimos. Se trata de una prueba por contradicción. Consideremos un anillo anónimo R con un tamaño n>1. Supongamos que existe un algoritmo "A" para resolver la elección del líder en este anillo anónimo R. [3]
Demostración. Demostración por inducción en .
Caso base : 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 las rondas.
Paso inductivo: en la ronda , cada proceso envía el mismo mensaje a la derecha y envía el mismo mensaje a la izquierda. Dado que todos los procesos están en el mismo estado después de la ronda , en la ronda k, cada proceso recibirá el mensaje del borde izquierdo y recibirá el mensaje del borde derecho. Dado que todos los procesos reciben los mismos mensajes en la ronda , están en el mismo estado después de la ronda .
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 enfoque común para resolver el problema de elección de líder en anillos anónimos es el uso de algoritmos probabilísticos . En tales enfoques, generalmente los procesadores asumen algunas identidades basadas en una función probabilística y la comunican al resto de la red. Al final, mediante la aplicación de un algoritmo, se selecciona un líder (con alta probabilidad).
Dado que no existe un algoritmo para anillos anónimos (como se demostró anteriormente), los anillos asincrónicos se considerarían anillos asincrónicos no anónimos. En los anillos no anónimos, cada proceso tiene un único , y no conocen el tamaño del anillo. La elección del líder en anillos asincrónicos se puede resolver mediante algún algoritmo con el uso de mensajes o mensajes.
En el algoritmo, cada proceso envía un mensaje con su , hacia el borde izquierdo. Luego espera hasta que llegue un mensaje desde el borde derecho. Si el , en el mensaje es mayor que el suyo , entonces reenvía el mensaje hacia el borde izquierdo; de lo contrario, ignora el mensaje y no hace nada. Si el , en el mensaje es igual al suyo , entonces envía un mensaje hacia la izquierda anunciando que yo soy elegido. Otros procesos reenvían el anuncio hacia la izquierda y se convierten en no elegidos. Está claro que el límite superior es para este algoritmo.
En el algoritmo, se ejecuta en fases. En la fase , un proceso determinará si es el ganador entre los vecinos del lado izquierdo y del lado derecho . Si es un ganador, entonces el proceso puede pasar a la siguiente fase. En la fase , cada proceso necesita determinar si es un ganador o no enviando un mensaje con sus a los vecinos izquierdo y derecho (el vecino no reenvía el mensaje). El vecino responde un solo si el en el mensaje es más grande que el del vecino , de lo contrario responde un . Si recibe dos s, uno de la izquierda, uno de la derecha, entonces es el ganador en la fase . En la fase , los ganadores en la fase necesitan enviar un mensaje con sus a los vecinos izquierdo y derecho. Si los vecinos en la ruta reciben el en el mensaje más grande que su , entonces reenvían el mensaje al siguiente vecino, de lo contrario responden un . Si el vecino recibe el más grande que su , entonces envía de vuelta un , de lo contrario responde un . Si el proceso recibe dos s, entonces es el ganador en la fase . En la última fase, el ganador final recibirá su propio mensaje, luego terminará y enviará un mensaje de terminación a los otros procesos. En el peor de los casos, en cada fase hay como máximo ganadores, donde es el número de fase. Hay fases en total. Cada ganador envía en el orden de los mensajes en cada fase. Por lo tanto, la complejidad de los mensajes es .
En el libro Distributed Computing de Attiya y Welch, [3] describieron un algoritmo no uniforme que utiliza mensajes en un anillo sincrónico con un tamaño de anillo conocido . El algoritmo funciona en fases, cada fase tiene rondas, cada ronda es una unidad de tiempo. En la fase , si hay un proceso con , entonces el proceso envía un mensaje de terminación a los otros procesos (el envío de mensajes de terminación cuesta rondas). De lo contrario, pasa a la siguiente fase. El algoritmo verificará si hay un número de fase igual a un proceso , luego realiza los mismos pasos que la fase . Al final de la ejecución, el mínimo será elegido como líder. Usa exactamente mensajes y rondas.
Itai y Rodeh [7] introdujeron un algoritmo para un anillo unidireccional con procesos sincronizados. Suponen que los procesos conocen el tamaño del anillo (número de nodos). Para un anillo de tamaño n, a≤n procesadores están activos. Cada procesador decide con una probabilidad de a^(-1) si se convierte en candidato. Al final de cada fase, cada procesador calcula el número de candidatos c y si es igual a 1, se convierte en el líder. Para determinar el valor de c, cada candidato envía un token (guijarro) al inicio de la fase que se pasa por el anillo y regresa después de exactamente n unidades de tiempo a su remitente. Cada procesador determina c contando el número de guijarros que pasaron. Este algoritmo logra la elección del líder con una complejidad de mensaje esperada de O(nlogn). También se utiliza un enfoque similar en el que se emplea un mecanismo de tiempo de espera para detectar bloqueos en el sistema. [8] También existen algoritmos para anillos de tamaños especiales, como tamaño primo [9] [10] y tamaño impar. [11]
En los enfoques típicos para la elección de líderes, se supone que los procesos conocen el tamaño del anillo. En el caso de anillos anónimos, sin utilizar una entidad externa, no es posible elegir un líder. Incluso suponiendo que exista un algoritmo, el líder no podría estimar el tamaño del anillo. Es decir, en cualquier anillo anónimo, existe una probabilidad positiva de que un algoritmo calcule un tamaño de anillo incorrecto. [12] Para superar este problema, Fisher y Jiang utilizaron un llamado oráculo de líderes Ω? al que cada procesador puede preguntar si existe un líder único. Demuestran que, a partir de cierto punto, se garantiza que devolverá la misma respuesta a todos los procesos. [13]
En uno de los primeros trabajos, Chang y Roberts [14] propusieron un algoritmo uniforme en el que se selecciona como líder a un procesador con el ID más alto. Cada procesador envía su ID en el sentido de las agujas del reloj. Un procesador recibe un mensaje y compara el ID con el suyo propio. Si el ID es mayor, el procesador lo pasa; de lo contrario, descarta el mensaje. Los autores muestran que este algoritmo utiliza mensajes en el peor de los casos y en el caso promedio. Hirschberg y Sinclair [15] mejoraron este algoritmo con la complejidad de los mensajes al introducir un esquema de paso de mensajes bidireccional.
La malla es otra forma popular de topología de red, especialmente en sistemas paralelos, sistemas de memoria redundante y redes de interconexión. [16]
En una estructura de malla, los nodos son de esquina (solo dos vecinos), de borde (solo tres vecinos) o interiores (con cuatro vecinos). El número de aristas en una malla de tamaño axb es m=2ab-ab.
Un algoritmo típico para resolver la elección del 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 pueden no estar al tanto del estado de otros procesos, el algoritmo primero debe despertar a los nodos de las esquinas. Se puede elegir un líder de la siguiente manera. [17]
La complejidad del mensaje es como máximo , y si la malla tiene forma cuadrada, .
Una malla orientada es un caso especial en el que 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 nominar una esquina, por ejemplo, "norte" y "este", y asegurarnos de que el nodo sepa que es un líder.
Un caso especial de arquitectura de malla es un toro, que es una malla con "envoltura". En esta estructura, cada nodo tiene exactamente 4 aristas de conexión. Un enfoque para elegir un líder en este tipo de estructura se conoce como etapas electorales. De manera similar a los procedimientos en las estructuras de anillo, este método en cada etapa elimina 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 de finalización. [16] Este enfoque se puede utilizar para lograr una complejidad de O(n). También se han introducido enfoques más prácticos para tratar la presencia de enlaces defectuosos en la red. [18] [19]
Un hipercubo es una red que consta de nodos, cada uno con grado de y aristas. Se pueden utilizar etapas electorales similares a las anteriores para resolver el problema de la elección del líder. En cada etapa compiten dos nodos (llamados duelistas) y el ganador es promovido a la siguiente etapa. Esto significa que en cada etapa solo la mitad de los duelistas ingresan a la siguiente etapa. Este procedimiento continúa hasta que solo queda un duelista, y se convierte en el líder. Una vez seleccionado, notifica a todos los demás procesos. Este algoritmo requiere mensajes. En el caso de hipercubos no orientados, se puede utilizar un enfoque similar pero con una complejidad de mensaje más alta de . [16]
Las redes completas son estructuras en las que todos los procesos están conectados entre sí, es decir, el grado de cada nodo es n-1, siendo n el tamaño de la red. Se conoce una solución óptima con complejidad de mensajes y espacio O(n). [20] En este algoritmo, los procesos tienen los siguientes estados:
Se supone que, aunque un nodo no conoce el conjunto total de nodos del sistema, se requiere que en esta disposición cada nodo conozca el identificador de su único sucesor, que se denomina vecino, [20] y cada nodo sea conocido por otro. [21]
Todos los procesadores comienzan inicialmente en un estado pasivo hasta que se los despierta. Una vez que los nodos están despiertos, son candidatos para convertirse en el líder. Según un esquema de prioridad, los nodos candidatos colaboran en el anillo virtual. En algún momento, los candidatos se dan cuenta de la identidad de los candidatos que los preceden en el anillo. Los candidatos con mayor prioridad preguntan a los de menor prioridad sobre sus predecesores. Los candidatos con menor prioridad se convierten en nodos ficticios después de responder a los candidatos con mayor prioridad. Según este esquema, el candidato con mayor prioridad finalmente sabe que todos los nodos del sistema son nodos ficticios excepto él mismo, momento en el que sabe que es el líder.
El algoritmo anterior no es correcto: necesita mejoras adicionales. [21]
Como su nombre lo indica, estos algoritmos están diseñados para usarse en cualquier red de procesos sin conocimiento previo de la topología o las propiedades de la red (como el tamaño). [16]
El protocolo Shout construye un árbol de expansión en un gráfico genérico y elige su raíz como líder. El algoritmo tiene un costo total lineal en la cardinalidad de las aristas.
Esta técnica es similar a encontrar un árbol de expansión mínimo (MST, por sus siglas en inglés) en el que la raíz del árbol se convierte en el líder. La idea es que los nodos individuales se "fusionen" entre sí para formar estructuras más grandes. El resultado de este algoritmo es un árbol (un gráfico sin ciclos) cuya raíz es el líder de todo el sistema. El costo del método de megafusión es , 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ínimos 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 en función del 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 hacia dentro (es decir, con 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-
-yo
Después de la etapa final, cualquier fuente que recibe un NO ya no es una fuente y se convierte en un sumidero. También se introduce una etapa adicional, la poda , para eliminar los nodos que son inútiles, es decir, su existencia no tiene impacto en las siguientes iteraciones.
Este método tiene un costo total de O(mlogn) mensajes. Su complejidad real de mensajes, incluida la poda, es un problema de investigación abierto y se desconoce.
En los protocolos de redes de radio, la elección de líder se utiliza a menudo como un primer paso para abordar primitivas de comunicación más avanzadas, como la recopilación de mensajes o las transmisiones. [22] La naturaleza misma de las redes inalámbricas induce colisiones cuando los nodos adyacentes transmiten al mismo tiempo; la elección de un líder permite coordinar mejor este proceso. Si bien el diámetro D de una red es un límite inferior natural para el tiempo necesario para elegir un líder, los límites superior e inferior para el problema de elección de líder dependen del modelo de radio específico estudiado.
En las redes de radio, los n nodos pueden elegir en cada ronda transmitir o recibir un mensaje. Si no hay detección de colisiones disponible, un nodo no puede distinguir entre silencio o recibir más de un mensaje a la vez. Si hay detección de colisiones disponible, un nodo puede detectar más de un mensaje entrante al mismo tiempo, aunque los mensajes en sí no se puedan decodificar en ese caso. En el modelo de pitidos , los nodos solo pueden distinguir entre silencio o al menos un mensaje a través de la detección de portadora .
Los tiempos de ejecución conocidos para redes de un solo salto varían desde una constante (esperada 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 aproximadamente de O((D+ log n)(log 2 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) a O(n log 3/2 n (log log n) 0,5 ) rondas (determinista y sin detección de colisiones).
{{cite journal}}
: CS1 maint: multiple names: authors list (link){{cite journal}}
: CS1 maint: multiple names: authors list (link){{cite book}}
: |journal=
ignorado ( ayuda )