Elección de líder

En informática 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 comience la tarea, 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 ejecutar un algoritmo de elección de líder, cada nodo de la red reconoce a un nodo particular y único como líder de la tarea.

Los nodos de la red se comunican entre sí para decidir cuál de ellos pasará al estado "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, entonces 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 a menudo se atribuye a LeLann, quien lo formalizó como un método para crear un nuevo token en una red 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 bytes totales transmitidos y tiempo. El algoritmo sugerido por Gallager, Humblet y Spira ^[1] para gráficos 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 gráficos de red , como anillos no dirigidos, anillos unidireccionales, gráficos completos, cuadrículas, gráficos de Euler dirigidos y otros. Korach, Kutten y Moran sugirieron un método general que desacopla la cuestión de la familia de gráficos del diseño del algoritmo de elección de líder . ^[2]

Definición

El problema de la elección del líder es que cada procesador decide eventualmente 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:

1. Los estados de procesadores se dividen en estados electos y no electos. Una vez elegido, permanece como elegido (lo mismo ocurre si no es elegido).
2. En cada ejecución, exactamente un procesador resulta elegido y el resto determina que no son elegidos.

Un algoritmo de elección de líder válido debe cumplir las siguientes condiciones: ^[4]

1. Terminación : el algoritmo debe finalizar en un tiempo finito una vez que se selecciona el líder. En los enfoques aleatorios, esta condición a veces se debilita (por ejemplo, se requiere la terminación con probabilidad 1).
2. Unicidad : hay exactamente un procesador que se considera líder.
3. Acuerdo : todos los demás procesadores saben quién es el líder.

Un algoritmo para la elección de líder puede variar en los siguientes aspectos: ^[5]

• Mecanismo de comunicación: los procesadores son síncronos, en los que los procesos se sincronizan mediante una señal de reloj, o asíncronos , donde los procesos se ejecutan a velocidades arbitrarias.
• Nombres de procesos: si los procesos tienen una identidad única o son indistinguibles (anónimos).
• Topología de red: por ejemplo, anillo , gráfico acíclico o gráfico completo .
• Tamaño de la red: el algoritmo puede o no utilizar el conocimiento de la cantidad de procesos en el sistema.

Algoritmos

Elección de líder en anillos

Topología de red en anillo

Una red en anillo es una topología de gráfico conectado en la que cada nodo está exactamente conectado a otros dos nodos, es decir, para un gráfico 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 puede enviar mensajes a la izquierda o solo a la derecha), o bidireccional, lo que significa que los procesadores pueden transmitir y recibir mensajes en ambas direcciones (un nodo puede enviar mensajes a izquierda y derecha).

Anillos anónimos

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 sólo depende del estado inicial de los nodos vecinos. Entonces, debido a que 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 líder, también lo serán todos los demás.

Para simplificar, aquí hay una prueba en anillos sincrónicos anónimos. Es una prueba por contradicción. Considere 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 de ejecución admisible de A en R, todos los procesos tienen los mismos estados. ${\displaystyle k}$

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

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

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

Paso inductivo: en 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 , permanecen en el mismo estado después de la ronda . ${\displaystyle k}$ ${\displaystyle m_{r}}$ ${\displaystyle m_{l}}$ ${\displaystyle k-1}$ ${\displaystyle m_{r}}$ ${\displaystyle m_{l}}$ ${\displaystyle k}$ ${\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.

Elección aleatoria (probabilística) de líder

Un enfoque común para resolver el problema de la elección de líderes en círculos 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).

Anillo asíncrono ^[3]

Algoritmo O (nlogn) para anillo asíncrono

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

En el algoritmo, cada proceso envía un mensaje hacia el borde izquierdo. Luego espera hasta que llegue un mensaje del borde derecho. Si el contenido del mensaje es mayor que el suyo , reenvía el mensaje al borde izquierdo; de lo contrario ignora el mensaje y no hace nada. Si el mensaje es igual al suyo , envía un mensaje a la izquierda anunciando que soy elegido. Otros procesos adelantan la convocatoria a la izquierda y se vuelcan hacia los no electos. Está claro que el límite superior es para este algoritmo. ${\displaystyle O(n^{2})}$ ${\displaystyle id}$ ${\displaystyle id}$ ${\displaystyle id}$ ${\displaystyle id}$ ${\displaystyle id}$ ${\displaystyle O(n^{2})}$

