stringtranslate.com

Elección de líder

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]

Definición

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:

  1. Los estados de los procesadores se dividen en estados electos y no electos. Una vez electo, permanece como electo (de manera similar si no es electo).
  2. En cada ejecución, exactamente un procesador es elegido y el resto determina que no es elegido.

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

  1. Terminación : el algoritmo debe terminar en un tiempo finito una vez que se selecciona al líder. En los enfoques aleatorios, esta condición a veces se debilita (por ejemplo, se requiere la terminación con probabilidad 1).
  2. Singularidad : 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]

Algoritmos

Elección de líder en anillos

Topología de red en anillo

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).

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 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]

Lema : después de la ronda de ejecución admisible de A en R, todos los procesos tienen los mismos estados.

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.

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

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).

Anillo asincrónico[3]
Algoritmo O(nlogn) para anillo asincrónico

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 .

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, 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]

Algoritmo uniforme

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]

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 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.

Elección de líder en una malla

Topología de red en malla. Los nodos rojos indican las 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 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]

  1. Proceso de activación : 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 iniciador, simplemente reenvía los mensajes a los demás nodos. En esta etapa se envían como máximo 10 mensajes.
  2. Proceso electoral : la elección en el anillo exterior consta de dos etapas como máximo con mensajes.
  3. Terminación : el líder envía un mensaje de terminación a todos los nodos. Esto requiere un máximo de 2n mensajes.

La complejidad del mensaje es como máximo , y si la malla tiene forma cuadrada, .

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 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.

Toro

Estructura de red toroidal.

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]

Elecciones en hipercubos

Topología de red de hipercubo H_4.

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]

Elecciones 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 complejidad de mensajes y espacio O(n). [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 del inicio.
  3. Candidato: el estado de los nodos después de activarse. Los nodos candidatos se considerarán 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 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]

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

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]

Gritar

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.

Megafusión

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.

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 de origen, d) Fase -YO enviando respuestas desde los sumideros, 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 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-

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

-yo

  1. Un sumidero 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 solo un NO, envía NO a todos.
  3. Una fuente espera hasta recibir todos los votos. Si todos son SÍ, sobrevive y si no, ya no es candidata.
  4. Cuando un nodo x envía NO a un nodo vecino y, la dirección lógica de ese borde se invierte.
  5. Cuando un nodo y recibe NO de un vecino externo, invierte la dirección de ese enlace.

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.

  1. Si un fregadero es de hojas, entonces no sirve y por lo tanto se elimina.
  2. Si en la fase YO un nodo recibe el mismo valor de más de un vecino, solicitará a todos menos uno que eliminen el enlace que los conecta.

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.

Aplicaciones

Redes de radio

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.

Modelos y tiempo de ejecución

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).

Véase también

Referencias

  1. ^ RG Gallager , PA Humblet y PM Spira (enero de 1983). "Un algoritmo distribuido para árboles de expansión de peso mínimo" (PDF) . ACM Transactions on Programming Languages ​​and Systems . 5 (1): 66–77. doi :10.1145/357195.357200. S2CID  2758285. Archivado desde el original (PDF) el 2016-10-12 . Consultado el 2007-09-30 .{{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". ACM Transactions on Programming Languages ​​and Systems . 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. ^ abcdef 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íderes en círculos 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, "Ruptura 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, en espacio constante y autoestabilizadora en anillos uniformes", en Proc. 9th Workshop on Distributed Algorithms , vol. 972, págs. 288-302.
  10. ^ J. Burns y J. Pachl, 1989, "Anillos autoestabilizadores uniformes", ACM Trans. Program. Lang. Systems , vol. 11, número 2, págs. 330-344
  11. ^ T. Herman, 1990, "Autoestabilización probabilística", Inf. Process. Lett. , 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 autoestabilizadora en redes de agentes anónimos de estado finito", en Proc. 10th Conf. on Principles of Distributed Systems , 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 de extremos descentralizados en configuraciones circulares de procesadores", ACM , vol. 23, número 11, págs. 627-628.
  16. ^ abcde N. Santoro, Diseño y análisis de algoritmos distribuidos , Wiley, 2006.
  17. ^ H. Kallasjoki, 2007, "Elección en redes en malla, en cubo y completas", Seminario sobre informática teórica .
  18. ^ M. Refai, A. Sharieh y . Alsmmari, 2010, "Algoritmo de elección de líder en red toroidal 2D con presencia de falla de un enlace", The International Arab Journal of Information Technology , vol. 7, n.º 2.
  19. ^ M Al Refai, 2014, "Algoritmo de elección de líder dinámico en una red toroidal 2D con falla de enlaces múltiples", IJCST , vol. 2, número 5.
  20. ^ ab J. Villadangos, A. Cordoba, F. Farina, y M. Prieto, 2005, "Elección eficiente de líderes en redes completas", PDP , pp.136-143.
  21. ^ ab Castillo, Maria, et al. "Un algoritmo de elección de líder O(n) modificado para redes completas". 15.ª 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 . pp. 748–766. arXiv : 1210.8439 . doi :10.1137/1.9781611973105.54. ISBN . 978-1-61197-251-1.S2CID 9976342  . {{cite book}}: |journal=ignorado ( ayuda )