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 informática distribuida .

el algoritmo

El algoritmo supone 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 el sentido de las agujas del reloj. El algoritmo de 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 advierte 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.
3. Cada vez que un proceso envía o reenvía un mensaje electoral , el proceso también se marca a sí mismo 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 electoral es mayor, el proceso reenvía incondicionalmente el mensaje electoral en el sentido de las agujas del reloj.
   2. Si el UID en el mensaje de elección es más pequeño 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 en el mensaje de elección es más pequeño y el proceso ya es un participante (es decir, el proceso ya envió un mensaje de elección con un UID al menos tan grande como su propio UID), el proceso descarta el mensaje de elección.
   4. 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.

1. El proceso líder se marca como no participante y envía un mensaje electo a su vecino anunciando su elección y la 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 cambios.
3. Cuando el mensaje elegido llega al líder recién elegido, éste lo descarta y la elección termina.

Suponiendo que no haya fallas, este algoritmo finalizará. El algoritmo funciona para cualquier número de procesos N y no requiere que ningún proceso sepa cuántos procesos hay en el anillo.

Propiedades

El algoritmo respeta la seguridad : un proceso recibirá un mensaje elegido con su propio UID sólo si su UID es mayor que el de los demás, y sólo cuando todos los procesos estén de acuerdo en el mismo UID. El algoritmo también respeta la vivacidad . 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 ganador.

Cuando hay un único 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 inmediatamente al que tiene el mayor UID: se necesitan N-1 mensajes para que el mensaje de la elección llegue, 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. La tolerancia a fallos se puede aumentar si cada proceso conoce la topología completa, introduciendo mensajes ACK y omitiendo nodos defectuosos al enviar mensajes.

Ver también

• Computación distribuída
• Elección de líder
• Algoritmo de matón
• algoritmo HS

Referencias

1. Ernesto Chang; Rosemary Roberts (1979), "Un algoritmo mejorado para la búsqueda de extremos descentralizados en configuraciones circulares de procesos", Communications of the ACM , 22 (5), ACM: 281–283, doi : 10.1145/359104.359108{{citation}}: Mantenimiento CS1: varios nombres: lista de autores ( enlace )