En el algoritmo, se ejecuta en fases. En la decima fase, un proceso determinará si es el ganador entre los vecinos del lado izquierdo y del lado derecho . Si resulta ganador, el proceso puede pasar a la siguiente fase. En la fase , cada proceso necesita determinar si es ganador o no enviando un mensaje a sus vecinos izquierdo y derecho (los vecinos no reenvían el mensaje). El vecino responde un solo si el mensaje es más grande que el del vecino ; de lo contrario, responde un . Si recibe dos s, uno de la izquierda y otro de la derecha, entonces es el ganador de la fase . En fase , los ganadores en fase deben enviar un mensaje a sus vecinos izquierdo y derecho. Si los vecinos en la ruta reciben el mensaje más grande que su , reenvíe el mensaje al siguiente vecino; de lo contrario, responda un . Si el enésimo vecino recibe el mayor que el suyo , envía de vuelta un ; de lo contrario, responde un . Si el proceso recibe dos s, entonces es el ganador de la fase . En la última fase, el ganador final recibirá el suyo en el mensaje, luego finalizará y enviará un mensaje de finalización a los demás procesos. En el peor de los casos, en cada fase hay como máximo ganadores, donde está el número de fase. Hay fases en total. Cada ganador envía en el orden de mensajes en cada fase. Entonces, la complejidad de los mensajes es . ${\displaystyle O(n\log n)}$ ${\displaystyle k}$ ${\displaystyle 2^{k}}$ ${\displaystyle 2^{k}}$ ${\displaystyle 0}$ ${\displaystyle P}$ ${\displaystyle id}$ ${\displaystyle ACK}$ ${\displaystyle id}$ ${\displaystyle id}$ ${\displaystyle ACK_{fault}}$ ${\displaystyle P}$ ${\displaystyle ACK}$ ${\displaystyle P}$ ${\displaystyle 0}$ ${\displaystyle k}$ ${\displaystyle k-1}$ ${\displaystyle id}$ ${\displaystyle 2^{k}}$ ${\displaystyle 2^{k}}$ ${\displaystyle id}$ ${\displaystyle id}$ ${\displaystyle ACK_{fault}}$ ${\displaystyle 2^{k}}$ ${\displaystyle id}$ ${\displaystyle id}$ ${\displaystyle ACK}$ ${\displaystyle ACK_{fault}}$ ${\displaystyle ACK}$ ${\displaystyle k}$ ${\displaystyle id}$ ${\displaystyle {\frac {n}{2^{k}+1}}}$ ${\displaystyle k}$ ${\displaystyle \lceil \log(n-1)\rceil }$ ${\displaystyle 2^{k}}$ ${\displaystyle O(n\log n)}$

Anillo sincrónico

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, pase a la siguiente fase. El algoritmo comprobará si hay un número de fase igual a un proceso y luego realizará los mismos pasos que la fase . Al final de la ejecución, el mínimo será elegido líder. Usó exactamente mensajes y rondas. ${\displaystyle O(n)}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle 0}$ ${\displaystyle id=0}$ ${\displaystyle 0}$ ${\displaystyle n}$ ${\displaystyle id}$ ${\displaystyle 0}$ ${\displaystyle id}$ ${\displaystyle n}$ ${\displaystyle n(minimum\_id+1)}$

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, están activos a≤n procesadores. Cada procesador decide con una probabilidad de a^(-1) si desea convertirse 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 líder. Para determinar el valor de c, cada candidato envía una ficha (guijarro) al inicio de la fase que pasa alrededor del anillo y regresa después de exactamente n unidades de tiempo a su remitente. Cada procesador determina c contando el número de piedras 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 interbloqueos 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]

Algoritmo uniforme

En 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 pudo 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 el llamado oráculo líder Ω? que cada procesador puede preguntar si existe un líder único. Muestran que, desde algún punto hacia arriba, se garantiza que se devolverá la misma respuesta a todos los procesos. ^[13]

Anillos con identificaciones únicas

