Algoritmo de Chang y Roberts

El algoritmo de Chang y Roberts ^{[ 1 ]} es un algoritmo de elección de coordinador basado en anillos , empleado en computación distribuida . Fue publicado inicialmente por Ernest Chang y Rosemary Roberts en 1979.

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 desde cada proceso al vecino en sentido horario. El algoritmo, dividido en dos partes, se puede describir de la siguiente manera:

1. Inicialmente, cada proceso en el anillo se marca como no participante .
2. Un proceso que detecta la falta de un 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.
3. Cada vez que un proceso envía o reenvía un mensaje electoral , también se identifica como participante.
4. Cuando un proceso recibe un mensaje de elección , compara el UID del mensaje con su propio UID.
   1. Si el UID en el mensaje de elección es mayor, el proceso reenvía incondicionalmente el mensaje de elección en el sentido de las agujas del reloj.
   2. Si el UID en el mensaje de elección es menor y el proceso aún no es participante, el proceso reemplaza el UID en el mensaje con su propio UID y envía el mensaje de elección actualizado en el sentido de las agujas del reloj.
   3. Si el UID del mensaje electoral es menor y el proceso ya participa (es decir, el proceso ya ha enviado un mensaje electoral con un UID al menos tan grande como su propio UID), el proceso descarta el mensaje electoral.
   4. Si el UID del mensaje de elección 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, inicia la segunda etapa del algoritmo.

1. El proceso de liderazgo se marca a sí mismo como no participante y envía un mensaje electo a su vecino anunciando su elección y UID.
2. 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 modificaciones.
3. Cuando el mensaje del electorado llega al líder recién electo, este lo descarta y la elección termina.

Si no se producen fallos, este algoritmo finalizará. Funciona para cualquier número de procesos N y no requiere que ningún proceso sepa cuántos procesos hay en el anillo.

El algoritmo respeta la seguridad : un proceso recibirá un mensaje de elección 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 vivacidad . Se utilizan los estados "participante" y "no participante" para que, cuando varios procesos inicien una elección casi simultáneamente, solo se anuncie un único ganador.

Cuando un único proceso inicia la elección, el algoritmo requiere 3N-1 mensajes secuenciales, en el peor de los casos. El peor caso se da cuando el proceso que inicia la elección es el siguiente inmediatamente al que tiene el UID más alto: se necesitan N-1 mensajes para que el mensaje de elección le llegue, luego N mensajes para que recupere su propio UID, y otros N mensajes para enviar el mensaje de elección a todos los demás procesos del anillo.

Este algoritmo no es muy tolerante a fallos. La tolerancia a fallos puede mejorarse si cada proceso conoce la topología completa, introduciendo mensajes ACK y omitiendo los nodos defectuosos al enviar mensajes.

• computación distribuida
• Elección del líder
• Algoritmo de acoso
• Algoritmo HS