Algoritmo Chang y Roberts

El algoritmo de Chang y Roberts​ es un algoritmo de elección de líder/coordinador en un conjunto de procesos situados en anillo. Se aplica en sistemas distribuidos.

Historia

En 1977 Le Lann propuso el primer algoritmo para la elección de líder en anillos unidireccionales de procesos.​ Dos años más tarde, en 1979, Chang y Roberts proponen una mejora de ese primer algoritmo con la que logran reducir el número de mensajes generados para la misma tarea. El objetivo de su algoritmo es encontrar el mayor identificador entre el total de los procesos. Consiguen pasar de un orden O(n^2) a un orden de O(n log n) en el caso medio.

Descripción del algoritmo

En el algoritmo se supone que:

1. Los procesos se encuentran en un anillo unidireccional.
2. Cada proceso dispone de un identificador.
3. Cada proceso dispone de un canal que comunica con su proceso vecino en el anillo.
4. Los mensajes viajan a través del anillo en el sentido de las agujas del reloj.

El algoritmo funciona de manera que:

1. Todos los procesos comienzan marcados como no participante.
2. Un proceso detecta la necesidad de elección de un coordinador y debido a esto convoca elecciones.
3. Este primer proceso se marca como participante, crea un mensaje de elección donde especifica su identificador y lo envía a su vecino.
4. Cuando ese mensaje llega a un proceso:
   1. Si el proceso al que llega tiene un identificador mayor que el que se indica en el mensaje:
      1. El mensaje es desechado.
      2. El proceso al que llega crea un mensaje de elección con su identificador y lo envía.
      3. Si el proceso al que llega está marcado como no participante se marca como participante.
   2. Si el proceso al que llega tiene un identificador menos que el que se indica en el mensaje:
      1. El mensaje se reenvía hacia el siguiente proceso en el anillo.
   3. Si el proceso al que llega tiene un identificador igual al que se indica en el mensaje:
      1. El proceso se convierte en el coordinador.
5. Una vez encontrado el proceso de mayor identificador y por tanto el que actuará de coordinador el algoritmo realiza una fase en la que se comunica el elegido al resto de procesos. El proceso coordinador envía un mensaje elegido con su identificador que se difunde a lo largo de todo el anillo, dando una vuelta completa. Así todos los procesos son informados del nuevo coordinador y cuando reciben este mensaje proceden a marcarse como no participante de nuevo.

En el caso peor, donde el proceso que resulta elegido como nuevo coordinador es el vecino anterior al proceso que da comienzo a la elección, se necesitan 3n-1 mensajes para encontrar el identificador mayor y comunicar el resultado de la elección a todos los procesos del anillo.

Escenario inicial: procesos dispuestos en forma de anillo.

Algoritmo Chang y Roberts, primera fase: El proceso 2 convoca elecciones y envía su propio identificador. Si llega a un proceso de identificadores menor el mensaje se desecha, si no, se reenvía. El resto de procesos actúan de igual manera.

Algoritmo Chang y Roberts, segunda fase: El proceso 8 recibe de vuelta su propio mensaje, con su propio identificador.

Algoritmo Chang y Roberts, tercera fase: El proceso 8 envía un mensaje comunicando que el elegido definitivo es él. El mensaje da una vuelta completa al anillo.

Tiempo que emplea

La primera de las mediciones significativas del algoritmo propuesto por Chang y Roberts es el tiempo que se necesita para encontrar el identificador de proceso más alto.

Para el análisis de tiempos se supone un conjunto de n procesos numerados de 1 a n dispuestos en anillo. El paso de mensajes es unidireccional y en el sentido de las agujas del reloj. El mensaje generado por el proceso i será identificado como mensaje i.

1. Caso mejor: El proceso de mayor identificador es el que da comienzo al algoritmo, enviando en un mensaje de elección su propio identificador. Este mensaje daría una vuelta completa al anillo y regresaría al proceso que lo generó. De esta manera en solo una vuelta se habría encontrado al nuevo coordinador en un tiempo O(n).
2. Caso peor: El proceso que está más lejos del proceso de mayor identificador comienza la elección del nuevo coordinador. Teniendo en cuenta la disposición en anillo y el paso de mensajes en el sentido de las agujas del reloj, este proceso sería el vecino del proceso que acabaría siendo elegido coordinador. En este caso el tiempo necesario para que un mensaje de elección llegue hasta el proceso de mayor identificador sería de O(n-1) y el tiempo necesario para que el mensaje del proceso de mayor identificador se propague por todo el anillo sería de O(n) lo que haría un tiempo total de O(2n-1).

Intercambios de mensajes

La segunda medición sustancial en el algoritmo es el número de intercambios de mensajes.

1. Caso mejor: Los procesos están ordenados según su identificador en el sentido de las agujas del reloj de manera creciente. Los mensajes generados por los procesos 1 al n-1 son enviados una sola vez pues al pasarse llegan a un proceso de identificador mayor y este los deshecha. Esto haría un total de n-1 intercambios. El mensaje generado por el proceso n, en este caso el de mayor identificador, se intercambiará n veces, una por cada proceso ya que ninguno lo desechará. Este mensaje dará una vuelta completa al anillo, resultando en n pasos de mensaje. El total sería de 2n – 1 pasos de mensajes.
2. Caso peor: Los procesos están ordenados según su identificador en el sentido de las agujas del reloj de manera decreciente:

• El mensaje del proceso de mayor identificador será pasado al siguiente n veces pues da una vuelta completa al anillo.

• El mensaje del proceso con el segundo mayor identificador será pasado por el anillo hasta encontrar un proceso de identificador mayor, es decir n-1 veces.
• El mensaje del proceso con el tercer mayor identificador será pasado por el anillo hasta encontrar un proceso de identificador mayor, es decir n-2 veces.
• Ocurrirá esto de manera sucesiva con los mensajes generados por los procesos n-1 a 1
• El mensaje del proceso 1 solo será intercambiado 1 vez el primer proceso con al que llega ya tiene un identificador mayor.

Total: (n + (n-1) + (n-2) + … + 1) = (n(n+1))/2, es decir O(n^2).

Características

• Seguridad: garantiza la detección del identificador de mayor valor en el anillo.
• Viveza: todos los procesos del anillo tienen conocimiento del líder.

Referencias

• Datos: Q1256877