Elección de líder en anillo

Introducción[editar]

En computación distribuida, la elección de líder es el procedimiento de designar un solo proceso como el organizador de una tarea distribuida entre varios ordenadores (nodos).^[1] Antes de que comience la tarea, todos los nodos de la red, o bien no saben qué nodo va a ser el líder (coordinador), o bien no se pueden comunicar con el coordinador actual. Después de que el algoritmo de elección de líder se haya ejecutado, todos los nodos reconocen a uno de ellos como el líder de la tarea.

Los nodos de la red se comunican entre ellos para decidir quién se convertirá en líder. Para ello, necesitan un método con el que romper la simetría entre ellos. Por ejemplo, si cada nodo tiene un identificador único, entonces los nodos pueden comparar sus identificadores y decidirán que el nodo de mayor identificador será el líder.

Esto resulta útil en las situaciones donde se elige un nuevo servidor si se cae el actual, se elige un nuevo proceso para que entre en una sección crítica, se elige un proceso con menos actividad (para balanceo de carga) o se elige un proceso con la copia más reciente (en caso de replicación).^[2]

Se han propuesto muchos otros algoritmos para diferentes tipos de grafos de tipo red, como anillos indirectos, anillos no direccionales, grafos completos, mallas (grids), grafos de Euler dirigidos y otros. A continuación, se profundiza en los algoritmos para topologías en anillo.

Este algoritmo es bastante senillo, sin embargo, eso no quita que es vulnerable a fallos, ya que en caso de que uno o más nodos fallen durante el proceso de elección, el nodo líder será uno erróneo.

Definición[editar]

El problema de la elección de líder es que cada procesador (nodo) acabe decidiendo si él mismo es el líder o no, sujeto a la condición de que sólo un procesador decide que es el líder (sólo puede haber uno). Se resuelve el problema si los nodos, al terminar el algoritmo, están divididos entre elegidos y no elegidos, y sólo uno se convierte en elegido.

Un algoritmo de elección de líder válido debe cumplir las siguientes condiciones:

Terminación. El algoritmo debe terminar en un tiempo finito una vez el líder haya sido seleccionado.
Unicidad. Sólo hay un nodo que se considera líder.
Acuerdo. Todos los otros procesos saben cuál es el líder.

Un algoritmo de elección de líder puede variar en los siguientes aspectos:

Mecanismo de comunicación: los nodos son, o síncronos (donde los procesos están sincronizados mediante una señal de reloj), o asíncronos (donde los procesos se ejecutan con tiempos arbitrarios).
Nombres de los procesos: los procesos pueden tener un identificador único o ser indistinguibles (anónimos).
Topología de la red: en este caso, en anillo.
Tamaño de la red: el algoritmo puede o no saber el número de procesos que están corriendo en el sistema.

Algoritmos de elección de líder en anillo[editar]

En el algoritmo en anillo, los procesos del sistema se consideran dispuestos en un anillo lógico, aunque no estén físicamente conectados. Pueden tener las siguientes características:

Un anillo puede ser unidireccional, lo que significa que los nodos solo pueden comunicarse en sentido horario o antihorario, o bidireccional, lo que significa que los nodos pueden enviar y recibir mensajes en ambos sentidos.

El número de nodos en el anillo puede ser conocido o desconocido por los procesos; si no lo es, los procesos estarían preparados para trabajar en un anillo de tamaño arbitrario.

Finalmente, los procesos pueden contar con un identificador único (comparables) o no, en cuyo caso se denominan anónimos.^[3]

Líderes anónimos[editar]

Se dice que un anillo es anónimo si todos los procesos son idénticos. No hay un algoritmo determinista para elegir un líder en anillos anónimos, incluso cuando el tamaño de la red es conocido por los procesos, tanto si nos encontramos en un sistema síncrono como asíncrono, o independientemente de si el paso de mensajes es unidireccional o bidireccional. El estado de los nodos, después de varios pasos, solamente depende del estado inicial de los nodos vecinos. Como los estados son idénticos y se ejecutan los mismos procedimientos, cada proceso envía los mismos mensajes en todas las rondas. Por lo tanto, cada estado del proceso también cambia de manera idéntica y por ello, si un nodo es elegido líder, también lo son los otros.

Elección de líder aleatoria (probabilística)[editar]

Una aproximación común para resolver el problema de la elección de líder en anillos anónimos es el uso de algoritmos probabilísticos, donde los nodos asumen algunas identidades basadas en una función probabilística y se la comunican al resto de la red. Al final, mediante la aplicación del algoritmo, hay una alta probabilidad de elegir un líder.

Anillo asíncrono[editar]

Ya que no hay un algoritmo para anillos anónimos, los anillos asíncronos de los que se habla en este apartado serán anillos asíncronos no anónimos, ya que escogen su identificador por probabilidad. Por tanto, consideramos que cada proceso tiene un id único, y no conoce el tamaño del anillo. La elección de líder se puede resolver con dos algoritmos que se diferencian en su eficiencia.

En el algoritmo menos eficiente, cada proceso envía un mensaje con su id al siguiente proceso. Cuando a un proceso le llega un mensaje, si el id contenido es mayor al suyo, lo reenvía en el mismo sentido; si es igual, se convierte en elegido, anunciándoselo al siguiente proceso. En caso de que sea menor, no hará nada.

