El algoritmo de Chang y Roberts [1] es un algoritmo de elección de coordinador basado en anillo , empleado en computación distribuida .
El algoritmo
El algoritmo asume que cada proceso tiene una identificación única (UID) y que los procesos pueden organizarse en un anillo unidireccional con un canal de comunicación que va de cada proceso al vecino en el sentido de las agujas del reloj. El algoritmo de dos partes se puede describir de la siguiente manera:
- Inicialmente, cada proceso en el ring se marca como no participante .
- Un proceso que advierte la falta de líder inicia una elección. Crea un mensaje electoral que contiene su UID. Luego envía este mensaje en el sentido de las agujas del reloj a su vecino.
- Cada vez que un proceso envía o reenvía un mensaje electoral , el proceso también se marca como participante.
- Cuando un proceso recibe un mensaje de elección , compara el UID del mensaje con su propio UID.
- Si el UID en el mensaje electoral es mayor, el proceso reenvía incondicionalmente el mensaje electoral en el sentido de las agujas del reloj.
- Si el UID en el mensaje de elección es más pequeño y el proceso aún no es un participante, el proceso reemplaza el UID en el mensaje con su propio UID, envía el mensaje de elección actualizado en el sentido de las agujas del reloj.
- Si el UID en el mensaje de elección es más pequeño y el proceso ya es un participante (es decir, el proceso ya ha enviado un mensaje de elección con un UID al menos tan grande como su propio UID), el proceso descarta el mensaje de elección.
- Si el UID en el mensaje electoral entrante es el mismo que el UID del proceso, ese proceso comienza a actuar como líder.
Cuando un proceso comienza a actuar como líder, comienza la segunda etapa del algoritmo.
- El proceso líder se marca a sí mismo como no participante y envía un mensaje electo a su vecino anunciando su elección y UID.
- Cuando un proceso recibe un mensaje elegido , se marca a sí mismo como no participante , registra el UID elegido y reenvía el mensaje elegido sin cambios.
- Cuando el mensaje elegido llega al líder recién elegido, el líder descarta ese mensaje y la elección termina.
Suponiendo que no haya fallas, este algoritmo terminará. El algoritmo funciona para cualquier número de procesos N y no requiere ningún proceso para saber cuántos procesos hay en el anillo.
Propiedades
El algoritmo respeta la seguridad : un proceso recibirá un mensaje elegido con su propio UID solo si su UID es mayor que el de los demás, y solo cuando todos los procesos coincidan en el mismo UID. El algoritmo también respeta la vitalidad . Los estados "participante" y "no participante" se utilizan para que cuando varios procesos inicien una elección aproximadamente al mismo tiempo, solo se anuncie un único ganador.
Cuando hay un solo proceso que inicia la elección, el algoritmo requiere mensajes secuenciales 3N-1, en el peor de los casos. El peor de los casos es cuando el proceso que inicia la elección es el siguiente inmediato al que tiene el mayor UID: se necesitan N-1 mensajes para que el mensaje de la elección llegue a él, luego N mensajes para que recupere su propio UID, luego otros N mensajes para enviar a todos en el ring el mensaje elegido.
Este algoritmo no es muy tolerante a fallos. Se puede aumentar la tolerancia a fallas si cada proceso conoce la topología completa, al introducir mensajes ACK y omitir los nodos defectuosos al enviar mensajes.
Ver también
Referencias
- ^ Ernest Chang; Rosemary Roberts (1979), "Un algoritmo mejorado para la búsqueda descentralizada de extremos en configuraciones circulares de procesos" , Comunicaciones del ACM , ACM, 22 (5): 281-283, doi : 10.1145 / 359104.359108CS1 maint: varios nombres: lista de autores ( enlace )