El algoritmo de Chang y Roberts [1] es un algoritmo de elección de coordinador basado en anillos , empleado en computación 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 hasta el 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 anillo está marcado como no participante .
- Un proceso que detecta la falta de un líder inicia una elección. Crea un mensaje de elección que contiene su UID y 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 de elección , 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 de elección es mayor, el proceso reenvía incondicionalmente el mensaje de elección 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 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.
- 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 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, comienza la segunda etapa del algoritmo.
- El proceso líder se marca a sí mismo como no participante y envía un mensaje elegido a su vecino anunciando su elección y UID.
- Cuando un proceso recibe un mensaje elegido , se marca 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, éste descarta ese mensaje y la elección termina.
Suponiendo que no haya fallos, este algoritmo finalizará. El algoritmo funciona para cualquier cantidad 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 solo si su UID es mayor que el de los demás, y solo cuando todos los procesos estén de acuerdo en el mismo UID. El algoritmo también respeta la vitalidad . Se utilizan los estados "participante" y "no participante" para que, cuando varios procesos inicien una elección aproximadamente al mismo tiempo, solo se anuncie un único ganador.
Cuando hay un único proceso que inicia la elección, el algoritmo requiere 3N-1 mensajes secuenciales, en el peor de los casos. El peor de los casos es cuando el proceso que inicia la elección es el siguiente al que tiene el UID más grande: se necesitan N-1 mensajes para que le llegue el mensaje de elección, luego N mensajes para que recupere su propio UID, luego otros N mensajes para enviar a todos los que están en el anillo el mensaje de elección.
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 los nodos defectuosos al enviar mensajes.
Véase también
Referencias
- ^ Ernest Chang; Rosemary Roberts (1979), "Un algoritmo mejorado para la búsqueda descentralizada de extremos en configuraciones circulares de procesos", Communications of the ACM , 22 (5), ACM: 281–283, doi : 10.1145/359104.359108
{{citation}}: CS1 maint: varios nombres: lista de autores ( enlace )