El algoritmo de más eficiencia funciona en fases.

En la fase k-ésima, un proceso determinará si es el elegido entre los vecinos a distancia igual o menor de 2^k en ambos sentidos. Si lo es, entonces el proceso pasa a la siguiente fase. Para saber si es uno de los elegidos de esta fase, envía un mensaje con su id a los procesos vecinos inmediatos, que, después de reenviarlo al número de vecinos dependiente de k, le comunicarán el resultado, con un ACK, en caso de ser el de id mayor de entre los preguntados, o con un NACK, en caso contrario.

A continuación, se explica con el ejemplo de la imagen.

Phase 0. Cada proceso P, envía un mensaje con su id a sus vecinos inmediatos. Estos pueden contestar de dos maneras posibles:

ACK (ACKnowledge). El id del proceso que ha recibido el mensaje es menor que el contenido en el mensaje, por lo que contesta a este con ACK.
NACK (Negative ACKnowledge). El id del proceso que ha recibido el mensaje es mayor que el contenido en este, por lo que contesta con NACK.

El proceso P, si ha recibido algún NACK, resultará no elegido.

Phase 1. Los procesos que en la fase anterior han recibido un ACK por ambos lados, vuelven a enviar un mensaje a sus vecinos inmediatos, que lo reenvían al siguiente vecino. El resultado de la comparación del id de P con el del vecino a distancia de P £ 2¹, se le comunica a P, pudiendo ser ACK o NACK. En el momento en el que recibe un NACK, proceso P será no elegido.

Phase 2. Se sigue el mismo procedimiento que en la fase anterior; esta vez, los vecinos de P reenvían el mensaje hasta llegar a la distancia de P ≤ 2². En este caso, el proceso con id 6 se lo enviará al de id 7, y el de id 7 al de id 6. 7 recibirá un ACK por ambos lados, y 6, un NACK, resultando 7 como elegido, como se ve en la Phase 3.

Anillo síncrono[editar]

En un anillo síncrono de tamaño conocido n, el algoritmo funciona en fases; cada una tiene n rondas, y cada ronda es una unidad de tiempo, considerándose una ronda el salto entre procesos contiguos. En este caso, el proceso elegido como líder es el de id más bajo.

En la fase k-ésima, se comprueba si existe un proceso con id igual a k. De ser así, éste es el de id menor (al comenzar con k = 0 e ir incrementándolo fase a fase), por lo que es elegido líder y se envía un mensaje de terminación al resto de procesos. Si no hay ningún proceso con id igual a k, se pasa a la siguiente fase. Entonces, se utilizan n mensajes, que corresponden con los de terminación que se envían a todos los procesos de la red, y n(k+1) rondas, saltos entre procesos, en el algoritmo.

También se ha presentado un algoritmo para un anillo unidireccional con procesos síncronos. Asumieron que el tamaño del anillo (número de nodos) es conocido por los procesos. Para un anillo de tamaño n, están activos a nodos, tal que a ≤ n.

Cada uno decide, con probabilidad de a^-1 (cada nodo tiene la misma probabilidad que el resto de convertirse en líder ( $1/a$ )) si se va a convertir en candidato. Al final de cada fase, cada nodo calcula el número de candidatos c y, si es igual a 1, se convierte en líder.^[4]

Para determinar el valor de c, cada candidato envía un token con su identificador al principio de la fase, que se va pasando a lo largo del anillo, volviendo a quien lo envió tras exactamente n unidades de tiempo. Cuando a un proceso le llega un token con un identificador menor al suyo, descarta el token, que ya no llegará a su emisor y, por lo tanto, no podrá convertirse en líder.

Cada nodo determina c contando el número de tokens que han pasado por él.

Una aproximación similar también se usa cuando se utiliza un mecanismo de time-out para detectar interbloqueos en el sistema. También hay algoritmos para anillos de un tamaño específico.

Algoritmo uniforme[editar]

En las soluciones típicas de elección de líder, el tamaño del anillo se supone conocido para todos los procesos. En el caso de anillos anónimos que no usen una entidad externa, no es posible escoger un líder. Incluso suponiendo que el algoritmo existiera, el líder no podría estimar el tamaño del anillo (hay una posibilidad de que el algoritmo calcule mal el tamaño).

Para solventar este problema, se puede usar un líder oráculo al que cada proceso puede preguntar si hay un líder único. Por probabilidad, en algún momento, va a devolver la misma respuesta a todos los procesos.

Algoritmos con identificadores únicos[editar]

Se ha propuesto un algoritmo en el que el nodo con el mayor id es elegido líder.

Para casos en los que la elección de líder se da por la caída del nodo líder, el que detecta este fallo comienza las elecciones, este es el proceso inmediatamente anterior en el anillo lógico. Este proceso pasa su id al siguiente proceso del anillo.

En caso de que el este proceso tenga un identificador mayor que el contenido en el mensaje elección, cambia el contenido por su id. Si es menor, lo sigue pasando sin cambiar nada. En el momento en el que le llega el mensaje elección al proceso convocante, se considera que se han acabado las elecciones y se transmite el identificador elegido, también en anillo, uno detrás de otro en el mismo orden que las elecciones mediante un mensaje elegido.^[2]