En uno de los primeros trabajos, Chang y Roberts ^[14] propusieron un algoritmo uniforme en el que se selecciona como líder el procesador con el ID más alto. Cada procesador envía su ID en el sentido de las agujas del reloj. Un proceso recibe un mensaje y lo compara con el suyo propio. Si es más grande lo pasa, en caso contrario descartará el mensaje. Muestran que este algoritmo utiliza en la mayoría de los mensajes y en el caso medio. Hirschberg y Sinclair ^[15] mejoraron este algoritmo con complejidad de mensajes al introducir un esquema de paso de mensajes bidireccional que permite a los procesadores enviar mensajes en ambas direcciones. ${\displaystyle O(n^{2})}$ ${\displaystyle O(n\log n)}$
${\displaystyle O(n\log n)}$

Elección de líder en una malla

Topología de red en malla. Los nodos rojos indican esquinas, el borde azul y el interior gris.

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.

Malla no orientada

Un algoritmo típico para resolver la elección del líder en una malla no orientada es elegir solo uno de los cuatro nodos de las esquinas como líder. Dado que es posible que los nodos de las esquinas no sean conscientes del estado de otros procesos, el algoritmo debe despertar primero a los nodos de las esquinas. Un líder puede ser elegido de la siguiente manera. ^[17]

1. Proceso de despertar : en el que 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 otros nodos. En esta etapa se envían como máximo los mensajes. ${\displaystyle k}$ ${\displaystyle 3n+k}$
2. Proceso electoral : la elección en el anillo exterior consta de dos etapas como máximo con mensajes. ${\displaystyle 6(a+b)-16}$
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 , y si la malla tiene forma cuadrada, . ${\displaystyle 6(a+b)-16}$ ${\displaystyle O({\sqrt {n}})}$

Malla orientada

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 de líder en una malla orientada es trivial. Sólo necesitamos designar una esquina, por ejemplo "norte" y "este", y asegurarnos de que el nodo sepa que es un líder.

Toro

Estructura de la red Torus.

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. Una forma de elegir a un líder en una estructura de este tipo se conoce como etapas electorales. De manera similar a los procedimientos en estructuras en anillo, este método en cada etapa elimina candidatos potenciales hasta que finalmente queda un nodo candidato. Este nodo se convierte en líder y luego notifica la terminación a todos los demás procesos. ^[16] Este enfoque se puede utilizar para lograr una complejidad de O(n). También se introdujeron enfoques más prácticos para abordar la presencia de enlaces defectuosos en la red. ^{[18] [19]}

Elección en hipercubos

Topología de red de hipercubo H_4.

Un hipercubo es una red que consta de nodos, cada uno con un grado y aristas. Se pueden utilizar etapas electorales similares a las anteriores para resolver el problema de la elección de líderes. En cada etapa compiten dos nodos (llamados duelistas) y el ganador asciende a la siguiente etapa. Esto significa que en cada etapa sólo la mitad de los duelistas pasan a la siguiente etapa. Este procedimiento continúa hasta que sólo 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 mayor de . ^[dieciséis] ${\displaystyle H_{k}}$ ${\displaystyle n=2^{k}}$ ${\displaystyle k}$ ${\displaystyle O(n\log n)}$ ${\displaystyle O(n)}$ ${\displaystyle O(n\log \log n)}$

Elección en redes completas

Estructura de red completa.

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 mensaje O(n) y complejidad espacial. ^[20] En este algoritmo, los procesos tienen los siguientes estados:

1. Dummy: nodos que no participan en el algoritmo de elección de líder.
2. Pasivo: el estado inicial de los procesos antes de su inicio.
3. Candidato: el estado de los nodos después de despertar. Los nodos candidatos serán considerados líderes.

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 llama vecino, ^[20] y cada nodo sea conocido. por otro. ^[21]

Todos los procesadores comienzan inicialmente en un estado pasivo hasta que se activan. Una vez que los nodos están despiertos, son candidatos a convertirse en líderes. Según un esquema de prioridades, los nodos candidatos colaboran en el anillo virtual. En algún momento, los candidatos toman conciencia de la identidad de los candidatos que les preceden en el ring. Los candidatos de mayor prioridad preguntan a los de menor prioridad sobre sus predecesores. Los candidatos con menor prioridad se convierten en tontos después de responder a los candidatos con mayor prioridad. Según este esquema, el candidato de mayor prioridad finalmente sabe que todos los nodos del sistema son ficticios excepto él mismo, momento en el que sabe que es el líder.

El algoritmo anterior no es correcto; necesita más mejoras. ^[21]

Técnicas universales de elección de líderes.

Como su nombre lo indica, estos algoritmos están diseñados para usarse en todo tipo de redes de procesos sin ningún conocimiento previo de la topología de una red o sus propiedades, como su tamaño. ^[dieciséis]

Gritar

Shout (protocolo) construye un árbol de expansión en un gráfico genérico y elige su raíz como líder. El algoritmo tiene un coste total lineal en la cardinalidad de las aristas.

Megafusión

En esencia, 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 líder. La idea básica de este método 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 ciclo) cuya raíz es la 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. ${\displaystyle O(m+n\log n)}$

Yoyó

Un ejemplo de procedimiento YO-YO. a) La red, b) Red orientada después de la fase de configuración , c) Fase YO- en la que se pasan los valores fuente, d) Fase -YO que envía respuestas desde los receptores, e) estructura actualizada después de la fase -YO.

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 bordes incidentes. Por ejemplo, si el nodo x tiene una identificación menor que y, x se orienta hacia y. Si un nodo tiene una identificación más pequeña que todos sus vecinos, se convierte en una fuente . Por el contrario, un nodo con todos los bordes internos (es decir, con una identificación mayor que todos sus vecinos) es un sumidero . Todos los demás nodos son nodos internos .
Una vez que todos los bordes están orientados, comienza la fase de iteración . Cada iteración es una etapa electoral en la que algunos candidatos serán eliminados. Cada iteración tiene dos fases: YO- y –YO . En esta fase, las fuentes inician 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ínimos locales) transmite su valor a todos sus vecinos
2. Un nodo interno espera recibir un valor de todos sus vecinos internos. Calcula el mínimo y lo envía al vecino.
3. Un sumidero (un nodo sin borde de salida) 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 vecinos de los que recibió el valor más pequeño y NO a los demás. Si recibe sólo un NO, envía NO a todos.
3. Una fuente espera hasta recibir todos los votos. Si todo es SÍ, sobrevive y si no, ya no es candidato.
4. Cuando un nodo x envía NO a un vecino y, la dirección lógica de ese borde se invierte.
5. Cuando un nodo y recibe NO de un vecino, invierte la dirección de ese enlace.

Después de la etapa final, cualquier fuente que reciba 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.

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

Este método tiene un costo total de mensajes O(mlogn). La complejidad real del mensaje, incluida la poda, es un problema de investigación abierto y se desconoce.

Aplicaciones

Redes de radio

En los protocolos de redes de radio, la elección del líder se utiliza a menudo como primer paso para abordar primitivas de comunicación más avanzadas, como la recopilación de mensajes o las transmisiones. ^[22] La propia naturaleza de las redes inalámbricas induce colisiones cuando nodos adyacentes transmiten al mismo tiempo; elegir un líder permite coordinar mejor este proceso. Mientras que 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.

Modelos y tiempo de ejecución

En las redes de radio, los n nodos pueden elegir en cada ronda entre transmitir o recibir un mensaje. Si no hay detección de colisiones disponible, entonces un nodo no puede distinguir entre silencio o recibir más de un mensaje a la vez. Si la detección de colisiones está disponible, entonces un nodo puede detectar más de un mensaje entrante al mismo tiempo, aunque los mensajes en sí no puedan descodificarse en ese caso. En el modelo de pitido , los nodos sólo pueden distinguir entre silencio o al menos un mensaje mediante detección de portadora .

Los tiempos de ejecución conocidos para redes de un solo salto varían desde rondas constantes (esperadas con detección de colisiones) hasta rondas O (n log n) (deterministas 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 ² 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 colisión) a O(n log ^3/2 n (log log n) ^0,5 ) rondas (determinista y sin detección de colisión).

Ver también

• Computación distribuida § Elección
• Algoritmo de matón
• Algoritmo de Chang y Roberts
• algoritmo HS
• Sistema de votación

Referencias

1. RG Gallager , PA Humblet y PM Spira (enero de 1983). "Un algoritmo distribuido para árboles de extensión de peso mínimo" (PDF) . Transacciones ACM sobre lenguajes y sistemas de programación . 5 (1): 66–77. doi :10.1145/357195.357200. S2CID  2758285. Archivado desde el original (PDF) el 12 de octubre de 2016 . Consultado el 30 de septiembre de 2007 .{{cite journal}}: CS1 maint: multiple names: authors list (link)
2. Ephraim Korach, Shay Kutten, Shlomo Moran (1990). "Una técnica modular para el diseño de algoritmos eficientes de búsqueda de líderes distribuidos". Transacciones ACM sobre lenguajes y sistemas de programación . 12 (1): 84-101. CiteSeerX 10.1.1.139.7342 . doi :10.1145/77606.77610. S2CID  9175968. {{cite journal}}: CS1 maint: multiple names: authors list (link)
3. H. Attiya y J. Welch, Computación distribuida: fundamentos, simulaciones y temas avanzados , John Wiley & Sons Inc., 2004, cap. 3
4. I. Gupta, R. van Renesse y KP Birman, 2000, Un protocolo de elección de líder probabilísticamente correcto para grupos grandes, Informe técnico , Universidad de Cornell
5. R. Bakhshi, W. Fokkink, J. pang y J. Van de Pol, c2008 "Elección de líder en anillos anónimos: Franklin se vuelve probabilístico", TCS , vol. 273, págs. 57-72.
6. H. Attiya y M. Snir, 1988, "Computación en un anillo anónimo", JACM , vol. 35, número. 4, págs. 845-875
7. A. Itai y M. Rodeh, 1990, "Rotura de simetría en redes distribuidas", vol. 88, número 1, págs. 60-87.
8. L. Higham y S. Myers, 1998, "Circulación de tokens autoestabilizadores en anillos de paso de mensajes anónimos", Segunda conferencia internacional sobre principios de sistemas distribuidos .
9. G. Itkis, C. Lin y J. Simon, 1995, "Elección de líder determinista, de espacio constante y autoestabilizadora en anillos uniformes", en Proc. Noveno Taller sobre Algoritmos Distribuidos , vol. 972, págs. 288-302.
10. J. Burns y J. Pachl, 1989, "Anillos autoestabilizadores uniformes", ACM Trans. Programa. Lang. Sistemas , vol. 11, edición. 2, págs.330-344
11. T. Herman, 1990, "Autoestabilización probabilística", Inf. Proceso. Letón. , vol. 35, número 2, págs.63-67.
12. G. Tel, Introducción a los algoritmos distribuidos . Cambridge University Press, 2000, segunda edición
13. M. Fischer y H. Jiang, 2006, "Elección de líder autoestabilizador en redes de agentes anónimos del estado finito", en Proc. Décima Conferencia. sobre principios de sistemas distribuidos , vol. 4305, págs. 395-409.
14. E. Chang y R. Roberts, 1979, "Un algoritmo mejorado para la búsqueda de extremos descentralizados en configuraciones circulares de procesos", ACM , vol. 22, número 5, págs. 281-283.
15. DS Hirschberg y JB Sinclair, 1980, "Búsqueda extrema descentralizada en configuraciones circulares de procesadores", ACM , vol. 23, número 11, págs. 627-628.
16. N. Santoro, Diseño y análisis de algoritmos distribuidos , Wiley, 2006.
17. H. Kallasjoki, 2007, "Elección en malla, cubo y redes completas", Seminario de Informática Teórica .
18. M. Refai, A. Sharieh y. Alsmmari, 2010, "Algoritmo de elección de líder en una red Torus 2D con presencia de falla en un enlace", Revista Árabe Internacional de Tecnología de la Información , vol. 7, núm. 2.
19. M Al Refai, 2014, "Algoritmo de elección de líder dinámico en una red Torus 2D con falla de enlaces múltiples", IJCST , vol. 2, número 5.
20. J. Villadangos, A. Córdoba, F. Farina y M. Prieto, 2005, "Elección de líder eficiente en redes completas", PDP , págs.136-143.
21. Castillo, María, et al. "Un algoritmo de elección de líder O(n) modificado para redes completas". XV Conferencia Internacional EUROMICRO sobre Procesamiento Paralelo, Distribuido y Basado en Red (PDP'07). IEEE, 2007.
22. Haeupler, Bernhard; Ghaffari, Mohsen (2013). "Elección de líder casi óptima en redes de radio de múltiples saltos" . págs. 748–766. arXiv : 1210.8439 . doi :10.1137/1.9781611973105.54. ISBN 978-1-61197-251-1. S2CID  9976342. {{cite book}}: |journal=ignorado ( ayuda )